Informática - Nível Intermediário - Semana 7

Número de Fora

Existe uma lista de números $a_1, a_2, ... a_n$, tal que todos os elementos dessa lista pertencem ao intervalo $[0, n]$. Como você pode ver, um dos números desse intervalo está faltando.

Você deve encontrar esse. Para isso, pode-se perguntar o estado do $b$-ésimo bit do número $a_i$. O número máximo de perguntas é $2$ $\cdotp n + 19$

Interação:

Esse é um problema interativo. Seu programa irá se comunicar com o juiz, usando o dispositivo padrão de entrada e saída.

Primeiro, seu programa lerá um inteiro $n$ - o tamanho da lista

Depois disso, seu programa poderá fazer no máximo $2$ $\cdotp n + 19$ perguntas. Para fazer uma pergunta, imprima um caractere $?$ e então dois inteiros $i$ e $b$, o índice na lista do número a ser perguntado e o bit a ser perguntado. Note que os bits começam contar a partir de $0$

O juiz então imprimira um inteiro $0$ ou $1$ - o valor do $b$-ésimo bit do número $a_i$

Quando determinar o número de fora, imprima um caractere ! e o número em si. Termine então o seu programa.

Restrições

• $1 \leq n \leq 1000$
• $1 \leq i \leq n$
• $0 \leq b \leq log_2 n$

Exemplo de interação:

3
0
1
0

? 1 1
? 2 0
? 3 1
! 2

Nota:

Cada mensagem que seu programa imprimir deve terminar com uma quebra de linha. Além disso, seu programa deve limpar o buffer, para o juiz ler a informação que foi impressa. Isso pode ser feito ao chamar $fflush(stdout)$ ou $cout.flush()$ em C++, $System.out.flush()$ em Java, $Console.Out.Flush()$ em C#, $flush(output)$ em pascal, ou $sys.stdout.flush()$ em Python.

Para testar sua solução, clique aqui