DMPG '18 G1 - Musical Chairs

View as PDF

Submit solution

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

Problem type

There are N chairs in a circle. Exactly K of these chairs are empty and there are K+1 students numbered from 1 to K+1 standing at some of these chairs. Every second, each student moves forward by one chair. In particular, if they are currently standing by chair N, then they will move to chair 1 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.


For all subtasks:

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

Subtask 1 [30%]

1 \le K < N \le 5\,000

Subtask 2 [50%]

1 \le K < N \le 200\,000

Subtask 3 [20%]

1 \le K < N \le 1\,000\,000

Input Specification

The first line will have two space-separated integers, N and K.
The next line will have K space-separated integers representing the indices of the empty chairs.
The third line will have K+1 space-separated integers. The i^\text{th} integer is the chair at which student i 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



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

    Okay. Thanks wleung_bvg very much!

  • 0
    DarthVader336  commented on May 13, 2018, 4:30 p.m.

    Will that happen?

  • 1
    DarthVader336  commented on May 13, 2018, 4: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?

    • 4
      wleung_bvg  commented on May 13, 2018, 6: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.

      • 1
        DarthVader336  commented on May 13, 2018, 7: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?

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

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