| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 9284 | Max-Heap |
|
| 9292 | Simply Fractions |
|
| 9360 | Word Frequency simplified |
|
| 9364 | Find max in 3n+1 series |
|
| 9372 | 8 Queens |
|
Description
Please maintain a max-heap, which stores integers and is able to support following operations:
(1) PUSH k – Insert an integer k into the heap. k will fit in a 32-bit signed integer.
(2) POP – Delete the maximum element from the heap.
(3) TOP – Print the maximum element in the heap.
Input
There is only one set of commands. Each command occupies a line, and the total number of commands is less than or equal to 500000. You may assume that the number of elements stored in the heap will be no more than 10000 at any time.
Output
For each “TOP” command, output a line containing the value of the element on the top of the heap. In case that the heap is empty, print ”Null” instead.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given a fraction, find its simplest fraction representation.
Input
There many cases in the input. In each case, each line contains two integers a and b (a, b <= 100000), which represent the numerator and the denominator of a fraction. Input will be terminated by EOF.
Output
For each case, output a line with the simplest fraction.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given an article, find the number of appearance for queried strings.
Input
The input includes multiple test cases. In each test case, the first line contains two integers, N and M (1 <= N <= 10, 1 <= M <= 100). N indicates the number of lines in the article, and M indicates the number of strings needs to search. The next N lines are for the article, and the length of each line <= 1000. The followed M lines contains M queries, one per line, the length of each query is less than or equal to 50. The input alphabet is (a-z, A-Z) and digit (0-9).
case 1: 1 <= line length <= 100, 1 <= query length <= 20
case 2: 1 <= line length <= 500, 1 <= query length <= 20
case 3: 1 <= line length <= 1000, 1 <= query length <= 50
case 4: 0 <= line length <= 1000, 1 <= query length <= 50
Output
For each string, output the string and the number of appearance in the article, separate by ‘:’. Uppercase and lowercase are treated as the same alphabet.
Print a blank line after the output of each test case.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Consider the following algorithm:
- Input n
- Set M to be n
- If n is equal to 1, then STOP
Else Set
- M = Max(M , n)
- GOTO Step 3.
Given one integer n. Please output the M after processing the algorithm.
Input
The input includes multiple test cases. In each test case, the first line contains one integer n. Guarantee the algorithm won’t go into infinite steps when n is between 1 and 106.
1<= n <= 106
For Case1 and Case2, the value during operation will not exceed 10^7.
For Case3 and Case4, the value during operation will not exceed 10^11.
For Case1, the number of test case <= 5000
For Case2, the number of test case <= 50000
For Case3, the number of test case <= 500000
For Case4, the number of testcase <= 1600000
Output
For each testcase, output one line contains one integer M.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Each chessboard has numbers in the range 1 to 99 written on each square and is supplied with 8 chess queens. The task is to place the 8 queens on the chess board in such a way that no queen threatens another one, and so that the sum of the numbers on the squares selected is the maximum . (For those unfamiliar with the rules of chess, this implies that each row and column of the board contains exactly one queen, and each diagonal contains no more than one queen.)
Write a program that will read in the number and details of the chessboards and determine the highest scores possible for each board under these conditions.
Input
Input will consist of K (the number of boards), on a line by itself, followed by K sets of 64 numbers, each set consisting of eight lines of eight numbers. Each number will be a non-negative integer less than 100. Each case is separated by a blank line. There will never be more than 20 boards.
Testcase 1: K<=5
Testcase 2: K<=10
Testcase 3: K<=15
Testcase 4: K<=20
Output
The outputs of all test cases should be printed in order. For each test case a line, print the highest score right justified in field 5 characters wide.