| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 12022 | prefix sum |
|
| 12421 | password-Z |
|
| 12422 | lazy_circulant matrix |
|
| 12423 | ID Card Verification |
|
| 12425 | Simple Zip |
|
| 12429 | Going To Class |
|
Description
Given a series of numbers, e1, e2, e3, ..., eN.
With these numbers, we want to know what the sum is in some consecutive range.
In every testcase, you will be given M queries.
Each of them contains two integers which represent left bound (L) and right bound (R) respectively.
Your mission is to give the result of eL + eL+1 + ... + eR,
-
Hint 0 : If you get WA for testcase 1, sample input and output might help you.
Hint 1 : If you get TLE for next three testcases, you should think how to decrease some redundant operations for calculations. Try to store other useful information in the array, instead of sum up all the elements for every query! You may search for the problem's title: "prefix sum".
A usual computer can run 109 basic operations (such as +, -, &, |) in 1 second. Althought this depends on the judging server, this number serves as a good estimation for the running time of your code. Try to figure out how much operations your code needs to execute to finish all the computations (since not all operations in your code are basic operations, another estimate criterion is 108 operations (+, -, *, /, =, ...) in 1 second)!
Hint 2 : If you get MLE, you have to reduce the size of array you created and decide what exactly should be in the array.
Input
First line contains one integer N which is the size of elements.
Second line will have N integers representing all elements in the testcase.
Third line contains one integer M which is the number of queries.
For following M lines, each line contains exactly two integers that stand for left bound (L) and right bound (R) respectively.
It is guaranteed that:
1. 10 ≦ N ≦ 1,000,000
2. 0 ≦ ei ≦ 100,000, for 1 ≦ i ≦ N
3. L must be less than or equal to R, and R won't exceed the size of elements.
Output
For each query, just give the answer in one line.
Also, remember to print '\n' in the end of line.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
A sequence from 1 to N is written in a zigzag pattern on a given number R of rows .
For example, N = 12, R = 3. You should encode it as
And if N = 12, R = 4. You should encode it as
In the end, you should output this sequence in order like 1 5 9 2 4 6 8 10 12 3 7 11 .
seperated by space and end by space, no need to change line.
Input
Two number N & R.
N is the length of sequence.
R is the numbers of row.
Output
An encoded sequence in row-major order.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given a vector of dimension 5, use it to create an 5-by-5 circulant matrix. An example of circulant matrix:
1 5 4 3 2
2 1 5 4 3
3 2 1 5 4
4 3 2 1 5
5 4 3 2 1
Input
5 integers.
Output
The 5-by-5 circulant matrix. Every element is followed by space and don't forget to change line in the end each row even in the last.
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
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' and the compress rate is 8/9 = 0.89
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 progeam.
Note : Fix time complexity problem modified by 2019/10/12
Input
S_1
S_2
...
S_N
Given the sequence contain only English letter or digit.
(2 <= the length of each sequence < 1000, and the input testcases are less than 1000)
Note that: the sequence is case-sensitive and the testcase is end of EOF character.
Output
Print out the zip string and the compression rate, each line followed by a newline character. (If the compression rate less than 1.0 then print out "compress rate:6.3f" with the result, otherwise print out "the string can't zip")
Note that : Using float not double.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Your friend is a lazy person.
He has N classes on each Monday, where all of these classes happen in the same room.
Like everybody else, he likes some classes but also dislikes other classes.
Specifically, the i'th class gives A[i] happiness to him, where A[i] may be positive, negative, or zero.
It would be nice for him to attend classes so that the sum of happiness he get is maximum, but it is not an option for him to leave the class and then come back for another, because he is too lazy to move. In other words, he may only choose to attend classes that are conducted successively (one after another).
Again, lazy as your friend is, he wants you to find the maximum happiness he can achieve by optimally choosing the classes.
Input
N
A_1
A_2
...
A_N
(N is a positive integer not exceeding 5000, A_i is an integer where|A_i| <= 10000)
It is guaranteed that at least one of A_i is positive.
Output
The maximum happiness, followed by a newline character.