| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 12448 | Hu_cheatsheet |
|
| 13021 | Longest Binary Distance |
|
| 13096 | Queen Problem |
|
| 13097 | kora kora |
|
| 13098 | String Zip |
|
Description
printf() and scanf() format
printf("%d", n);
FORMAT ARGUMENT TYPE
%d, %i int decimal
%lld long long
%llu unsigned long long
%u unsigned int
%x unsigned int hexadecimal
%#x unsigned int hexadecimal with prefix 0x
%f double
%Lf long double
%c char to print a character
%s char * string (character array ended with '\0')
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)
#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");
}
logical and comparison operators operators:
! && || == != > < >= <=
arithmetic operators:
+ - * / %
bitwise operators:
& | ^ << >> ~
int strcmp(const char *lhs, const char *rhs);
int strcat(const char *lhs, const char *rhs);
int strcpy(const char *lhs, const char *rhs);
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.
Note : If you are using visual studio, add #pragma warning(disable:4996) in the first line so that you can use scanf on your local machine.
Input
Output
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Binary distance for an integer is the number of "0" between two adjoining "1"s in the binary representation of an integer. For example, the binary representation of 37 is 1001012, so 37 has two binary distances which are 2 and 1.
If there aren't any "0"s between two adjoining "1"s, the binay distance will be 0. e.g. 7 (1112) has two binary distances = 0.
If the number of "1" in the binary representation is less than 2, the binay distance will be -1. e.g. 8(10002) only has one binary distances = -1.
In this problem, you are asked to compute the longest binary distances for the given q integers.
For example, if the input integer is 37, you should output 2 as the answer.
Input
First line countains an integer which denotes q. (1 ≤ q ≤ 20)
Then, q lines follow.
Each line contains one integer N (0 ≤ N ≤ 263 - 1).
Output
Output contains q lines and each line contain the longest binary distance of the input integer ended with '\n'.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given a NxN array, your goal is to place N queens on it, and all of them should be safe from each other. We define the weighted sum as the total value of where your queens are placed. Please find out the second-highest weighted sum among the given array, whose value is different from the highest one.
A queen is safe from each other if there's no other queen in the same row/column/two diagonal lines.
For example, given a array:
| 1 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 |
| 1 | 2 | 3 | 1 |
The pattern with highest weighted sum is
| 1 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 |
| 1 | 2 | 3 | 1 |
1 + 1 + 1 + 3 = 6, and the second highest weighted sum is
| 1 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 |
| 1 | 2 | 3 | 1 |
1 + 1 + 1 + 2 = 5, so the answer to this example is 5.
Input
The input contains an integer N, follow by a NxN array A.
1 <= N <= 11, |elements in A| <= 1010.
Output
Output the second highest weighted sum of given array, followed by a newline character. If there's no such value, output "Invalid".
Sample Input Download
Sample Output Download
Tags
Discuss
Description
There is a row with N blocks. Blocks are numbered from left to right in 1-based indexing. The i-th block's value is ai.
First you have to sort these blocks by their value in increasing order. So the order of blocks may be changed after sorting.
Then you need to execute Q operations. There are two kinds of operations:
- Let m = N' divided by 2 rounding up, where N' is the number of blocks now. Then remove the m-th block.
- Output the k-th block's value. Then divide all the blocks' value by 2 rounding down.
It's guaranteed that the first type of operations appears at most N - 1 times(i.e there must be at least one block all the time).
Note: be careful of the efficiency of your strategy. And the difference between rounding up and rounding down is to carry or to chop the remainder. For instance:
- 5 divided by 2 rounding up is equal to 3
- 5 divided by 2 rounding down is equal to 2
Input
The first line contains one integer N (1 ≤ N ≤ 105) – the number of blocks.
The second line contains N integers a1, a2, ..., aN (0 ≤ ai ≤ 1018) – the value of each block.
The third line contains one integer Q (1 ≤ Q ≤ 105) – the number of operations you need to execute.
Then Q lines follow. The i+3-th line contains one integer typei (1 ≤ typei ≤ 2) – the type of operations you need to execute. If typei = 2 then one integer k (1 ≤ k ≤ N', where N' is the number of blocks then) follows.
It's guaranteed that:
- The 1st testcase must be as same as Sample below
- For the testcases 2 and 3: 1 ≤ N, Q ≤ 3000
- For the testcases 4 and 5: the number of the 2nd type operations ≤ 60
- For the testcases 6: ai ≤ 60
Output
For every 2nd type operations, output the k-th block's value then.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
ZIP is an archive file format that supports lossless data compression. There are many way to zip compress data nowadays, such as RLE, LZW,Huffman Coding ans so on. Today your friend think out a method similiar as RLE(run length encoding) to compress data.
The zip way purpose by your friend:
Given the sequence contain only English letter or digit, the runs of data(sequences in which the same data value occurs in many consecutive data elements) will be store as a single data value and count, rather than as the original run.
Take squence aaabbb444 for example, aaabbb444 can be encoded to 3a3b3'4'
When there are less than three consecutive "letters", you don't need to compress it.
For example, aabbbdcccc can be encoded to aa3bd4c.
For those non-consecutive "digits", simply store the digit, you don't need to store the count.
For example, aabbb1ccc2dd33dd can be encoded to aa3b'1'3c'2'dd2'3'dd
Besides encoding, your friend is also interested in the compress rate of the result, which is defined by
Compress Rate = (length of the encoded string)/(length of the original string).
He ask you to help him implement the zip algoithm program and analysis the compress rate of the method. As the best friend of you, you decided to try your best to finish the program.
Input
Given a sequence contain only English letter or digit.
(2 <= the length of the sequence <= 1000)
Output
Print out the zip string and the compression rate, both followed by a newline character.
If the compression rate is less than 1.0 then print out "Compress rate: X.XXX" with the result (round to the third digit after the decimal point), otherwise print out "The string can't zip".
You can use printf("Compress rate: %.3f\n", rate) for printing the result.