Editorial for COI '09 #2 Kolo

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

We use the sieve of Eratosthenes to find the first $K$ $K$ prime numbers.

Now we mark the square with $0$ $0$ and circles with numbers $1$ $1$ to $N-1$ $N - 1$ . Since it would be impossible to simulate the entire game within the time limit, we first determine an algorithm that will help us find $A$ $A$ 's final position. Let's assume that currently $A$ $A$ is on position $x$ $x$ and the current prime is $p$ $p$ :

If $x = 0$ $x = 0$ , then $A$ $A$ is in the square so $x$ $x$ becomes $N \bmod p$ $N mod p$ .
Else, if $x \ne 0$ $x \neq 0$ , then we can determine how many times the person in the square changes place with $x$ $x$ :
- If $x \le p \bmod (N-1)$ $x \leq p mod (N - 1)$ then $x$ $x$ becomes $(x-1) \bmod N$ $(x - 1) mod N$
- Else $x$ $x$ becomes $(x - p \mathbin{\text{div}} (N-1)) \bmod N$ $(x - p div (N - 1)) mod N$

Where $\bmod$ $mod$ is the modulus operator and $\text{div}$ $div$ is integer division. Now we need to solve the other way so that we may answer the question "If $A$ $A$ is on $X$ $X$ then who is on $X-1$ $X - 1$ (or $X+1$ $X + 1$ )?"

Let's assume that we know position $x$ $x$ after the prime $p$ $p$ was played.

If $x = p \bmod N$ $x = p mod N$ , then $x$ $x$ was at $0$ $0$ before prime $p$ $p$ .
Else, if $x \ne p \bmod N$ $x \neq p mod N$ :
- $x$ $x$ becomes $(x + p \mathbin{\text{div}} (N-1)) \bmod N$ $(x + p div (N - 1)) mod N$
- If $x \le p \bmod (N-1)$ $x \leq p mod (N - 1)$ then $x$ $x$ becomes $(x+1) \bmod N$ $(x + 1) mod N$

The time complexity is $\mathcal O(K)$ $O (K)$ .

Comments

There are no comments at the moment.