733 - I2P(II)2015_Lee_Mid1補考 Scoreboard

Time

2015/04/22 08:10:00 2015/04/22 09:50:00

Clarification

# Problem Asker Description Reply Replier Reply Time For all team
# Problem Pass Rate (passed user / total user)
10538 Mid1 Josephus Composite
10543 Mid1 Queue

10538 - Mid1 Josephus Composite   

Status  |  Limits Submit

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

 There will be more than one line, each line with one integer 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<5000

Output

  The output will consist in separate lines containing the position of the person which life will be saved. 

Sample Input  Download

Sample Output  Download

Tags




Discuss




10543 - Mid1 Queue   

Status  |  Limits Submit

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.

 
A new comer has a certain group ID and a personal name. The length of the name is less than or equal to 10. For each new comer, you first check if there exists a group of the same ID. If yes, add this new comer to the end of that group; otherwise, create a new group at the end of the queue, and add this new comer to the new group. 

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.

The string in the last line is always "END" indicating the end of the input. 

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.

Note that there is a space after every string except the last one, which is ended with a newline character.

Sample Input  Download

Sample Output  Download

Tags




Discuss