| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 11575 | The Blocks Problem |
|
| 11578 | Base |
|
| 11969 | Prime |
|
| 11972 | Is it a forest? |
|
| 11973 | Inversion Pair |
|
Description
Problem description
The problem is to parse a series of commands that instruct a robot arm in how to manipulate blocks lying on a flat table. Initially there are n blocks on the table (numbered from 0 to n-1) with block bi adjacent to block bi+1 for all 0 <= i < n-1 as shown in the figure below:
Figure 1. Initial Blocks World
The valid commands for the robot arm that manipulates blocks are:
move a onto b
where a and b are block numbers, put block a onto block b after returning any blocks that are stacked on top of blocks a and b to their initial positions.
move a over b
where a and b are block numbers, put block a onto the top of the stack containing block b, if there are other blocks, stacked on top of block a or block b . return them to their initial position, after returning any blocks that are stacked on top of block a to their initial positions.
pile a onto b
where a and b are block numbers, moves the pile of blocks consisting of block a, and any blocks that are stacked above block a, onto block b. All blocks on top of block b are moved to their initial positions prior to the pile taking place. The blocks stacked above block a retain their order when moved.
pile a over b
where a and b are block numbers, puts the pile of blocks consisting of block a, and any blocks that are stacked above block a, onto the top of the stack containing block b. The blocks stacked above block a retain their original order when moved.
quit
terminates manipulations in the block world.
Any command in which a = b or in which a and b are in the same stack of blocks is an illegal command. All illegal commands should be ignored and should have no affect on the configuration of blocks.
Input
The input begins with an integer n on a line by itself representing the number of blocks in the block world. You may assume that 0 < n < 25.
The number of blocks is followed by a sequence of block commands, one command per line. Your program should process all commands until the quit command is encountered.
You may assume that all commands will be of the form specified above. There will be no syntactically incorrect commands.
Output
The output should consist of the final state of the blocks world. Each original block position numbered i ( 0 <= i < n where n is the number of blocks) should appear followed immediately by a colon. If there is at least a block on it, the colon must be followed by one space, followed by a list of blocks that appear stacked in that position with each block number separated from other block numbers by a space. Don't put any trailing spaces on a line.
There should be one line of output for each block position (i.e., n lines of output where n is the integer on the first line of input).
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given a decimal integer n and a base k, translate n to the corresponding k-based number.
Input
The first line contains an integer t (1 <= t <= 20), which indicates the number of test cases in the input. Each test case is given in a line, containing two integers n and k (n <= 10000000, k<=9).
Output
Output the number in base k.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Output the number of primes between two given integer a and b.
Input
The first line of input contains a positive integer t (t<=1000), which indicates the numbers of test cases in the input. In the next t line, each line contains two positive integers a, b(1 <= a <= b <= 10000), indicating the range between a and b.
Output
Output the number of primes in the range between a and b (including a and b).
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. (1 <=vi <= N) 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
In a number sequence S = {S1, S2, S3, …, Sn}, we called (i,j) an “inversion pair” when Si > Sj and i < j.
Given S, calculate the number of inversion pair in this sequence.
Input
There are several numbers of test cases. Each case begins with an integer N in a line, and then N integers N1~Nnfollow, each in a single line. The input is terminated by the number zero.
For case 1, 1<=N<=10, 0<=Ni<=100, the answer <231.
For case 2, 1<=N<=100, 0<=Ni<=106, the answer <231.
For case 3, 1<=N<=106, -231<=Ni<231, the answer <263.
For case 4, 1<=N<=106, -231<=Ni<231, the answer <263.
Output
For each test case, print a number of inversion pairs in the given sequence.