| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 9104 | Carry In |
|
| 9108 | String Reverse |
|
| 9112 | Is it a forest? |
|
| 9116 | DNA Sorting |
|
| 9120 | Minimum Bounding Rectangle |
|
Description
Compute how many carries will occur when calculating the sum of two decimal numbers A and B.
Input
For each case a line, there are two positive integers A and B. ( 0 < A, B < 101000 ) There are multiple cases terminated by EOF.
Output
For each case a line, output how many carries occur.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
A string S is given, please output the reverse of S.
Input
Input contains multiple test cases. Each case contains one line with a string S. The string S only consists of A-Z, a-z, 0-9. The length of S is less than or equal to 107. The input is terminated by EOF.
Output
For each test case, output a line with the reverse of S.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
An undirected graph is a forest if it contains no cycle.
Given an undirected graph, output "Yes" if it is a forest, otherwise "No".
Input
The input contains at most 20 test cases. For each test case, the first line contains two positive integers N (2 <= N <= 500000) and M (0 <= M <= 500000) separated by a space; N is the number of vertices and M is the number of edges in the undirected graph G. The vertices in G are denoted by v1, v2, ..., vN. In the next M lines, each line contains two integers i and j separated by a space, which means that there is an edge between vi and vj.
There is a blank line after each test case. The last test case is followed by two zeros in one line.
Output
For each test case, output "Yes" if it's a forest, otherwise "No".
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Here we consider the string composed of only characters A, C, G, and T. For each character x in the string, we define the unsortedness of x to be the number of characters at the right of x whose alphabetical order is smaller than x.
For example, if the string is ACACA, the unsortedness of the five characters (from left to right) are respectively 0, 2, 0, 1, 0.
The unsortedness score of the whole string is defined to be the sum of the unsortedness of each of its characters.
Given a string, output its unsortedness score.
Input
Input contains multiple testcases. Each case contains one line with a string. The string is formed by four uppercase characters 'A', 'C', 'G', and 'T'. The length of string is less than or equal to 107.
The input is terminated by EOF.
Output
For each case, output a line with the unsortedness score.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Consider a rectangular grid paper with width W units and height H units. We mark some points on the paper, and wrap it around with the left and the right edges glued together to form a cylinder of height H and circumference W.
Find a rectangle R of smallest area, whose four vertices fall on the grid points, that contains all the points we marked. Note that the interior of the rectangle could now cross the edges on the left and the right, since we have wrapped the paper around. For example, the figure below illustrates a valid rectangle with its lower-left corner and upper-right corner locating at (24, 2) and (6, 6) on a grid paper of width 28 units and height 9 units. The bold black line is the glued left edge and right edge of the grid paper.
Figure. An example of a valid rectangle with its interior cross the left and the right edge of the grid paper
Input
The first line of the input contains an integer T, denoting the number of test cases. Each case starts with three integers N, W, H, which are the number of points marked, the width and the height of the grid paper. Each of the following N lines contains a pair of integers x (0 ≤ x ≤ W), y (0 ≤ y ≤ H), representing the x, y coordinates of the point. There will be a blank line before the first line of each case. You may assume that there is no degenerated case that all of the points lie on a line parallelling to the x-axis or y-axis.
Output
For each test case, print the answer in the format “Case i: w h” in a line, where i is the sequence number of the test case, w (0 < w < W) and h (0 < h < H) are the width and the height of the minimum area rectangle R.
Technical Specification
For data set #1, N ≤ 5, W ≤ 500, H ≤ 250.
For data set #2, N ≤ 100, W ≤ 1000, H ≤ 500.
For data set #3, N ≤ 1000, W ≤ 30000, H ≤ 20000.
For data set #4, N ≤ 5000, W ≤ 5000000, H ≤ 3000000.