Eggs

You are given one N-story building and K identical eggs. There is a number X, such that any egg dropped from a floor lower than X will survive the fall, while any egg dropped from a floor higher than or equal to X will break.

Your task is to find the value of X. You can only make one attempt at guessing the answer. Your solution will be verified by a simulator. The two programs interact as follows:

First, the simulator will print the integers N and K separated by a space. Then, your program can print commands of the form query P and answer X.

If your program prints query P, the simulator will drop one egg from the P-th floor, and will print one of the following results:

survived
The egg has survived the fall
broke
The egg has broken
error
All K eggs are broken. Your program will be rejected.

If your program prints answer X, the simulator will check your anser, print exit and terminate. If both of the following conditions are true, your program will be accepted.

  • X must be correct
  • The number of egg drops must not exceed (the official solution's number of egg drops + 4)
Note: After each command you should print a newline character and flush the output (using functions such as fflush(stdout) or cout.flush())

Constraints

  • 1 <= N <= 1000
  • 1 <= K <= 10

Example code (C++)

    1 int n, k;
    2 cin>>n>>k; //read the number of stories and eggs
    3 
    4 string response;
    5 while(response != "exit") {
    6     cout << "query " << x << "\n"; //can also use endl for newline
    7     cout.flush();
    8 
    9     cin >> response;
   10     if(response == "broke") k--;
   11 
   12     if(!sureAboutAnswer) { //perhaps you need more information
   13         cout << "query " << x << "\n";
   14         cout.flush();
   15 
   16         cin >> response;
   17         if(response == "broke") k--;
   18     }
   19     else { //in case you've found the answer
   20         cout << "answer " << x << "\n";
   21         cout.flush();
   22         cin >> response; //the response is going to be "exit"
   23     }
   24 }

Example interaction

User programSimulator
10 5
query 9
broke
query 6
survived
query 8
broke
query 7
survived
answer 8
exit
Questions?

Sponsors Gold