| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 9184 | Partial Sum |
|
| 9188 | Tree Recovery |
|
| 9192 | Find the Longest Palindrome |
|
| 9196 | Territory Expansion |
|
| 9200 | Postfix Evaluation |
|
Description
Given n integers and q queries, in which each query defines a range, find the sum of the n given integers within the range.
Input
The first line contains an integer t (1 <= t <= 20), which indicates the number of test cases. In each test case, the first line contains an integer n (n <= 105), specifying how many integers will be given. The next line contains n integers, in which the ith integer represents ai (-231 <= ai <= 231-1). The followed line contains a positive integer q (q <= 105), denoting the number of queries. Next q lines define q queries, one per line. Each query is specified by two integers a and b (1 <= a <= b <= n), meaning a range, in which the partial sum of the given integers are queried.
Output
For each query, output a line with the partial sum of the given integers within the queried range.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Give two strings which represent the pre-order traversal and the in-order traversal of a binary tree, generate the post-order traversal of the binary tree.
Input
The input consists of several test cases. Each test case has two strings in a line separated by a space. The first string is the pre-order traversal of the binary tree; the second string is the in-order traversal of the binary tree. Each string will contain only capital characters and the characters will be unique.
Output
For each test case, output a string to represent the post-order traversal of the binary tree.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Palindrome is a string that is identical to its reverse, like "level" or "aba". Given a string, find the longest palindrome in the string.
Input
The input consists of multiple lines. Each line contains a string. The length of each string is less than 1000.
Output
In each test case, output the longest palindrome in the string. If there are many palindromes of the same length, output the first one in the string.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
There are many countries on a map. Each of them has a unique ID, which is a positive integer. All of them want to expand their territories. A country can expand its territory if its neighboring land (up, down, left, and right) has not been occupied by any other countries. The expansion speeds are the same for all countries. (We may consider that all countries simultaneously perform one expansion move at a time.) If two or more countries want to occupy the same land, the country with the smaller ID can occupy the land. The expansion stops if no changes of the map can be made.
Input
The input file begins with an integer T (1 < T < 1000), indicating the number of test cases. Each test case begins with three integers N, M, and K (0 < N < 300, 0 < M < 300, K
Output
For each test case, output the final area (number of lands) of each county, ordered by the country’s ID (from small to large). Print a blank after each case.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Evaluate the result of a given numerical expression written in postfix notation.
Input
The first line of the input contains an integer N (N ≤ 100) which denotes the number of test cases. Each test case begins with an integer M (M ≤ 10000) representing the number of tokens in the expression, followed by M tokens in the next line. Tokens are separated by spaces and the operators contain only “+”, “-”, “*” and “/”; the operands are integers in the range [0, 100]. The division operator “/” here is considered as integral division. You may assume that all of the expressions are valid (divide-by-zero would never occur) and the answer will fit in 32-bit signed integers. Evaluated results (in each stage of the evaluation ) will fit in 100-digit signed integers and divide-by-bignumber would never occur.
Output
The output of each test case occupies a line. Each line begins with the test case number “Case i:”, and then a space character followed by the evaluated answer.