At school, Max is learning how to add numbers together! He finds the task of adding numbers too easy, so he gives you the following problem: sum an array of () integers (), without looking at the array. Instead, you're only allowed to ask the following question: "How many numbers in the array are greater than or equal to ?" Because he is impatient, Max says you can only ask up to questions.
Subtask 1 [15%]
Subtask 2 [15%]
Subtask 3 [70%]
No additional constraints.
The first line of input will be , the number of items in the array.
To ask questions, output
? k, followed by a newline. The next line of input will be the answer to your question.
To submit your answer, output
! x (followed by a newline), where is the sum of all the numbers.
If your output is ever invalid, undefined behavior will be invoked.
Please note that the grader for this problem does not differentiate between asking too many queries or giving an incorrect answer. In both cases, you will receive a
>>> denotes your output. Do not print
4 >>> ? 1 4 >>> ? 2 3 >>> ? 3 2 >>> ? 4 1 >>> ! 10
The array was , and its sum is .