The polls are looking grim for the government of Absurdistan. Leadership speculation and high-profile scandals dominate popular current affairs shows Tomorrow This Morning and An Antiquated Event. In order to radically change public perceptions, the leaders plan to remove a ministry position and blame all the problems of the day on the ousted minister. At the same time, the other cabinet positions will be shuffled so as to portray a fresh, new face of government.
Naturally, the ministers can not agree between themselves who will be blamed and expelled, nor can they agree who will take which remaining ministry positions (including the position of Prime Minister). They decide to play a fair game of Musical Chairs to the tune of Party Rock Anthem in order to resolve these disputes.
There are K ministry positions available, each represented by a physical seat at a point around a circle. The K+1 ministers are also initially standing at points around the circle. Points on the circle are labelled clockwise from 1 to N, such that point 1 immediately follows point N. No two ministers will be initially standing at the same point, and no two chairs will be at the same point.
Each second, all the ministers who are still standing do the following (simultaneously):
Since there are K+1 ministers, eventually all K seats will be taken and the one minister remaining without a seat will be booted out and shamed by the media. Furthermore, the minister sitting in the first seat in the circle will have the place of Prime Minister. (The `first' seat in the circle is defined as the first seat clockwise from point 1.)
Your task is to determine who will be Prime Minister and who will be expelled from cabinet after the reshuffle. Note that your program can score half of the available marks for correctly answering only one of these questions, and will score full marks for correctly answering both.
Your program should read from the file shufflein.txt.
Your program should write to the file shuffleout.txt. Your output file should contain two lines.
10 3 2 5 8 3 4 6 8
In the first second, the fourth minister (at point 8) will immediately sit down on the chair beneath her. The other three ministers will move one place around the circle. In the next second, the second minister (now in position 5) will sit down on the second seat. The first and third ministers will continue walking around the circle until the third minister reaches position 2 and sits down, leaving the first minister with no chair to sit in.
To evaluate your solution, the judges will run your program against several different input files. All of these files will adhere to the following bounds:
As some of the test cases will be quite large, you may need to think about how well your solution scales for larger input values. However, not all the cases will be large. In particular:
Your score for each test case will be 100% if both lines are correct, 50% if exactly one is correct, and 0% otherwise.