Guess the Array
시간 제한2초메모리 제한512 MB
Bob은 n번 이하의 구간 합 질의로 n개 정수 배열을 알아내야 하는데, 질의할 때마다 Alice가 한 구간을 막아 이후 그 구간은 다시 물을 수 없다.
문제
This is an interactive problem. Your program will interact with the jury program using standard input and output.
Alice and Bob have decided to play a game called "Guess the Array". The rules of the game are very simple: Alice has an array of integers, and Bob has to guess this array by making no more than queries about the sums on the segments.
In one move Bob can make one of two types of queries to Alice:
- "
? l r" to find out the sum of numbers on the segment of the array from the -th to the -th element inclusive; - "
!" to tell Alice that he is ready to give the answer. After this query Alice expects integers from Bob: the initial array.
For each first type query, Alice tells Bob the sum of the numbers in the requested segment. But to make it harder to guess, after each query Alice makes one segment blocked. In further queries, Bob cannot ask for the sum of the numbers on the blocked segments.
Help Bob guess Alice's array by making no more than first type queries.