## DMPG '18 G1 - Musical Chairs

View as PDF

Points: 10 (partial)
Time limit: 1.4s
Memory limit: 256M

Author:
Problem type

There are chairs in a circle. Exactly of these chairs are empty and there are students numbered from to standing at some of these chairs. Every second, each student moves forward by one chair. In particular, if they are currently standing by chair , then they will move to chair after. If a student reaches an empty chair, including at the very beginning, they will sit down for the remaining time. Who will be the last standing student?

It is guaranteed that every student begins at a different chair.

Edit: The test data has been fixed.

#### Constraints

All the indices in the input will be between and inclusive.

#### Input Specification

The first line will have two space-separated integers, and .
The next line will have space-separated integers representing the indices of the empty chairs.
The third line will have space-separated integers. The integer is the chair at which student begins at.

#### Output Specification

Output a single integer, the index of the last standing student.

#### Sample Input

7 2
2 1
6 5 4

#### Sample Output

3

• commented on May 13, 2018, 4:04 p.m.

Okay. Thanks wleung_bvg very much!

• commented on May 13, 2018, 12:30 p.m.

Will that happen?

• commented on May 13, 2018, 12:30 p.m. edited

What should I output if more than one students remain standing in the end and sit down at the same time? Will that happen?

• commented on May 13, 2018, 2:11 p.m. edited

Since there is exactly 1 less chair than students, if the last 2 students were to sit down at the same time, then they must be sitting down at the same chair. Since each student only move forward exactly one spot each second, then for this to happen, they would have had to start at the same place. Since the problem guarantees that each student starts at a different location, we know that this situation is impossible.

• commented on May 13, 2018, 3:04 p.m. edited

What if the input is:

4 2

2 4

1 2 3?

2nd student will immediately sit down. After one round, 1 sit on 2 and 3 sit on 4.

For clarification, if a student sit on a chair, will that chair count as non-empty?

• commented on May 13, 2018, 3:55 p.m.

Student 1 cannot sit on chair 2 since student 2 is already sitting there.