Description

 

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 append a copy of str2 to str1 strcat(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 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;
        }
    }
}

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]

Input

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

The Tower of Hanoi is a mathematical game puzzle. It consists of three rods, which are A, B and C. The puzzle starts with n disks in ascending order of size on rod A, the smallest at the top.

The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules:

1.   Only one disk can be moved at a time.

2.   Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack i.e. a disk can only be moved if it is the uppermost disk on a stack.

3.   No disk may be placed on top of a smaller disk.

Write a program to simulate the moves of the disks. Print the number of disk which is moved in each step.

 

For example, if n = 3, the moves of each steps are:

move disk 1 from rod A to rod C
move disk 2 from rod A to rod B
move disk 1 from rod C to rod B
move disk 3 from rod A to rod C
move disk 1 from rod B to rod A
move disk 2 from rod B to rod C
move disk 1 from rod A to rod C

You should print out:

1
2
1
3
1
2
1

HINT : You can modify this sample code and implement the function 'hanoi'

#include <stdio.h>
void hanoi(int n, char A, char B, char C);

int main(){
    int n;
    scanf("%d", &n);
    hanoi(n, 'A', 'B', 'C');
    return 0;
}

Input

An integer n (0<n<20), which means the number of disk.

Output

Print out the number of disk which is moved in each step, and there is a '\n' at the end of each line.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Determine the positions of each letter in a given string (with length < 1000001). Then output the positions of each letters in lexicographical order. For each letter, output its positions in increasing order. 

 

For example, “AbAABBCAaa”

 

A is at position 0, 2, 3, 7; B is at position 4, 5; C is at position 6; a is at position 8, 9; b is at position 1.

Input

There is only one row, and it is a string S with length smaller than 1000001. 

Output

Please output the answer according to the above requirements, and remember to add ‘\n’ at the end of the outcome of every letter.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

There are N students in line according to the seat number, then M pairs of students exchanged their positions in the sequence.

Can you help the teacher find the positions of students K₁ ~ K_Q? 

 

For example, N = 4 M = 3, and three exchanges are:

1 2

2 3

3 4

The seat arrangement of students during the exchange process:

1 2 3 4

-> 2 1 3 4

-> 2 3 1 4

-> 2 3 4 1

The final positions of students 1 ~ N are 4 1 2 3

Input

The first line contains three integers N M Q, the number of students, the number of pairs who exchange positions and the number of students whose positions the teacher wants to know.

Each of the next M lines contains two integers a b, indicating the seat exchange.

The last line contains Q integers that mean K₁ ~ K_Q, giving the id. of the students whose positions the teacher wants to know.

 

 

test cases:

(4/6) 1 <= a, b, K_i <= N, M, Q <= 1000

(1/6) 1 <= a, b, K_i <= N, M <= 1000, 1 <= Q <= 1000000

(1/6) 1 <= a, b, K_i <= N, M <= 100000, 1 <= Q <= 1000000

NOTE:

To pass test cases 5 and 6, please consider how to reduce unnecessary loop iterations.

Output

The positions of students K₁ ~ K_Q

Note that you need to print ‘\n’ at the end of the output.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Denny is an elementary school student. However, he is not good at math, and hopes you can help him. One day the teacher gave some addition homework. When he copied the formulas, some errors occurred, where all the '+'s became spaces or lowercase english letters.

To solve this problem, you need to correct the message sent by Denny, and calculate the sum.

 

For example:

The message sent by Denny: 32n2333 34a1 44a3

The corrected message: 32+2333+34+1+44+3

The sum of the message: 2447

Input

The input contains multiple lines, where each line contains several space-separated strings.

The last line contains only "0\n", and you don't need to output anything this line.

 

Testcases:

Guarantee that the beginning and end of each line are numbers(not include '\n'), and no more than 1500 characters in a single line.

(3/12) multiple lines, each line contains 3 space-separated strings consisting of only numbers

(3/12) two lines, a single string consisting of numbers and letters

(3/12) multiple lines, each line contains 3 space-separated strings consisting of numbers and letters

(3/12) No constraint.

Output

The output contains multiple lines, each line contains a number: the sum of the corresponding corrected message.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Given a carpet, it has some numbers on it. It can be represented by a n*m rectangle and each square has its own value. 

For example:

 

You are asked to cut out a piece of carpet (should not be empty) so that the sum of the numbers in it is the greatest.

In this example, you should cut out the blue part whose total sum is 110. Note that the cut-out part must be a rectangle too.

 

Input

Given two positive integers n and m in the first line.

 

Next, there're n lines, each containing m signed integers (c_i1 c_i2 c_i3 ... c_im), which represent the carpet. 

Constraints:
|c_ij| <= 1000 for all test cases
- 50%: min{n,m} = 1, n*m <=10⁵
- 25%: max{n,m} <= 20
- 25%: max{n,m} <= 80

Output

Output a single line containing the largest sum of the carpet you cut out.
Remember to print '\n'.

Sample Input  Download

Sample Output  Download

Tags

Discuss