Solução Número de Fora, por Pedro Racchetti
Conhecimentos utilizados:
- Representação binária de números
- Set
Para esse problema, analise primeiro o primeiro bit. Como existem 
números, de um intervalo de 
a , podemos ver que, como 
dos números do intervalo são ímpares, se menos que essa quantidade de número da lista for ímpar, sabemos que o número de fora é impar, caso contrário ele é par. Podemos agora eliminar todos os índices com paridade contrária ao número de fora, dividindo o tamanho da lista por 
Perceba que um número é par se e somente se o -ésimo bit dele for . Perceba que o que foi dito acima também se aplica para todos os bits, podendo então se aplicar a ideia para o bit 
de todos os números que não foram eliminados, dividindo o tamanho da lista possível de números de fora por . Fazendo isso sucessivamente, eventualmente chegaremos a resposta, já que saberemos todos os bits do número. Isso irá nos custar no máximo 
perguntas já que 
é igual a 
, cujo limite é 2*n.
Para isso, podemos guardar um set com todos os índices que ainda não foram eliminados, e para cada bit, fazer uma pergunta sobre todos os índices no set, guardar em um outro set com os índices que tem o bit atual ativo. Se o tamanho desse set for menor que 
, o set global passa a conter somente os elementos do set local, caso contrário são removidos do set global todos os elementos do set local.
Segue o código comentado, para melhor compreensão:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <bits/stdc++.h> | |
| using namespace std; | |
| int n; | |
| set<int> global; | |
| int main() { | |
| cin >> n; | |
| for(int i = 1; i <= n; i++) global.insert(i); //inserimos todos os indices de 1 à n no set global | |
| set<int>::iterator it; | |
| int pergunta = 0, resp = 0; // resp será o numero de fora | |
| for(int i = 0; global.size() > 0; i++){ // enquanto ainda existir algum elemento do set, passaremos pelo i-ésimo bit | |
| set<int> local; | |
| for(it = global.begin(); it!=global.end(); it++){ | |
| int numeroatual = *it; | |
| cout << "? " << numeroatual << " "<< i << endl; | |
| cout.flush(); | |
| cin >> pergunta; // verificamos se o indice atual tem o i-ésimo bit ativo | |
| if(pergunta) local.insert(numeroatual); // inserimos no set local todos os indíces | |
| // com o i-ésimo bit ativo em seu respectivo número | |
| } | |
| int mid = (global.size() + 1)/2; | |
| // caso existam menos que o (tamanho do set global + 1)/2 números com o i-ésimo | |
| // bit ativo, com certeza o número de fora tem o i-ésimo bit ativo | |
| if(local.size() < mid){ | |
| resp += (1<<i); | |
| global = local; | |
| } | |
| // caso contrário, temos que retirar todos os indíces | |
| // com o i-ésimo bit ativo em seu respectivo número do set global | |
| else{ | |
| for(it = local.begin(); it!=local.end(); it++){ | |
| int esse = *it; | |
| global.erase(esse); | |
| } | |
| } | |
| } | |
| cout << "! " << resp << endl; // imprimimos a resposta | |
| cout.flush(); | |
| } |