| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 11246 | Cheat Sheet Chen Mid2 |
|
| 11318 | CS Simple 001 |
|
| 11319 | CS Simple 002 |
|
| 11320 | CS Simple 003 |
|
| 11321 | CS Simple 004 |
|
| 11322 | Melting Pot |
|
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:
|
a[0][0] |
a[0][1] |
a[0][2] |
a[0][3] |
a[0][4] |
|
a[1][0] |
a[1][1] |
a[1][2] |
a[1][3] |
a[1][4] |
|
a[2][0] |
a[2][1] |
a[2][2] |
a[2][3] |
a[2][4] |
|
a[3][0] |
a[3][1] |
a[3][2] |
a[3][3] |
a[3][4] |
|
a[4][0] |
a[4][1] |
a[4][2] |
a[4][3] |
a[4][4] |
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 M-by-N integer matrix, compute the maximum column sum.
[Example]
For example, if the input is a 3-by-4 matrix containing
3 2 4 5
2 8 3 7
3 1 5 6
The maximum column sum is 18 (=5+7+6).
Input
The first line of the input contains two integers M and N indicating the size of the integer matrix (M for row and N for column, 0 < M, N< 10).
Next M lines list the elements of the matrix row by row. All elements are integers.
Output
The output contains an integer indicating the maximum column sum. There is NO newline character at the end of line.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given a list of N digits, re-arrange the digits in non-decreasing order.
[Example]
For example, if the list is 4 7 4 9 7, the output should be 4 4 7 7 9.
Input
The input has two lines.
The first line is an integer N indicating the number of digits in the list.
The second line contains the N digits, separated by a whitespace.
Output
The output is the re-arranged digits, separated by a whitespace. The is NO newline character at the end of the ouput.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given a sequence of positive integers, divide them into partitions (sequentially and greedily from left to right) so that the sum of the integers in each partition is as large as possible but no larger than 10.
All integers in the sequence are greater than 0 and no greater than 10.
[Example]
For example, if the input is
2 8 3 6 5 1 2 1 9 8 7 4 5
then the partitions are
[2, 8], [3, 6], [5, 1, 2, 1], [9], [8], [7], [4, 5]
The output is the number of partitions, which is 7 for this example.
Input
The first line of the input is an integer N indicating the length of the sequence. (0 < N < 1000)
The second line contains the sequence of N integers. All integers are larger than 0 and no greater than 10.
Output
The output is the number of partitions. There is NO newline character at the end of line.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Consider nine variables that are indexed by integers 1, 2, 3, 4, 5, 6, 7, 8, 9.
The nine variables are divided into two groups, say, Group A: 1 3 5 7 9 and Group B: 2 4 6 8.
Given a sequence of SWAP commands, your program has to perform the exchange between the specified members.
[Example]
For example, if the SWAP command is 2 3, then Group A becomes 1 2 5 7 9 and Group B is now 3 4 6 8.
If the next SWAP command is 5 4, then Group A becomes 1 2 4 7 9 and Group B becomes 3 5 6 8.
If the next SWAP command is 7 9, then nothing changes, Group A is still 1 2 4 7 9 and Broup B is 3 5 6 8.
The task is to print the final members of Group A.
[Hint]
Similar to the problem of finding equivalence relation. Variables that belong to the same group are considered equivalent.
Input
The first line of input is an integer K indicating the number of variables in Group A. (0 < K < 9)
The variables that are not in Group A are all in Gropu B.
The second line of input contains the K variables that belong to Group A. The variables that are not in Group A are all in Group B.
The third line of input is an integer N indicating the number of SWAP operations. (0 < N < 100)
The next N lines specify the SWAP operations for exchaning group members.
Each SWAP operation is represented by a pair of integers indicating the indexes of the two variables to be exchanged.
Output
The output contains only one line listing the variables that belong to Group A.
The variables are listed in ascending order with respect to their indexes, with a whitespace in between, and NO newline character at the end.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
The input contains N strings (0 < N < 100). Each string consists of at most 9 lowercase letters.
1. Find the longest nondecreasing substring(s) of each string. (There might be more than one longest nondecreasing substring.)
2. Count the number of occurrences (frequency) of each distinct substring.
3. Sort the substrings according to their frequencies (high to low). If two substrings have the same frequency, sort them in lexicographical order (alphabetical order).
4. Use the ranking of each substring as its score. E.g., the first one gets 1 point, the second gets 2 points, and so on.
5. Use the scores of substrings to re-evaluate the original input string and print the total score of each input string.
[Example]
For example, the input may be
7
xxaccb
xabcud
yyxacc
efgacc
tsefgab
aca
rqabcud
The longest nondecreasing substrings are
acc
abcu
acc
efg acc
efg
ac
abcu
The frequencies are
abcu 2
ac 1
acc 3
efg 2
The sorted order should be
acc 3
abcu 2
efg 2
ac 1
Their scores are
acc 1
abcu 2
efg 3
ac 4
The re-evaluation results are
xxaccb 1 (because acc gets 1 point)
xabcud 2 (because abcu gets 2 points)
yyxacc 1 (because acc gets 1 point)
efgacc 4 (because efg gets 3 points and acc gets 1 point)
tsefgab 3 (because efg gets 3 points)
aca 4 (because ac gets 4 points)
rqabcud 2 (because abcu gets 2 points)
Another example: If the input is
2
fgcdab
fgdbca
The longest nondecreasing substrings are
fg cd ab
fg bc
The frequencies are
fg 2
cd 1
ab 1
bc 1
The sorted order should be
fg 2
ab 1
bc 1
cd 1
Their scores are
fg 1
ab 2
bc 3
cd 4
The re-evaluation results are
fgcdab 7 (fg gets 1 point, cd gets 4 points, and ab gets 2 points)
fgdbca 4 (fg gets 1 point and bc gets 3 points)
Input
The first line of input is an integer N indicating the number of input strings. (0 < N < 100)
The next N lines are the input strings. Each string consists of at most 9 lowercase letters.
Output
The output contains N lines of strings and their scores. The strings are listed as their original input order.
Each line contains a string and its score.
Each line has a newline character at the end. (Note that the last line also needs to be ended with a newline character.)