A Sum Problem

View as PDF

Submit solution

Points: 12 (partial)
Time limit: 10.0s
Memory limit: 18M

Author:
Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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 N (1 \leq N \leq 5 \cdot 10^4) integers (0 \leq a_i \leq 10^7), 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 k?" Because he is impatient, Max says you can only ask up to 5 \cdot 10^5 questions.

Subtasks

Subtask 1 (15%)

0 \leq a_i \leq 10^5

Subtask 2 (15%)

1 \leq N \leq 10^4

Subtask 3 (70%)

No further constraints.

Interaction

The first line of input will be N, 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 x 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 the incorrect answer. In both cases you will receive a WA verdict.

Sample Interaction

>>> denotes your output. Do not print >>> out.

4
>>> ? 1
4
>>> ? 2
3
>>> ? 3
2
>>> ? 4
1
>>> ! 10

Sample Explanation

The array was [1, 2, 3, 4], and its sum is 10.


Comments


  • 4
    c  commented on Dec. 24, 2019, 9:51 p.m.

    The interactor has been fixed and all submissions in the past 17 hours have been rejudged.

    Sorry for the inconvenience.