Canadian Computing Competition: 2007 Stage 2, Day 2, Problem 2

You may have heard that you cannot observe both the speed and location of a subatomic particle, simultaneously. At least, not until today, since computer scientists can ignore physicists whenever we want.

Your task is to determine both the speed and location of a particle that is moving around a nucleus. Of course, we will assume that the particle is moving in a circular orbit and moving at a constant velocity.

You can use your high-tech measuring device (which is, in fact, the synthesis of a spoon and a Commodore-64) to perform the following 3 different queries at most ~100\,000~ times (depending on the I/O speed):

• GetSize – this returns the integer representing the number of different positions in one orbit of the particle. You may assume that if this function returns ~N~, the positions are labelled ~0, \dots, N-1~. You may assume ~2 \le N \le 100\,000~.
• Look a b – returns true if the point is in the range from ~a \dots b~ (where ~0 \le a \le b \le N-1~) at this moment and false otherwise. This will be called repeatedly, but subsequent calls cause the particle to move ~v~ positions from its current position. In other words, the particle is moving at ~v~ units per query. The first call will query the initial position of the point (i.e., the GetSize call does not advance the point).
• Guess v p – will record the final velocity ~v~ and final position ~p~ (where ~0 \le v, p \le N-1~). There is exactly one call, which will terminate the high-tech measuring device (i.e., no other calls may be made). Note that the particle is ~v~ units away from where it was at the last query statement.

Sample Interaction

>>> denotes your output; don't actually print this out.

>>> GetSize
4
>>> Look 0 3
True
>>> Look 3 3
False
>>> Guess 1 2