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:
ENTRADA |
SAÍDA |
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