2001 Canadian Computing Competition, Stage 2
Day 2, Problem 1: Breaking Level
You are playing a game with your friends up in a tall tower with N levels labelled 1 to N (1 ≤ N ≤ 100). You are given an object which is somewhat fragile, and you are warned that the object will break if you drop it from the "breaking level" or higher. That is, for the given object, there is a unique level H (1 ≤ H ≤ N) such that if the object is dropped from level H-1 or lower, it will not break, and if it is dropped from level H or higher, it will break. Your job is to determine the breaking level by dropping samples of the object from various levels of the building and observing the results.
Your friends have made the challenge a bit harder. You are given only two samples of the object. Once these have broken, there are no more objects to drop. There is one more restriction: you are given only a certain number, D, of opportunities to drop the object (D is much less than N). If you successfully determine the breaking level (the unique H defined above) before you run out of drop opportunities and using no more than the 2 samples of the object, you win the game and the unending respect and cash of your friends.
Input
Your program will read the values of N and D from standard input, on a single line and separated by a space.Interaction
Your program will repeatedly interact with the judge as follows: if you wish to drop an object, simply print the level from which you wish to drop it, on a single line, to standard output. The judge will then print the result of the query (1 if it breaks, 0 if it does not) on a single line, which should be read by your program. (If your program attempts to print any more output before reading in the result of a query, it will probably result in a block and subsequent TLE.) When you are ready to report the breaking level, print the value you have determined followed by a period.Sample Interaction
Here is an example of how your program might proceed. (Lines starting with "> " are read by your program, and lines starting with "< " are written by your program. These characters do not appear in the actual interaction.)> 5 3 < 3 > 1 < 1 > 0 < 2 > 1 < 1.
Explanation
Your program reads 5 and 3; the tower has five levels and you are given up to three drop opportunities. First, you drop the object from the third level; it breaks. Then, you drop it from the first level, and it does not break. Finally, you drop it from the second level, and it breaks. You conclude that the breaking level is 2.
All Submissions
Best Solutions
Point Value: 20
Time Limit: 2.00s
Memory Limit: 16M
Added: Aug 13, 2013
Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3
Comments (Search)