Description

Given a positive integer N of int type, you are asked to find the maximum K such that N/(pow(2,K)) is a positive integer.

Input

The input is a positive integer N. (0<N)

Output

Please output pow(2,K).

 

Sample Input  Download

Sample Output  Download

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

Given a linked-list structure named Node.

 

typedef struct _Node {

    int data;

    struct _Node *next;

} Node;

Use this structure to implement a reversing linked list.

 

You will be provided with main.c and function.h, and asked to implement function.c.

For OJ submission:

       Step 1. Submit only your function.c into the submission block. (Please choose c compiler) 

       Step 2. Check the results and debug your program if necessary.

Input

The input contains a sequence of positive integers as the linked list and the order, except the last one, which is -1, indicating the end of the sequence. 

Output

The output contains the sequence of the resulting linked list.

Sample Input  Download

Sample Output  Download

Partial Judge Code

11796.c

Partial Judge Header

11796.h

Tags

Discuss

Description

Write a program that simulates a mouse in a maze. The program must count the steps taken by the mouse from the starting point to the final point.

The maze type is shown in following figure:

S$###
$$#$$
$$$##
##$$F

it consists of S (starting point), #(walls), $(road) and F (final point).

In above case, it needs 7 steps from S to F as following figure,

S$###
$$#$$
$$$##
##$$F

and the mouse can move in the four directions: up, down, left, right. There may be more than one way to reach final point, the program only need to print the least steps.

If there is no way from S to F, then print -1.

Input

The first line has an integer N(1<=N<=10^6), which means the number of test cases.

For each case, the first line has two integers. The first and second integers R and C (3<=R, C<=500) represent the numbers of rows and columns of the maze, respectively. The total number of elements in the maze is thus R x C.

The following R lines, each containing C characters, specify the elements of the maze.

Output

Print out the least steps for each case, and there is a new line character at the end of each line.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

In this problem, we simulate a simple text editor. Given a series of keyboard input texts and commands, output the final text content.

 

The text editing rules are defined as follows:

• Five special commands started with a backslash (/) character:
  1. (/I): The editing-mode changing command, which switches the mode between INSERT and REPLACE.
     1. Initially, the editor is in the INSERT mode. Then a /I command changes the mode to REPLACE, the next /I command changes the mode back to INSERT, and so on.
     2. The INSERT mode: insert the text after the cursor.
     3. The REPLACE mode:
        1. If there is a character after the cursor and it is a newline character, ***insert the text before the newline character*** (this is what we have in the existing PC operation);
        2. Otherwise, use the text to replace the existing content after the cursor.
  2. (/R /L): The two navigating commands, which move the cursor to the right or to the left;
  3. (/B): The backspace command, which deletes a character (letter, digit or newline) before the cursor;
  4. (/n): The newline command, which creates a new line after the cursor.

 

• Normal alphabetical/numerical and whitespace input (A-Za-z0-9 and ' '): directly writes (inserts or replaces) after the cursor of the text content.

 

The keyboard input sequence will not exceed 600 characters, and the text content of the testcases will also not exceed 600 characters when simulating.

 

Hint1:

#include <stdio.h>

#define MAX_SIZE 600

char content[MAX_SIZE];
char input[MAX_SIZE];

int main()
{

    fgets(input, MAX_SIZE, stdin);

    /* your code here */

    printf("%s", content);

    return 0;
}

Hint2:

Testcase1 contains /B+/L
Testcase2 contains /R+/L+/B
Testcase3 contains /R+/L+/B+/n
Testcase4 contains /n+/R+/L+/B+/I
Testcase5 contains /n+/R+/L+/B+/I

Input

The keyboard input sequence, which is only one line (i.e., without a newline character at the end).

There is always a valid command (/B /n /L /R /I) right after the backslash character.

Output

The final text content.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

The goal of this problem is to implement a text ciphering (加密) method: the Jinkela Trio transform (JTT). 

Besides the input string S to be ciphered, JTT also requires an integer parameter K. Here, we take S=”banana”, and K=7122 to explain the ideas of JTT.

Step 1.

Let N be the size of the input string (in our example N = 6). We create an array G[N] using K and the special prime number:

P = 233811181 (hexadecimal: 0xdefaced)

as follows:

X = K;

int i=0;

for(;i<N;++i){

    X = (X*P+1) % 4294967296;

    G[i] = X%N;

}

Note to use unsigned or long long to avoid overflow.

 

In this example:

G[6] = {1,0,5,2,3,0};

Step 2.

Create a 2d NxN array Q, where Q[0] (the 0-th row) corresponds to the input string S, and Q[i] (0 < i < N) corresponds to a circular left shift of i  positions with respect to the input string S. For S="banana", we obtain the following array Q:

  0 1 2 3 4 5
0 b a n a n a
1 a n a n a b
2 n a n a b a
3 a n a b a n
4 n a b a n a
5 a b a n a n

 

Step 3.

Do the following:

int i;

for(i=0;i<N;++i){
    if G[i]!=G[(i+1)%N], then swap the two rows: Q[G[i]] and Q[G[(i+1)%N]].
}

For our example, after the above step 3, we can obtain Q as follows:

  0 1 2 3 4 5
0 b a n a n a
1 a n a n a b
2 a n a b a n
3 a b a n a n
4 n a b a n a
5 n a n a b a

Finally, the result of the JTT method is the last column (i.e. column N-1) of array Q.

In our example, the last column of Q is "abnnaa". Therefore, JTT outputs "abnnaa".

Input

The first line contains two integers T, K (T<=100,1<=K<=2147483647), indicating that there’re T test cases, all of which take K as the parameter for JTT. For the next T lines, each contains a string consisting of lower case English letters as the input string for JTT to cipher. The length of the input strings will be <= 1000.

Output

Output the results of JTT for the test cases, one string per line. 

Note that you need to print a newline character ‘\n’ at the end of each line.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Cheat Sheet

printf() and  scanf() format

printf("%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

scanf("%d", &n);
 

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

 

Frequently used functions

#include <string.h>
char str[10];
scanf("%s", str);
to get the string length using 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
#include <ctype.h>
isspace(ch), islower(ch), isupper(ch), isdigit(ch)
isalpha(ch), toupper(ch), tolower(ch)

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 A

for (i = 0; i < n; i++) {
   for (j = 1; j < n; j++) {
      if (A[j] > A[j-1]) {
         /* swap A[j] A[j-1] */
      }
   }
}

operators:
!   &&    ||    ==     !=    +    -    *    /    %
>   <     >=    <=

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]

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);

}

Input

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss