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

Your friend likes walking up stairs.
He likes walking up stairs so much that everytime, he attempts to walk up stairs in a way he never did before.
When walking up stairs, he either takes one step up or three steps up at once.
Specifically, given a staircase with N levels, he would decide a sequence of steps (composed of 1s and 3s) to take, such that the sum of the sequence is N.

Two ways of walking up stairs are different if and only if the sequence of steps differ.

For example, given a stairs with 5 floors, he has 4 unique ways of walking up the stairs:
a. [1, 1, 3]
b. [1, 3, 1]
c. [3, 1, 1]
d. [1, 1, 1, 1, 1]

Given N, find out how many times your friend may enjoy walking the stairs up in a unique way.

Smart as your friend is, figured out that f(n), the number of ways to walk up n levels, may be described as the following:

f(n) = f(n - 1) + f(n - 3), if n > 2
f(n) = 1, otherwise

Input

N

(N is a positive integer in between 1 and 116)

Output

A positive integer indicating the number of unique ways to walk up the stairs, with a trailing newline character.

 

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

With the improvement of your programming skill, you receive the invitation from government to design an ID card verification program. The government give you the rule of ID card below:

The ID number have special encode rule. The first word is uppercase English letter and remaining 9 words must be numbers, when applying the special encode rule, the first word will be encode to a number. (encoded by following table)

A	B	C	D	E	F	G	H	J	K	L	M	N
10	11	12	13	14	15	16	17	18	19	20	21	22
P	Q	R	S	T	U	V	X	Y	W	Z	I	O
23	24	25	26	27	28	29	30	31	32	33	34	35

The encoded ID number will be 11 digits in total and each of digit has a fixed weight from left to right(1 9 8 7 6 5 4 3 2 1 1 ). If the ID number is real, the ID number must follow the rule bellow:

"sum of each digit multiply with each weight can be divided by 10"

Take ID A135607214 for example, it can first be translate to 10135607214 and then use the special rule to compute the value 1*1 + 0*9 + 1*8 + 3*7 + 5*6 + 6*5 + 0*4 + 7*3 + 2*2 + 1*1 + 4*1 = 120. Since 120 can be divided by 10 then A135607214 is the real

Input

Input the ID card number need to examine

Output

Print out the result of verification. If the card number is true then print "Real", otherwise pint "Fake".(followed by a newline character at the end of the output string)

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

You are a smart thief who broke into sombody's house and found all the valuables.

You know the value of each item in the house, but kind as you are decided to take as few items as possible, as long as the sum of values you take is strictly greater than the sum of values of the remaining valuables.

Determine the number of items you will take.

Input

N

V_1 V_2 ... V_N

(N is a positive integer not exceeding 5000, and each V_i is a positive integer not exceeding 100000)

Output

The number of items to take, as an integer, followed by a newline character

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

There is a grid with H horizontal rows and W vertical columns, and there are obstacles on some of the squares.

Snuke is going to choose one of the squares not occupied by an obstacle and place a lamp on it. The lamp placed on the square will emit straight beams of light in four cardinal directions: up, down, left, and right. In each direction, the beam will continue traveling until it hits a square occupied by an obstacle or it hits the border of the grid. It will light all the squares on the way, including the square on which the lamp is placed, but not the square occupied by an obstacle.

Snuke wants to maximize the number of squares lighted by the lamp.

You are given H strings Si (1 <= i <= H), each of length W. If the j-th character (1 <= j <= W) of Si is '#', there is an obstacle on the square at the i-th row from the top and the j-th column from the left; if that character is ., there is no obstacle on that square.

Find the maximum possible number of squares lighted by the lamp.

Take below map for example:

8 is maximum possible number of squares lighted by the lamp. (lamp placed on second row and second column)

Input

H W

S1

...

SH

H: the lenght of the row (1 <= H <= 2500)

W: the lenght of the column (1 <= W <= 2500)

Si : the row information (contain '.' or '#')

Output

Output The maximum number of squares lighted by the lamp. (the output string followed by a newline character.)

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Given a link list structure named Node.

typedef struct _Node {

    int data;

    struct _Node *next;

} Node;

In this problem, you need to implement five operation for the linked list. 

func1: Node* createList(int *a, int size);

func2: void push_front(Node** head, int val);

func3: Node* copyList(Node* head);

func4: void deleteElementByIdx(Node** head, int idx);

func5: void SwapElementByIdx(Node** head, int idx1, int idx2);

#include <stdio.h> #include <stdlib.h> #include "function.h" void traversal(Node* head); int main(){ int T,M,inst,i; int val,idx1,idx2; scanf("%d%d", &T,&M); Node* head = NULL; int *array = (int*)malloc(sizeof(int)*M); for(i=0; i<M; ++i){ scanf("%d",&array[i]); } if(M > 0){ head = createList(array, M); traversal(head); } while(T--){ scanf("%d",&inst); if(inst == 0){ // insert scanf("%d",&val); push_front(&head, val); }else if(inst == 1){ // copy link list Node* otherHead = copyList(head); /* free original list*/ while(head != NULL){ Node* temp = head; head = head->next; free(temp); } head = otherHead; }else if(inst == 2){ // delete element scanf("%d",&val); deleteElementByIdx(&head, val); }else if(inst == 3){ // swap link element scanf("%d%d",&idx1, &idx2); SwapElementByIdx(&head,idx1,idx2); } traversal(head); } /* free linked list*/ while(head != NULL){ Node* temp = head; head = head->next; free(temp); } return 0; } void traversal(Node* head){ if(head == NULL) return; while(head != NULL){ printf("%d ", head->data); head = head->next; }printf("\n"); }

Note: We guarantee that function 1, 3~5 will not operate on an empty list.

Input

T M

S1 .. SM

t1_command

...

tT_command

T: the number of command ( 0 <= T < 200)

M: the number of initial linked size (0 <= M <= 2000)

Si: the value of the initial array (0 <= Si <= 1000)

ti_command: the command description

(0: push_front, 1: clone, 2: delete, 3: swap)

Hint: 

testcase1 : contain only createList operation

testcase2: contain only push_front operation

testcase3: contain createList , push_front, copyList operation

testcase4: contain createList , push_front , copyList operation, deleteElementByIdx

testcase5: contain all operation 

Output

Output the element in linked list whenever the operation be called. 

Sample Input  Download

Sample Output  Download

Partial Judge Code

12594.c

Partial Judge Header

12594.h

Tags

Discuss