Submit solution

Points: 7 (partial)
Time limit: 3.0s
Memory limit: 64M

Author:
Problem types

Inaho is given an array k of length N, such that k_i is a unique integer. With the array, he defines a function:

\displaystyle f(x) = \sum_{i=1}^N \sin(2^{k_i} x)

Inaho wants to play a game with you! He wants you to recreate the array. Because he knows this is impossible, he will allow you to ask him some questions. In particular, you are to ask him x, where 0 \le x \le \pi, and he will reply with f(x). He wants this to be challenging. As such, he will only allow you to ask him Q questions.

Tell Inaho what his array k is!

Input Specification

Inaho will provide you the integer N on the first line.

Interaction

You may then ask questions. To ask a question, you must use the form Q x. Note that x is in radians and must be in the range [0, \pi]. x may contain as many decimal places as you desire, however, x will be rounded to 20 decimal places. Inaho's response is guaranteed to be precise to 15 decimal places.

To tell Inaho the array k, you must use the form A p. p is an integer, such that the j^{th} bit in p is 1 if there exists a k_i = j, and 0 otherwise. Because k_i is guaranteed to be unique, this means the number of 1 bits in p should be equal to N.

For example, if N=3, and k = [0,3,2], then p = 13.

You are allowed to ask Inaho a maximum of Q questions. Note that telling Inaho the array k does not count as a question.

After each question or the answer, you may need to flush stdout. You do not need to flush if you are using C++, Java, or Python 2/3. In other languages, such as Pascal, you will need to flush stdout for the interactor to receive your output.

Note 1: Up to 0.5 seconds of the time limit could be used up by the interactor.

Output Specification

To tell Inaho the array k, use the form A p, where p is the integer as defined in the Interaction section.

Constraints

  • 1 \le N \le 20
  • 0 \le k_i \le 22

Subtasks

Subtask 1 [10%]

Q = N^2

Subtask 2 [30%]

Q = N

Subtask 3 [60%]

Q = \min(2,N)

Note that these are not explicit subtasks. You will receive the specified percentage of points depending on which subtask you fall in. For example, using 10 questions for N = 20 will grant you 40\% of the points.

Sample Interaction

>>> denotes your output; don't actually print this out.

N = 3, k = [0,3,2]

3
>>> Q 0.000000000000
0.000000000000000
>>> Q 3.01
-1.239969287666227
>>> A 13

Comments


  • -1
    Zeyu  commented on Jan. 13, 2019, 10:45 p.m.

    Stuck from getting IR with python 2/3 but I can't seem to reproduce the issue on multiple different environments, can someone help guide me in the right direction?


    • 0
      Kirito  commented on Jan. 13, 2019, 11:51 p.m.

      Do you flush your output?


      • 1
        Zeyu  commented on Jan. 14, 2019, 12:58 a.m. edited

        Same IR response after flushing for every interaction unfortunately, that didn't seem to be the case.

        EDIT: Apparently flushing before an interaction is also needed? That seemed to cure the IR response.