Timed K-Bomb (APCS 2016-10 Advanced)

Points 100 1.0s 256M

In the game "Timed \(K\)-Bomb," \(N\) players numbered from \(1\) to \(N\) stand in a circle. Starting with player \(1\), they pass a toy bomb in order. Whenever the bomb reaches the \(M\)-th counted player, it explodes and that player leaves the circle. Counting then continues from the eliminated player's next remaining neighbor.

The bomb explodes exactly \(K\) times. After the \(K\)-th explosion, the player immediately following the last eliminated player is called the lucky player.

For example, when \(N=5\) and \(M=2\):

  • If \(K=2\), players \(2\) and \(4\) are eliminated, so player \(5\) is lucky.
  • If \(K=3\), player \(1\) is eliminated next, so player \(3\) is lucky.
  • If \(K=4\), player \(5\) is eliminated next, and player \(3\) is still lucky.

Elimination process for N=5 and M=2

Given \(N\), \(M\), and \(K\), determine the number of the lucky player.

Input Format

The input contains one line with three space-separated positive integers \(N\), \(M\), and \(K\).

Output Format

Output one integer: the number of the lucky player.

Constraints

  • \(1 \le N \le 200000\)
  • \(1 \le M \le 1000000\)
  • \(1 \le K < N\)
  • The time limit is 1 second per test case.
  • The memory limit is 256 MB.
Subtasks
Subtask Points Additional constraints
1 20 \(N \le 100\), \(M \le 10\), and \(K=N-1\)
2 30 \(N \le 10000\) and \(K=N-1\)
3 20 \(K=N-1\)
4 30 No additional constraints

The official evaluation contains 20 scored test cases, each worth 5 points.

Sample Input 1

5 2 4

Sample Output 1

3

Sample Input 2

8 3 6

Sample Output 2

4

Source

APCS October 2016 Programming Problem 3, "Timed K-Bomb," also available as ZeroJudge c296.

Problem page help

Keyboard shortcuts

Main features

  • Sample tests — Runs the sample cases bundled with the problem and auto-compares against the expected output.
  • Custom test — Run your code with your own stdin. Optionally tick the "Compare with expected (diff)" box to verify against expected output line-by-line.
  • Template — Paste the default code template you set on your profile page.
  • Collab — Edit this problem together with classmates in real time.
  • Auto-draft — Editor contents auto-save to your browser every 1.5 seconds (per account / problem / language).
  • Submit — Send your code to the judge for grading; returns AC / WA / TLE etc.

Limits

  • Source code: at most 65,536 characters
  • Custom test stdin and expected output: at most 1 MB each (≈1 million characters)
  • Custom test and sample test share the sandbox; about 1 request per 3 s per user (sample test: 1 per 1 s)
  • Custom test and sample test both have a 15 second wall-clock cap (the official judge still uses the problem time limit)
  • Interactive problems do not offer custom test (cannot simulate interaction with the judge).
  • Submitting has no rate limit, but rapid repeated submissions on the same problem are treated as score farming.