| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 10509 | Queue |
|
| 10518 | Moving Books |
|
| 10519 | Josephus with Composite |
|
Description
Consider a queue of groups. Each group has a unique ID denoted by a string of uppercase alphabets. The length of an ID is less than or equal to 6 characters.
Input
The input contains several lines. Each line presents the group ID and the name of a new comer. The group ID and the name are separated by a space.
Output
The output contains one line. The first string is the ID of the last group in the queue. After that you need to print the name of members in the last group, one by one according to their coming order.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
The problem is to parse a series of commands to move the books that lie on the table. Initially there are n books lying on the table with book bi adjacent to book bi+1 for all 0 <= i < n-1, as shown in the diagram below:
|
Book N-1 |
|
...... |
|
Book 2 |
|
Book 1 |
|
Book 0 |
|
Table |
The valid commands and limited for moving books are:
Illegal commands:
- A = B
- A or B is not in the range (e.g. You cannot move or remove any book that does not exist)
All illegal commands should be ignored and should have no affect on the configuration of books.
Valid commands:
l move A on B
Puts book A on book B.
As below:
0 1 2 3 4
>> move 1 on 3
0 2 3 1 4
l move A under B
Puts book A under of book B.
As below:
0 1 2 3 4
>> move 1 under 3
0 2 1 3 4
l remove A
Remove book A from the list.
As below:
0 1 2 3 4
>> remove 1
0 2 3 4
l exit
Finish moving the books, print the final status.
Input
The input begins with an integer n on a line by itself representing the number of books in the book world. You may assume that 0 < n <= 10000.
The number of books is followed by a sequence of book commands, one command per line. Your program should process all commands until the exit command is encountered.
You may assume that all commands will be of the form specified above. There will be no syntactically incorrect commands.
Output
Your output should contains one line of sequence which represents the order of books from the bottom to the top.
Each number is followed by a single space. And you are asked to add a new line character at the end.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
The Josephs problem is notoriously known. For those who are not familiar with the problem, among n people numbered 1, 2, . . . , n, standing in circle every mth is going to be executed and only the life of the last remaining person will be saved. Joseph was smart enough to choose the position of the last remaining person, thus saving his life to give the message about the incident.
The persons are eliminated in a very peculiar order; m is a dynamical variable, which each time takes a different value corresponding to the Composite numbers succession (4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, ...). So in order to kill the i-th person, Josephus cousin counts up to the i-th composite.
A composite number is a positive integer that has at least one positive divisor other than one or the number itself. In other words, a composite number is any integer greater than one that is not a prime number.
For example, there are 6 people in a circle, and the sequence of couting is composite number succession (4, 6, 8, 9, 10, …).
In the beginning, the step to kill m = 4. The sequence of killing people is as follows.
1, 2, 3, 4.............................(kill 4, and m is changed to 6)
5, 6, 1, 2, 3, 5.....................(kill 5, and m is changed to 8)
6, 1, 2, 3, 6, 1, 2, 3.............(kill 3, and m is changed to 9)
6, 1, 2, 6, 1, 2, 6, 1, 2.........(kill 2, and m is changed to 10)
6, 1, 6, 1, 6, 1, 6, 1, 6, 1.....(kill 1)
Then print 6 as answer.
Input
Each line with 1 integers, n. n is the number of people.Input terminated by EOF.
Testcase 1 : 1<=n<100
Testcase 2 : 100<=n<1000
Testcase 3 : 1000<=n<10000
Testcase 4 : 10000<=n<50000
Testcase 5 : 50000<=n<100000
Output
The output will consist in separate lines containing the position of the person which life will be saved.