ZOJ Problem Set - 2731
There is a well-known story about Flavius Josephus, a famous historian of the first century. Legend has it that Josephus wouldn't have lived to become famous without his mathematical talents. During the Jewish-Roman war, he was among a band of 41 Jewish rebels trapped in a cave by the Romans, Preferring suicide to capture, the rebels decided to form a circle and, proceeding around it, to kill every third remaining person until no one was left. But Josephus, along with an unindicted co-conspirator, wanted none of this suicide nonsense; so he quickly calculated where he and his friend should stand in the vicious circle.
Josephus' great talents really saved his life, as well as saved his tale for us to here. For this reason, he got a great many fellows. But he and his fans were so unfortunate that they are caught by the Romans again. The Romans were very interested of the death game played previously by the Jewish, so they wanted Josephus and his fellows to play it again and offered the last person to survive. The Romans have also heard of Josephus' talents, so they didn't let him choose his position to stand in the circle. However, the fellows of Josephus are so loyal to him, that they were all willing to die for him. Josephus had got a chance to select a fellow to die instead of him in case that he was about to be executed, and the counting process will be adjusted accordingly.
For instance, if there are 8 people in total, every 4th person is executed, and Josephus is the first person in the circle. The people in these positions will be killed first:
There are 4 people left, and Josephus would be the next person to die if the process continues. Now, Josephus could select a fellow to be executed instead of him. If he chooses the 6th person, he would survive. Please note, the counting will resume immediately after the person died for him (start at 7 in this case). Please see the picture for the details.
Given the above information, could you help Josephus to calculate the fellow to choose to save the famous historian?Input
Input will consist of up to 100 cases. Each case consists of one line containing 3 numbers. n, the number of people in the circle, 1 <= n <= 1000; m, every m-th person will be killed, 1 <= m <= 1000000; p, the position of Josephus in the circle, one-based, 1 <= p <= n. The input will end with three 0 (zero), which should not be processed.Output
For each case, output the position of the fellow to choose in a single line. If there is no need for anyone to die for Josephus, output the position of Josephus himself.Sample Input
8 4 1 8 4 6 1000 1 1 0 0 0Sample Output
6 6 2
Author: YANG, Chao
Source: Zhejiang University Local Contest 2006