Distinct Numbers

curly_braces CUET CSE Fest 2022 - Inte...
Limits 1s, 512 MB · Interactive

This is an Interactive Problem.

The judge has a secret array AA of size nn.

You can ask the judge at most 10n10*n queries, and after that, you have to figure out the number of distinct elements in the array.

Query: To do a query you will give the judge two integers i,j(1i,jn)i, j(1 \leq i, j \leq n), the judge will reply with a character indicating the relation of the elements AiA_i and AjA_j. There can be 3 types of responses,

  1. < , if Ai<AjA_i<A_j

  2. > , if Ai>AjA_i > A_j

  3. = , if Ai=AjA_i = A_j

Input

Interaction Details:

The interaction starts with reading an integer n(1n1000)n(1 \leq n \leq 1000), the size of the secret array.

After that to do a query print “? i j” in a line and flush the output stream.

Read a character in a line, the response from the judge.

When you are ready to answer, print “! x” in a line. Here x is the number of distinct elements in AA. [Note: This does not count as one of the queries.]

After that flush the output stream and finish!

To flush the output stream, you may use:

  • fflush(stdout) in C/C++

  • stdout.flush() in Python

Output

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

>> 4

<< ? 1 4

>> <

<< ? 1 3

>> =

<< ! 3

Another one if the secret array was [1, 1, 1, 2, 1, 1]

>> 6

<< ? 1 2

>> =

<< ? 3 4

>> <

<< ? 5 6

>> =

<< ! 2

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.

Submit

Login to submit.

Statistics

89% Solution Ratio
RakibJoyEarliest, 1M ago
tanzim_bnFastest, 0.0s
Hamim_Lightest, 5.6 MB
tanzim_bnShortest, 768B
Toph uses cookies. By continuing you agree to our Cookie Policy.