COI '09 #2 Kolo

View as PDF

Submit solution

Points: 20 (partial)
Time limit: 0.6s
Memory limit: 32M

Problem type

During meetings of young mathematicians a frequent pastime is the Prime Number Circle. For this task, we refer to mathematicians in the circle with numbers 1 to N.

Before the game starts we first draw N-1 circles and one square on the pavement arranged in a big circle. The player numbered 1 stands in the square. All other players stand in the circles, starting with the player 2 in a counterclockwise fashion facing towards the middle of the big circle.

The game consists of K rounds. In the i-th round the person standing in the square jumps up, says "It's me!" and then swaps places with the person standing on his right side p_k times, where p_k is the k-th prime. For example for N = 5 and K = 3 the following three rounds occur:

Write a program that will for given N, K and A determine the neighbours of the player numbered A at the end of the game.

Input Specification

The first and only line contains three integers N, K and A. (1 \le A \le N), the number of players, rounds and the selected player.


Test data is divided into four groups each worth 25 points, with the following constraints:

First group: (3 \le N \le 1\,000, 1 \le K \le 1\,000).

Second group: (3 \le N \le 1\,000, 1 \le K \le 50\,000).

Third group: (3 \le N \le 50\,000, 1 \le K \le 50\,000).

Fourth group: (3 \le N \le 5\,000\,000, 1 \le K \le 500\,000).

Output Specification

The first and only line of output should contain two integers, the numbers on the right and left neighbours of the player numbered A at the end of the game.

Sample Input 1

5 3 1

Sample Output 1

3 5

Sample Input 2

5 3 2

Sample Output 2

5 4

Sample Input 3

5 4 5

Sample Output 3

3 2


There are no comments at the moment.