2007 Canadian Computing Competition, Stage 2

Day 2, Problem 2: Particle Catcher

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:

GetSize() - this method 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, ..., N-1. You may assume 2 ≤ N ≤ 100,000.

Look(a, b) - returns true if the point is in the range from a..b (where 0 ≤ a ≤ b ≤ N-1) at this moment and false otherwise. This method 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 to this method will query the initial position of the point (i.e., the GetSize() method does not advance the point).

Guess(v, p) - will record the final velocity v and final position p (where 0 ≤ v, p ≤ N-1). There is exactly one call to this method, which will terminate the high-tech measuring device (i.e., no other calls may be made) and the high-tech device will output a statement indicating the success or failure of the guess (whether the point is at position p and velocity v when the call to Guess is made.) Note that the particle is v units away from where it was at the last query statement.

You have a limit of 100 Looks, so be wise about your queries.

Interacting with the Judge

The methods mentioned above can be accessed through regular input/output.

1. The first line of input to your program will be N. (GetSize())
2. After that, you'll have to Look. To Look(a, b), just output a and b separated by a space on one line.
3. To get the result of your look, read an integer. You will receive 1 (true) or 0 (false) accordingly.
4. Repeat steps 2-3 as desired.
5. To make your final Guess, output "G v p" on one line where v and p are your guesses for the velocity/position.

You'll also need to fflush(NULL) [C++] or flush(output) [Pascal] whenever you output something.

Sample Code

#include <iostream>
using namespace std;

int main()
{
	int N;
	scanf("%d", &N);
	
	//look around
	printf("%d %d\n", 0, N-1);
	fflush(NULL);
	int result;
	scanf("%d", &result); //result of the look

	int v = 1, p = 2;	
	printf("G %d %d\n", v, p); //final guess
	fflush(NULL);
	
	return 0;
}

All Submissions
Best Solutions

Point Value: 40 (partial)
Time Limit: 2.00s
Memory Limit: 128M
Added: Jan 17, 2009

Languages Allowed:

Comments (Search)

Why has been 'Languages Allowed' NULL ?? We can't submit our solutions . Please fix it ASAP :)

there was a comment five days ago that the "You can get AC by outputting nothing" issue was not fixed yet. since there is no reply, i think we can safely assume that the admins have turned off the submissions until they can fix it :)

Hopefully we can get that fixed soon. In the meantime, if you submit something like that, I'll delete it. And maybe ban you.

**Update:** It's still not fixed. Please don't ban me.

The judge accepts my answer although RE (I tried an O(N^2) space solution, so it's clear the program should not solve the hard test-cases). How can I cancel my submission (#280157)? I don't want to get points for a wrong solution.

Please output the initial position instead of the final position.