Inaho X

View as PDF

Submit solution

All submissions

Best submissions

Points: 7 (partial)

Time limit: 3.0s

Memory limit: 64M

Author:

Ninjaclasher

Problem types

Inaho is given an array $k$ $k$ of length $N$ $N$ , such that $k_i$ $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)$ $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$ $x$ , where $0 \le x \le \pi$ $0 \leq x \leq π$ , and he will reply with $f(x)$ $f (x)$ . He wants this to be challenging. As such, he will only allow you to ask him $Q$ $Q$ questions.

Tell Inaho what his array $k$ $k$ is!

Input Specification

Inaho will provide you the integer $N$ $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$ $x$ is in radians and must be in the range $[0, \pi]$ $[0, π]$ . $x$ $x$ may contain as many decimal places as you desire, however, $x$ $x$ will be rounded to $20$ $20$ decimal places. Inaho's response is guaranteed to be precise to $15$ $15$ decimal places.

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

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

You are allowed to ask Inaho a maximum of $Q$ $Q$ questions. Note that telling Inaho the array $k$ $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$ $0.5$ seconds of the time limit could be used up by the interactor.

Output Specification

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

Constraints

$1 \le N \le 20$ $1 \leq N \leq 20$
$0 \le k_i \le 22$ $0 \leq k_{i} \leq 22$

Subtasks

Subtask 1 [10%]

$Q = N^2$ $Q = N^{2}$

Subtask 2 [30%]

$Q = N$ $Q = N$

Subtask 3 [60%]

$Q = \min(2,N)$ $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$ $10$ questions for $N = 20$ $N = 20$ will grant you $40\%$ $40 %$ of the points.

Sample Interaction

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

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

Copy

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.