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)
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 program | Simulator |
---|---|
10 5 | |
query 9 | |
broke | |
query 6 | |
survived | |
query 8 | |
broke | |
query 7 | |
survived | |
answer 8 | |
exit |