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$$ números, de um intervalo de $$0$$ a $$n$$, podemos ver que, como $$floor((n + 1)/2)$$ 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 $$2$$
Perceba que um número é par se e somente se o $$0$$-ésimo bit dele for $$0$$. 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 $$1$$ de todos os números que não foram eliminados, dividindo o tamanho da lista possível de números de fora por $$2$$. Fazendo isso sucessivamente, eventualmente chegaremos a resposta, já que saberemos todos os bits do número. Isso irá nos custar no máximo $$2 \cdotp n$$ perguntas já que $$n + n/2 + (n/2)/2 + ((n/2)/2)/2 … $$ é igual a $$n + n/2 + n/4+ n/8…$$, 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 $$(tamanno do set global + 1)/2$$, 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:
| #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(); | |
| } |
