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

Description

Given an integer pointer array **ptr with size N, and an integer array *array with size (N+1)*N/2. Please use malloc function to allocate memory to **ptr and *array. The *array is an ascending sequence of numbers. Each pointer in array **ptr shall point to one element of *array. And the elements pointed by the **ptr are also ascending.

 

For example, when n = 5, the size of **ptr will be 5, and the size of *array will be 15. The first pointer of **ptr is *ptr[0] which points to array[0], and the second pointer of **ptr is *ptr[1] which points to array[1], and the third pointer of **ptr is *ptr[2] which points to array[3], and the fourth pointer of **ptr is *ptr[3] which points to array[6].

Input

The first line is size of **ptr

The second line is offset

offset < size <10000

Output

Print each pointer of **ptr + offset

Note that you need to print a newline character ‘\n’ after each number, that is, just one number will be shown in each line of the output.

Sample Input  Download

Sample Output  Download

Partial Judge Code

12588.c

Partial Judge Header

12588.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

related problem : 12574 - New Year

Alice is a grownup. She thinks New Year is a tradition that involves many troublesome events such as family reunion, etc. Even worse, there is always one event that can despair her - giving red envelopes to relatives( a.k.a. people in your family whom you will only meet once a year ).

Her family tree looks like this. Alice has to give red envelopes to relatives marked in red circles.

Since Alice is a grownup who is expected to be kind, mature, showing respect to the elderlies, and showing care to the younger generations.  She is giving red envelopes to :

• 1 for parents, 1 for grandparents, 1 for grand-grand-parents, 1 for grand-...-grandparents

• 1 for each of siblings' children

• 1 for each of children, children's children, children's children's children, children's ... children's children

Therefore, the version "New Year Family Tree" for Alice looks like the following graph. Relatives marked with red nodes in the "New Year Family Tree" are whom Alice has to give red envelopes to.

Alice has a large family, she has to give many red envelopes in New Year's Eve. Given Alice's "New Year Family Tree", please tell Alice how many red envelopes she is going to give.

 

Maybe Useful Hints - 1

In the previous 12574 - New Year, you learned to find who will give red envelopes to a specific person.

Try to find for each person, whether Alice will give a red envelope to him/her.

Maybe Useful Hints - 2

Q : How to count the number of "children, children's children, children's children's children, children's ... children's children" in a faster way?

A : Recursion may be a good approach

Consider this simple family tree : Let f(x) be the number of people in family tree x

Input

The input is in the following format :

  N
  P1 P2 P3 ... PN

• N is an integer which means there are N people in the "New Year Family Tree" (including Alice). People are numbered from 1 to N. Alice is numbered with N.

• There are N integers in the second line. Pi (the i-th number counted from the left) is the parent of person i. If Pi = -1, it means that person i 's parent is too old and has passed away.

Technical Restrictions

• 1 <= N <= 10^5

• 1 <= Pi <= N or Pi = -1

• Only the oldest grand-...-grandparents has passed away in the "New Year Family Tree"

• Each person has at most 5 children

Test Case

• Test 1 : n <= 100, can be passed using hint 1

• Test 2 - 3 : n <= 2000, can be passed using hint 1

• Test 4 - 6 : n <= 100000, can be passed using hint 2

 

Output

Output how many red envelopes Alice will give. Remember to add a newline character in the end.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Little brick is once playing a RPG game.
In this game, there are some magical reels(魔法卷軸) that can increase your skill level.
As a serious OCD patient (強迫症患者),
he can only accept that every skill he has is at the same level.

At the beginning, every skill is at level 0,
and he has N magical reels,
the ith reel can increase one of his skill by X_i levels.
LittleBrick wants to have as many skills as possible,
and he also want to use all N reels.

Tell LittleBrick what is the maximum number of skills he may have.

ouo.

For Example 1: 
6
1 1 2 2 3 3
The answer is 4, since you can make 4 skills to reach the same level 3,
by distributing the reels like (1, 2), (3), (1, 2), (3)

For Example 2: 
5
1 1 2 5 3
The answer is 2, since you can make 2 skills to reach the same level 6,
by distributing the reels like (1, 5), (1, 2, 3)

For Example 3: 
3
1 2 4
The answer is 1, since you can make only 1 skill to reach the same level 7,
by distributing the reels like (1, 2, 4)

HINTS :

1. You can get testcases 1 ~ 3 by using the same code that you used in your final practice "The Beauty of Distributing".

2. In order to get testcases 4 ~ 6, we suggest you to do some optimizations (優化).

 

MORE HINTS :

1. We suggest you to do "3 optimizations" in your code.

2. We give you a piece of sample code below for your reference, and use it to further explain the three optimizations:

    I. We've provided Optimization 3 in the sample code below for you to use directly.

    II. We've also highlighted the recommended places for Optimization 1 and Optimization 2 in the sample code.

Sample code:

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

int n, box; // n = total reel number, box = SUM / ans
int a[1000];
bool vis[1000];

bool solver(int step, int sum) {
    if (step == n) return true;

    for (int i = 0; i < n; i++) {
        // Try to pick an unused reel to fill the current box

        // Case 1 : If sum < box after picking the reel
        // => Pick more reels to fill the current box by calling solver recursively

        // Case 2 : If sum == box after picking the reel
        // => Start with a new box (skill) by calling solver recursively with sum set to 0
        // => IMPORTANT : You can do Optimization 2 in this case after returning from solver

        if (sum == 0) return false; // Optimization 3
    }

    return false;
}

int main() {
    int T, SUM, ans; // SUM = sum of all reels, ans = total skill number

    scanf("%d", &T);

    while (T--) {
        // Read test case data

        // Optimization 1

        // Find the answer recursively and print the answer
    }

    return 0;
}

Input

The first line contains an integer T, represent the number of test cases.
For each test case, the first line is an integer N,
which represents the number of reels LittleBrick has.
The next lines contains N number X_i, separate by spaces,
which represents the number of levels the i_th reels can increase to a single skill.

It is guarantee that:
For all test cases:
1 <= T <= 10,
1 <= N <= 100,
1 <= Xi <= 100

For test case 1 ~ 3:
1 <= N <= 10,
For test case 4:
1 <= N <= 100, 1 <= Xi <= 5
For test case 5 & 6:
1 <= N <= 100

Output

For each test case,
output the maximum number of skills LittleBrick can learn,
and a newline character after the answer.

Sample Input  Download

Sample Output  Download

Tags

Discuss