codeforces 1011D. Rocket(인터랙티브 + 2점)

D. Rocket
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
This is an interactive problem.
Natasha is going to fly to Mars. Finally, Natasha sat in the rocket. She flies, flies... but gets bored. She wishes to arrive to Mars already! So she decides to find something to occupy herself. She couldn't think of anything better to do than to calculate the distance to the red planet.
Let's define xx as the distance to Mars. Unfortunately, Natasha does not know xx. But it is known that 1≤x≤m1≤x≤m, where Natasha knows the number mm. Besides, xx and mm are positive integers.
Natasha can ask the rocket questions. Every question is an integer yy (1≤y≤m1≤y≤m). The correct answer to the question is −1−1, if xyx>y. But the rocket is broken — it does not always answer correctly. Precisely: let the correct answer to the current question be equal to tt, then, if the rocket answers this question correctly, then it will answer tt, otherwise it will answer −t−t.
In addition, the rocket has a sequence pp of length nn. Each element of the sequence is either 00 or 11. The rocket processes this sequence in the cyclic order, that is 11-st element, 22-nd, 33-rd, ……, (n−1)(n−1)-th, nn-th, 11-st, 22-nd, 33-rd, ……, (n−1)(n−1)-th, nn-th, ……. If the current element is 11, the rocket answers correctly, if 00 — lies. Natasha doesn't know the sequence pp, but she knows its length — nn.
You can ask the rocket no more than 6060 questions.
Help Natasha find the distance to Mars. Assume, that the distance to Mars does not change while Natasha is asking questions.
Your solution will not be accepted, if it does not receive an answer 00 from the rocket (even if the distance to Mars is uniquely determined by the already received rocket's answers).
Input
The first line contains two integers mm and nn (1≤m≤1091≤m≤109, 1≤n≤301≤n≤30) — the maximum distance to Mars and the number of elements in the sequence pp.
Interaction
You can ask the rocket no more than 6060 questions.
To ask a question, print a number yy (1≤y≤m1≤y≤m) and an end-of-line character, then do the operation flush and read the answer to the question.
If the program reads 00, then the distance is correct and you must immediately terminate the program (for example, by calling exit(0)). If you ignore this, you can get any verdict, since your program will continue to read from the closed input stream.
If at some point your program reads −2−2 as an answer, it must immediately end (for example, by calling exit(0)). You will receive the "Wrong answer"verdict, and this will mean that the request is incorrect or the number of requests exceeds 6060. If you ignore this, you can get any verdict, since your program will continue to read from the closed input stream.
If your program's request is not a valid integer between −231−231 and 231−1231−1 (inclusive) without leading zeros, then you can get any verdict.
You can get "Idleness limit exceeded"if you don't print anything or if you forget to flush the output.
To flush the output buffer you can use (after printing a query and end-of-line):

fflush(stdout) in C++;

System.out.flush() in Java;

stdout.flush() in Python;

flush(output) in Pascal;

See the documentation for other languages.

Hacking
Use the following format for hacking:
In the first line, print 33 integers m,n,xm,n,x (1≤x≤m≤1091≤x≤m≤109, 1≤n≤301≤n≤30) — the maximum distance to Mars, the number of elements in the sequence pp and the current distance to Mars.
In the second line, enter nn numbers, each of which is equal to 00 or 11 — sequence pp.
The hacked solution will not have access to the number xx and sequence pp.
Example
input
Copy

5 2
1
-1
-1
1
0

output
Copy

1
2
4
5
3

Note
In the example, hacking would look like this:
5 2 3
1 0
This means that the current distance to Mars is equal to 33, Natasha knows that it does not exceed 55, and the rocket answers in order: correctly, incorrectly, correctly, incorrectly ...
Really:
on the first query (11) the correct answer is 11, the rocket answered correctly: 11;
on the second query (22) the correct answer is 11, the rocket answered incorrectly: −1−1;
on the third query (44) the correct answer is −1−1, the rocket answered correctly: −1−1;
on the fourth query (55) the correct answer is −1−1, the rocket answered incorrectly: 11;
on the fifth query (33) the correct and incorrect answer is 00.
 
 
1. 원제 주소
점아 전송
 
대체로
지금 추측할 숫자가 하나 있습니다.처음에 m, n을 줬어요.추측할 숫자의 크기는 최대 m일 수 있다.그리고 너는 매번 숫자를 기계에 출력해서 기계가 네가 제시한 숫자가 큰지 작은지 대답하도록 해라.그러나 기계는 너를 속인다. 즉, 때때로 그는 고의로 거꾸로 말한다.그러나 기계의 사기는 주기적이다. 즉, 그는 i차 대답과 i+T차 대답이 모두 정확하거나 사기라는 것을 보장하기 위해 T가 존재한다.이 주기는 n이다.
네가 제시한 기계를 너무 세면 -1이 돌아온다.
네가 제시한 것을 세면 작은 기계가 1로 돌아간다
네가 제시한 숫자가 답일 때 0이 돌아간다.
 
3. 사고방식
먼저 한 조가 모두 1인 질문으로 기계의 사기 서열을 얻어 주기 내 기계의 정확성을 얻는다.그 다음은 일반적인 2분 조작이다.제목에 제시된 힌트는 시간을 초과하지 않도록 fflush(stdout)를 사용해야 합니다.
 
4. 코드

#include 
#include 
#include 
#include