Want to try solving this problem? You can submit your code online if you log in or register.

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):

- If the minister is standing at the same point as an empty chair, the
minister will sit down in it.
- Otherwise, the minister will step one place clockwise around the circle
to the next point. If the minister was previously at point i (with i < N),
the minister will now be at point i+1. If the minister was previously at
point N, the minister will now be at point 1.

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`.

- The first line of input will contain two space-separated integers N and
K.
- The second line of input will contain K space-separated integers
representing the points at which there are chairs, in increasing order. Hence,
the first chair in this list will be the Prime Minister's.
- The third line of input will contain K+1 space-separated integers
representing the points of ministers, in increasing order. The ministers are
numbered from 1 to K+1 by their position in this list.

Your program should write to the file `shuffleout.txt`. Your output
file should contain two lines.

- The first line should contain one integer: the number of the minister who is
in the first seat at the end of the game.
- The second line should contain one integer: the number of the minister who is
left with no seat at the end of the game.

10 3 2 5 8 3 4 6 8

3 1

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:

- 1 ≤ N ≤ 1,000,000
- 1 ≤ K ≤ 100,000
- All chair and minister positions will be integers between 1 and N
inclusive. No two chairs will have the same position and no two ministers will
have the same initial position.

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:

- For 30% of the available marks, 1 ≤ N ≤ 1,000.

Your score for each test case will be 100% if both lines are correct, 50% if exactly one is correct, and 0% otherwise.

Privacy
statement

© Australian Mathematics Trust 2001-2022

Page generated: 22 May 2022, 12:20pm AEST