Description

Given several operations, push x, pop, print, reverse, create a linked list dynamicly.

• push x: Add one Node (with data = x) at the front of linked list.
• pop: Delete the Node at the front of linked list.
• reverse: reverse the current linked list
• print: output the linked list in given format.

You have to implement 1 function :

1. void Reverse_List(Node** ptr_head)

 

Note: Modify the Node* head by Node** ptr_head

Input

There’re operations on several lines.
All operations are one of push x, pop, print, reverse.
It’s guaranteed that:

• Number of operations is less than 5,000,000
• Integer x is in [−1000,1000]
• The maximum length of linked list is less than 10,000.

Output

Output the linked list for every print.

 

Sample Input  Download

Sample Output  Download

Partial Judge Code

12575.c

Partial Judge Header

12575.h

Tags

Discuss

Description

Wild cats take care of each other in the wild. However, when winter comes, the preys are not enough to feed all the cats.

In this problem, you are asked to help decide who can enjoy the precious food for three different categories of cats: apprentice, elder, and kitty.

First, the cats dine according to the following order of their occupations:

1. elder

2. kitty

3. apprentice

Then, except that the apprentices have the dining priority of the young over the old, for the other two occupations, the old have higher priority. If the occupations and the ages of two or more cats are the same, they will dine in lexicographic order according to their names.

Input

There are multiple test cases.

The first line of each test case contains two integers N and M, indicating the number of cats and the portions of food respectively, where 0<N,M<=10000.

The next N lines are the information of each cat, including name, occupation, and age.

The length of the names will not exceed 30 letters and will contain no spaces.

Output

Please output the cats that could eat the food in order, each name a line.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Last Pokemon Contest (神奇寶貝華麗大賽) between Satoshi (小智) and Haruka (小遙) ! After Satoshi won the victory in Battle Pyramid, Satoshi and Haruka signed up for an unofficial Pokemon Contest in Terracotta Town.

Pokemon Contest is a contest in which trainers and Pokemons coordinate strength and beauty. It is divided into two stages. In the first stage, the Performance Stage, trainers and their Pokemons will perform moves to showcase their styles and skills. In the second stage, the Battle Stage, trainers battles against each other as well as demonstrating charm of their Pokemons.

Satoshi and Haruka met in the Battle stage, where Satoshi's Sceptile (蜥蜴王) fought against Haruka's Blaziken (火焰雞). In the final ten seconds of the battle, Haruka's Blaziken activates Blaze (猛火) and fires Overheat (過熱). To battle in a dazzling style, the pattern of Overheat is cleverly designed with golden ratio:

The pattern of Overheat can be expressed with a string. First, Haruka and Blaziken design two short patterns F0 and F1. Then they generate longer patterns using the following recurrence formula: Fn-2 + Fn-1 = Fn (+ means string concatenation). Finally, Haruka tells Blaziken a number n, and Blaziken fires the Overheat with pattern Fn.

Given F0, F1, n, and k, please find out the k-th character in Fn.

For full episode, please google "AG191 Satoshi vs. Haruka! Last Battle!!" or refer to this page.

Explanation on Sample IO

All test data provide same F0 = "abc", F1 = "def". We can generate the following patterns:

• F2 = "abcdef"

• F3 = "defabcdef"

• F4 = "abcdefdefabcdef"

The first test data asks 0-th character of F0, therefore output 'a'. Similarly, the outputs for the second to fifth test data are 'd', 'f', 'f', 'e', respectively.

Input

The input contains multiple test data. The first line of input contains an integer T, being number of test data. After that are T test data.

The first line of test data contains two non-empty strings F0 and F1.

The second line of test data contains two integers n and k.

• 1 <= T <= 100

• F0 and F1 contain only lower case alphabets (a-z) and have length no greater than 2000.

• 0 <= n < 60 and 0 <= k < |Fn|, where |Fn| is length of Fn

Output

For each test data, output the answer in a single line.  Remember to add new line in the end.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

CHEAT SHEET

BASIC I/O

printf() and  scanf() format

printf("%d", n);

scanf("%d", &n);

 

FORMAT  ARGUMENT TYPE

%d, %i  int           decimal

%u      unsigned int

%x      unsigned int  hexadecimal

%#x     unsigned int  hexadecimal with prefix 0x

%f      double  

%Lf     long double

%e, %E  double      scientific notation

%c      int         to print a character

%s      char *      string (character array ended with '\0')

%p      void *      print memory address

%g, %G  double      %f or %e depending on the length
 

FORMAT  ARGUMENT TYPE

%d      int *       &n, store the input integer in n

%ld     long *

%lld    long long *

%u      unsigned int *

%f      float *     read float

%lf     double *    read double

%Lf     long double *   read long double

%c      char *      read 3 characters %3c

%s      char *      read a string until whitespace

%n      int *       with %s, to get string length

                   char a[100]; int len; 
                  scanf("%s%n", a, &len);
                  len will have the string length

 

OPERATION
!   &&    ||    ==     !=    +    -    *    /    %
>   <     >=    <=

 

To create a 5-by-5 two-dimensional array, we need to write

int a[5][5];

It will be indexed as follows:

a[0][0]	a[0][1]	a[0][2]	a[0][3]	a[0][4]
a[1][0]	a[1][1]	a[1][2]	a[1][3]	a[1][4]
a[2][0]	a[2][1]	a[2][2]	a[2][3]	a[2][4]
a[3][0]	a[3][1]	a[3][2]	a[3][3]	a[3][4]
a[4][0]	a[4][1]	a[4][2]	a[4][3]	a[4][4]

 

How to read the following data?
1 2 3 4 5 e
#include <stdio.h>
int main(void)
{
    int x;
    while (scanf("%d", &x) == 1) {   
     printf("x=%d\n", x);
    }
    return 0;
}

 

How to read the following data?

2

L 5 2
D 5 3

#include <stdio.h>

int main(void)

{

   char ch;
   int i, n, row, col;

   scanf("%d", &n);

   for (i=0; i<n; i++) {

      while(getchar()!='\n');

      scanf("%c%d%d", &ch, &row, &col);

   }

   return 0;

}

 

Using for loops to print a two-dimensional array

   for(i = 0; i < row; i++) {
      for (j = 0; j < col; j++) {
         printf("%5d", A[i][j]);
      }
      printf("\n");
   } 

 

Using bubble sort to rearrange an array ap

for (i = 0; i < n-1; i++)
{
    for (j = 0; j < n-1-i; j++)
    {
        if (ap[j] > ap[j + 1])
        {
            temp = ap[j];
            ap[j] = ap[j + 1];
            ap[j + 1] = temp;
        }
    }
}

qsort 

you have to include <stdlib.h>

usage :

void qsort (void *array, size_t count, size_t size, comparison_fn_t compare);

qsort an int array

int compare_int (const void *a, const void *b)

{

    const int *va = (const int *) a;

    const int *vb = (const int *) b;

    return *va-*vb;

}

 

qsort a double array

int compare_double (const void *a, const void *b)

{

    const double *da = (const double *) a;

    const double *db = (const double *) b;

    return (*da > *db) - (*da < *db);

}

 

How to avoid common errors and how to debug for OJ

1. Put the arrays in the 'global' area. Set their size bigger than required. Avoid using variable-length arrays (e.g. int arr[n];). Keep the array size fix (e.g., int arr[1000];).

2. After writing the code for reading input data, you may print out the data to check if your code reads them correctly. Do not proceed to write subsequent code before you confirm that.

3. If your program crashes, usually it is caused by memory-related errors. Check the ranges of for-loops to see if your code attempts to read or write the elements out of the arrays’ boundary.

*(a+i) is equivalent to a[i]
(a+i) is equivalent to &a[i]

 

FREQUENTLY USED FUNCTIONS

#include <string.h>

char str[10];

scanf("%s", str);
fgets (str, 10, stdin);

gets(str);

 

to get the string length : strlen(str)

to compare two strings : strcmp(str1, str2) ==0 if equal

to compare the first n chars of two strings : strncmp(str1, str2, n) ==0 if equal

to copy str2 to str1 : strcpy(str1, str2)

to copy the first n chars of str2 to str1 : strncpy(str1,str2, n), remember to add '\0' to str1

to get the first token in str1 splitted by delim : token = strtok(str1, delim), and use loop to get next token

example:

#include <string.h>
#include <stdio.h>

int main () {
   char str[80] = "This is - www.tutorialspoint.com - website";
   const char s[2] = "-";
   char *token;
   
   /* get the first token */
   token = strtok(str, s);
   
   /* walk through other tokens */
   while( token != NULL ) {
      printf( " %s\n", token );
    
      token = strtok(NULL, s);
   }
   
   return(0);
}

to check if str2 is str1's substring: strstr(str1, str2), return pointer to the first character of the substring in str1.
example:

#include <stdio.h>
#include <string.h>


int main () {
   const char haystack[20] = "TutorialsPoint";
   const char needle[10] = "Point";
   char *ret;

   ret = strstr(haystack, needle);

   printf("The substring is: %s\n", ret);
   
   return(0);
}

 

#include <ctype.h>

isspace(ch), islower(ch), isupper(ch), isdigit(ch)

isalpha(ch), toupper(ch), tolower(ch)

 

Input

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

There are N students in the class, and now they're going to play the game of making sentences again.
Similarly, there are rules for making sentences: the teacher will randomly select students who can make sentences, and randomly decide what they can do.

There are 4 types of operations (the students are indexed from 1 to N):

1. reverse x: reverse student x's sentence
2. print x: print student x's sentence, and a newline character at the end of the line
3. append x y: append student x's sentence to student y's sentence, if y.length < x.length, otherwise append y's sentence to x's sentence ("y.length" means length of student y's sentence; "x.length" means length of student x's sentence)
4. delete s x: delete the first occurrence of s in student x's sentence (do nothing if the sentence does not contain s)

Note: Please use malloc() and free() properly.

Input

The first line contains two integers N, M: the number of students and the number of operations.
Then the following N lines, each line contains a string, where the i + 1 th line represents the initial value of the i th student's sentence.
The last M lines, each line contains one type of operation.

Constraints:
0 < x, y <= N <= 100
0 < M <= 1000
|s| <= 10000

The sentences would only contain lowercase letters.
Note that the length of a student's sentence may exceed 10000 after some operations.

Testcases 1~2: operations can only be "reverse" or "print"
Testcases 3~4: operations can only be "reverse", "print" or "append"
Testcases 5~6: no further constraints

Output

Output student x's sentence when performing the operations of "print".

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

After a whole semester's learning, professor Bear is now examining your learning progress. She knows that some of you never take homework seriously or resubmit the problem that had failed in the past exam, so she decided to introduce you to a problem that is based on past problems one more time.

But it would be cruel for professor Bear to do such things and let most of you get 0 scores on this problem, so she would provide some hints from some of the "electric gods" in the computer science department. But yet, inevitably to mention, some of the hints might be wrong since those "electric gods" aren't all quite "有料".

So you have to distinguish the correct hints yourself, based on your observation about these "electric gods". Maybe you don't know who they are, maybe they are all wrong. After all, you have to count on your own. But let's take a look at what they said first.

• Stiff Waist Beast(master of Japanese mahjong): All I know is I know everything.
• Pigeon(aims to be master of Japanese mahjong): I think Stiff Waist Beast is the best.
• Little Pants(the winner): Don't pretend to be me and say something weird. Also, why there are so many DP problems?
• PolarisChiba(the one you'll never know): kiraling~
• Tipsy Lin(the most handsome one): Do you have the AC code?
• DYY(You know who he is): Programming is trivial, unless you haven't learned calculus first.

With a glance at what those "electric gods" had said, you may be helped to solve the problem below:

---

Given a string \(s\) that consists of only lowercase Latin characters, there are \(Q\) operations to apply on this string.

There are 4 types of operations, with the following 4 forms:

• \(1\) \(A\) \(B\)
• \(2\) \(id\) \(C\)
• \(3\) \(id_a\) \(id_b\)
• \(4\) \(l\)

For operation of type \(1\), you have to turn every \(A\) in the given string to \(B\).

For operation of type \(2\), you have to set the \(id\)th character to \(C\).

For operation of type \(3\), you have to swap the \(id_a\)th character and the \(id_b\)th character.

For operation of type \(4\), you have to circularly shift the string to the right for \(l\) characters, i.e., each \(s[i]\) now becomes \(s[j]\) such that \(j \equiv i-l \space mod \space (the \space length \space of \space the \space string)\).

After the \(Q\) operations, you should print the resulting string in one line(remember to print a new line character).

Input

The first line contains a string \(s\), which consists of only lowercase Latin characters.

The second line contains an integer \(Q\).

The next \(Q\) lines, each contains an operation.

Constraints

• \(1 \le |s| \le 10^6\)
• \(1 \le Q \le 10^6\)
• \(0 \le id, id_a, id_b \le |s|-1\)
• \(A, B, C \in \{a \dots z\}\)
• \(1 \le l \le |s|-1\)

Subtasks

• Testsets [1, 2]: There are only type 1 and type 2 operations.
• Testsets [3, 6]: There are only type 1 and type 2 and type 3 operations.
• Testsets [7, 8]: \(1 \le |s|, Q \le 10^3\)
• Testsets [9, 12]: No further constraints.

Output

Print your answer in one line and end with a newline character.

Sample Input  Download

Sample Output  Download

Tags

Discuss