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 3 functions:

1. void Push(Node** ptr_head,int x)
2. void Pop(Node** ptr_head)
3. 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

Partial Judge Header

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

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:

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

Doraemon aims to make a fortune from the significant daily price changes of dorayakis. He plans to buy a dorayaki on one day and sell it on another to profit from the price spread. To keep his plan secret, Doraemon will only hold one dorayaki at a time, meaning he must sell each one before buying another.

Given the dorayaki prices over a continuous span of N days, please calculate the maximum profit Doraemon can gain.

(This part differs from the Practice Problem "Doraemon's dorayaki")
Recently, Doraemon decided not to be too ostentatious (炫耀的) for this evil plan and chose to limit the number of transactions he can make (where a 'transaction' is defined as buying and selling one dorayaki). In this problem, an integer M is given to restrict Doraemon to do at most M transactions. If M equals -1, this means that there is still no limit to the number of transactions.

Sample I/O Explanation

N = 8 days, M = unlimited transactions (-1), prices = [7, 2, 5, 6, 3, 8, 1, 9]
Buy on day 2 (-2) -> Sell on day 4 (+6) -> Buy on day 5 (-3) -> Sell on day 6 (+8) -> Buy on day 7 (-1) -> Sell on day 8 (+9)
Maximum profit = (-2) + 6 + (-3) + 8 + (-1) + 9 = 17

N = 8 days, M = 1 transaction, prices = [7, 2, 5, 6, 3, 8, 1, 9]
Buy on day 7 (-1) -> Sell on day 8 (+9)
Maximum profit = (-1) + 9 = 8

N = 8 days, M = 2 transactions, prices = [7, 2, 5, 6, 3, 8, 1, 9]
Buy on day 2 (-2) -> Sell on day 6 (+8) -> Buy on day 7 (-1) -> Sell on day 8 (+9)
Maximum profit = (-2) + 8 + (-1) + 9 = 14

Input

• The first line contains two integers N, M (1 ≤ N ≤ 10⁷, M ∈ {-1, 1, 2}), representing the number of days and the limited number of transactions.
• The second line contains N integers: x₁, x₂, ..., x_N (1 ≤ x_i ≤ 10⁹), where x_i represents the price of dorayakis on the i-th day.

Output

Output a single line containing one integer — the maximum profit Doraemon can gain.

Constraints

• Test Case 1 : N ≤ 20, M = -1
• Test Case 2 : N ≤ 20, M = 1
• Test Cases 3 ~ 4 : N ≤ 10⁵, M = -1
• Test Case 5 : N ≤ 10⁵, M = 1
• Test Case 6 : N ≤ 10⁵, M = 2
• Test Case 7 : N ≤ 10⁷, M = 1
• Test Case 8 : N ≤ 10⁷, M = 2

Hints

• N ≤ 20: Brute-Force Recursion or Loop
• N ≤ 10⁵: Recursion and Memorization
• N ≤ 10⁷: Be aware of memory space limitation (128 MB), and try to observe the characteristics of the problem and use an approach other than recursion

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Koying and Thanksone are enthusiastic students who excel in programming, and are good friends. However, Thanksone likes to play tricks (捉弄) on Koying by hacking his accounts.

To avoid being hacked again, Koying decided to set up a high-strength password, ensuring that Thanksone could never hack him again.

Unfortunately, Thanksone knows Koying very well, and is also very clever. He finally discovered that Koying’s password follows the recursive function below (Koying frequently talks in his sleep and has a pet phrase (口頭禪) “OAO” ^^):

where + represents string concatenation.

Koying’s password is the substring of S_N from the L-th position to the R-th position, denoted as S_N[L : R].

Now, Thanksone provides you with Koying’s sleep-talking, along with values for N, L, and R. Please determine Koying’s password to assist Thanksone in hacking Koying’s computer.

And when you successfully help Thanksone hack Koying’s computer, Koying’s facial expression will be --> OAO.

Input

//return the k-th character of S_N, that is, S_N[k]

char find(long long int N, long long int k) {

...

}


int main() {

...

    for (long long int i = L; i <= R; i++)

        printf("%c", find(N, i));

    printf("\n");

    return 0;

}

Output

Please output a string representing S_N[L : R].

Remember to print a ‘\n’ at the end of the output.

Sample Input  Download

Sample Output  Download

Tags

Discuss