Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Interactive GCD

By curly_braces · Limits 2s, 256 MB · Interactive

This is an interactive problem.

Alice and bob are playing a game of Interactive GCD.

The game engine has a secret array of length $n$ consisting of integers in range $[1,100]$. The players take turn alternatively. In each turn, a player chooses a subsequence of index from the array which is not chosen before. If the GCD (Greatest Common Divisor) of elements in that subsequence is $1$, then the player gets a point, otherwise he/she gets no point. The game ends when there are no subsequences left to be chosen. So, it can be shown that the game will run for $2^n - 1$ turns. At the end, whoever has higher points wins. If both of them has equal points, then it’s a draw.

As Alice and Bob are best friends, no one wants to defeat the other one and make him/her sad. They will play the game if and only if there is a chance that they will draw. Formally, they will only play if the probability that the game will end in a draw is nonzero.

As mathematicians, both believe in probability. Before playing the game, they want the engine to be inspected. They have given you the responsibility to inspect the engine and tell them whether they should play or not. To inspect the engine, you ask some questions about the secret array to the owner. The owner is smart. It will not reveal the array, rather you will give it an integer, and it will reply with how many elements in the array is divisible by that integer.

For example, if the array is $[2,3,4,5,6]$ and your query is $2$, the owner will reply with $3$.

You can ask at most $2^6$ queries (excluding printing Start and printing the result). Can you tell if they should play the game or not?

Input

Interaction Details:

Problem starts with reading an integer $T(0 < T \leq 100 )$, number of testcases.

Print “Start” and flush the output to start interaction for that testcase,

Read an integer $n(1 \leq n \leq 500)$, the length of the array.

Then for at most $2^6$ queries, print an integer in range $[1,100]$.

Read an integer (the response of the owner).

When you are sure about the inspection, print a string “Yes” or “No”.

After printing your inspection, read a string containing “Correct” if your inspection is correct and “Incorrect” otherwise.

If you get any “Incorrect” verdict, make sure to terminate the program, otherwise you may get Undetermined verdict or Time Limit Exceeded or Run Time Error instead of Wrong Answer.

After that, move on to the next testcase by printing “Start”.

After processing the final testcase, make sure to terminate the program.

Print every query in a new line and don’t forget to flush the output stream after every query.

You may use: - fflush(stdout) in C/C++ - stdout.flush() in Python to flush the output.

Subtask Constraints

Subtask 1 (5% of points)

$n = 1$
All values in the secret array are in the range $[1,10]$

Subtask 2 (15% of points)

$n \leq 2$
All values in the secret array are in the range $[1,10]$

Subtask 3 (50% of points)

$n \leq 20$
All values in the secret array are in the range $[1,32]$

Subtask 4 (100% of points)

Original constraints

Output

A sample interaction is given below if the secret array was $[2,4,2,3,1]$.

> 1

< Start

> 5

< 1

> 5

< 2

> 3

< 3

> 2

< 4

> 1

< Yes

> Incorrect

Here’ >’ indicates what your program reads and ‘<’ indicates what your program writes. These symbols are here to make it easy to understand. You do not have to print such symbols from your program.

Another sample interaction if the secret array was [2,5,4,3]

> 1

< Start

> 4

< 1

> 4

< 2

> 2

< 3

> 1

< 4

> 1

< 5

> 1

< Yes

> Correct

    Discussion

    Statistics


    67% Solution Ratio

    DibyaJyotiEarliest, 3w ago

    YouKnowWhoFastest, 0.0s

    YouKnowWhoLightest, 188 kB

    YouKnowWhoShortest, 921B

    Submit

    Login to submit

    Editorial

    If number of subsequences with GCD 1 is odd, then the game will never end in a draw. So we have to c...