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 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]

Input

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Given a two-dimensional array of size R _x 5 (1 < R < 100).

We want to sort the two dimensional array according to each row.

For example:

After sorted

Note that

1.      This problem involves three files.

• function.h: Function definition of sortArray.
• function.c: Function implementation of sortArray.
• main.c: A driver program to test your implementation.

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

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

Hints : bubble sort algorithm

/* Using bubble sort to rearrange an array A[n] */

for (i = n; i > 0; i--) {

   for (j = 1; j < i; j++) {

      if (A[j-1] > A[j]) {

         /* swap A[j-1] A[j] */

      }

   }

}

function.h

#ifndef FUNCTION_H #define FUNCTION_H #define COLUMN 5 void sortArray(int R, int (*array)[COLUMN]); #endif

main.c

#include <stdio.h> #include <stdlib.h> #include "function.h" int main(void) { int i,j,n,N,R; scanf("%d", &N); int (*array)[COLUMN]; // array is a pointer to an one-dimensional array of COLUMN elements for(n=0;n<N;n++){ scanf("%d", &R); array = (int(*)[COLUMN])malloc(sizeof(int)*COLUMN*R); for(i = 0; i < R; i++) for(j = 0; j < COLUMN; j++) scanf("%d", &array[i][j]); sortArray(R, array); for(i = 0; i < R; i++){ printf("%d", array[i][0]); for(j = 1; j < COLUMN; j++){ printf(" %d", array[i][j]); } printf("\n"); } if(n!=N-1) printf("\n"); free(array); } return 0; }

Input

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

For each case, the first line has an integer R (1<R<100) represent the numbers of rows. The following R lines, each containing 5 integers, specify the elements of the two-dimensional array.

Output

Print out all elements of the sorted array row-by-row.

All of the integers in the same line are separated by a space and there is a '\n' at the end of each line. All of the arrays should be separated by a new line character (\n).

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Tags

Discuss

Description

A substring S' of a given string S with length N is a contiguous sequence of N letters from S.
For instance, the substrings with length 2 of “abcde” are “ab”, “bc”, “cd”, “de”.

Given a string S and an integer N together with another string P.
Your task is to find all substrings from S with length N that have the same pattern as P, and the frequencies of these substrings.

In this problem, the patterns of two strings A, B are the same if and only if the numbers of each kind of letters in A, B are equal.
For example:

• A = “ouo”, B = “oou” have the same pattern

  number of letter	a~n	o	p~t	u	v~z
  A = “ouo”	0	2	0	1	0
  B = “oou”	0	2	0	1	0

• A = “pap”, B = “oao” have different patterns

  number of letter	a	b~n	o	p	q~z
  A = “pap”	1	0	0	2	0
  B = “oao”	1	0	2	0	0

Moreover, under a given N, the frequency of a substring S' is its number of occurrences within all resulting substrings of S.
For example: S = “ababa”, S' = “aba”

• all substrings with length 3 = {“aba”, “bab”, “aba”}
• frequency of S' = 2

Hint:
To efficiently check if a substring S' and P have the same pattern as required by this problem: 

1. use two 1D arrays to record the numbers of each kind of letters in S' and P, respectively; 
   • ​​Just like the example above. TP[0] = the number of ‘a’ in P, TP[1] = the number of ‘b’ in P, and so on
2. check if each pair of corresponding elements in the two 1D arrays are equal. 

Input

One string S and an integer N on the first line.
Another string P on the second line.

• 1 ≤ N ≤ 3,000
• 1 ≤ |S|, |P| ≤ 3,000
• S, P contain only lower-case English letters.

Output

Print on the first line the number M of distinct substrings of S with length N that have the same pattern as P.

On the following M lines, print the (S', F') pair for the M substrings that have the same pattern as P, where F' is the frequency of S', one pair per line, in decreasing order of their frequencies. When the frequencies tie, please use the lexicographical order of the substrings.
Remember ‘\n’ on the end of line.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

In the village of hakka's, there are lots of big big mazes.
It is said that the delicious hakka mochi (麻糬) is hidden in one of the secret mazes.

You, a poor programmer, working for hakkas without getting any paid,
want to find out the secret, and change the job to selling mochi,
since being a programmer is too tired, and may die overworked.
So, one day, you sneaked into the village head's house, and stole all the mazes' maps out.

You have got T maps, where
each map shows that the maze is N*M grids big,
and starts from (1,1) (the left top corner), and the mochi is at (N,M) (the right bottom corner),
and a '#' on the map represents a wall,
and a '*' on the map represents that you can walk through that grid,
and the 'A', 'B' and 'C' represent 3 different types of traps (陷阱) on the map.

Walking in a hakka's maze, starting from the starting point (1,1),
if you are standing on a road,
you can go to the up, right, left, or the bottom grid near you,
but you cannot be on a wall,
and there are 3 kinds of traps on the map, where
at the first step, for example during (1,1)->(1,2), the type A traps will be on, and the B, C traps will be off,
at the second step, the type B traps will be on, and the A, C traps will be off,
at the third step, the type C traps will be on, and the A, B traps will be off,
at the fourth step, the type A traps will be on, and the B, C traps will be off,
and repeatedly.

You want to make sure if it is possible to walk from the starting point (1, 1) to the ending point (N, M) of each map,
so you won't waste time finding the mochi.

ouo.

Example 1:

If the input is:
1
1 3
*A*
The output should be 'No' (without quotes), since if you move right, the 'A' trap will be on, so you cannot move.

Example 2:

If the input is:
1
1 6
**BCA*
The output should be 'Yes', since you can move (right, left, right, right, right, right, right) and get to the end point,
but you cannot just go right straight since you will step on the B trap.

Hint:
As shown in the above Example 2, a grid should be allowed to be visited more than once, in order to check if we can obtain a walking sequence that fits the trap on-off pattern. 
For this, we can use a 3D array visited[N][M][3] to record if a grid (x,y) has been previously visited in a different trap setting as follows:

• if visited[x-1][y-1][0]==1: (x,y) has been visited during a step where the A traps are on, and the B, C traps are off;
• if visited[x-1][y-1][1]==1: (x,y) has been visited during a step where the B traps are on, and the A, C traps are off;
• if visited[x-1][y-1][2]==1: (x,y) has been visited during a step where the C traps are on, and the A, B traps are off.

In this way, we allow (x,y) to be visited more than once while avoiding TLE.

Input

The first line contains an integer T,
representing the number of maps.

Starting from the second line, there are T maps, in each of which,
the first line contains 2 numbers N, M, indicating that the maze is N*M big,
then each of the following N lines contains M characters, where
a character '#' represents that the grid is a wall,
a character '*' represents that the grid is a road, and
the characters 'A', 'B', 'C', represent 3 different types of traps.

It is guaranteed that:
for all test cases: 1 <= T <= 10, 1 <= N, M <= 1000,
for test case 1, without traps, 1 <= N, M <= 10,
for test case 2, without traps, 1 <= N, M <= 800,
for test case 3, without traps, 2 <= N, M <= 200,
for test case 4, without traps, 2 <= N, M <= 1000,
for test case 5, with traps, N = 1, 1 <= M <= 300,
for test case 6, with traps, 1 <= N, M <= 800.

Output

Output T lines, in each of which
if it is possible to walk from the starting point to the ending point in the corresponding maze,
output "Yes", otherwise, output "No". (Without quotes)

Sample Input  Download

Sample Output  Download

Tags

Discuss