Solução Informática - Nível Avançado - Semana 43

Solução escrita por João Pedro

Conhecimento prévio necessário:

• Operações binárias em números

Chame de $n(x)$ a quantidade de bits ativos na representação binária de $x$. Agora, perceba que se $a \oplus b = c$, $n(a) + n(b) \equiv n(c)~(mod~2)$. Já que para cada bit ativo em $c$ temos somente 1 bit ativo no total, e para cada bit desativado temos ou 2 ou 0 bits ativos no total. Logo, como é $(mod~2)$ podemos desconsiderar os bits desativados de $c$, já que somam 2 ou 0 pra $n(a) + n(b)$. Como temos exatamente $n(c)$ bits ativos, chegamos a conclusão que $n(a) + n(b) \equiv n(c)~(mod~2)$.

Também perceba que o único caso onde o jogo está perdido para o jogador que vai escolher entre $p_1$ e $p_2$ para quebrar é quando $n(p_1) = n(p_2) = 1$. Já que é impossível dividir um número $p$ de 1 bit ativo em $p_1$ e $p_2$ seguindo as condições que $p_1 \oplus p_2 = p$ e $0 < p1, p2 < p$. Perceba que para chegar em $n(p_1) = n(p_2) = 1$ só podemos ter quebrado um número que tem $n(p) \equiv 0~(mod~2)$, por conta da observação anterior. Logo, chegamos a conclusão que o único estado ganhador advém de quebrar um número que tem $n(p)$ par.

Também perceba que sempre podemos garantir que sempre cairemos em um estado par, enquanto nosso oponente caí em um estado ímpar. Já que podemos quebrar um $p$ com $n(p)$ par em dois $p_1$ e $p_2$ com $n(p_1)$ e $n(p_2)$ ímpar, fazendo com que o oponente só possa escolher um número $x$ com $n(x)$ ímpar. E um oponente que vai quebrar um $n(p)$ ímpar só pode dividir ele em um ímpar e em um par, e quando isso acontece podemos simplesmente escolher o par toda vez. Como vamos diminuir o MSB (Most Significant Bit) do número em pelo menos 1 toda rodada, temos certeza que o jogo não dura mais que $log2(10^{18}) < 63$, logo não precisamos nos preocupar com o limite.

Concluindo, nossa estratégia é:

• Se o número inicial $n$ for par, jogar primeiro, se não, jogar segundo.
• Sempre que tiver a opção de escolher entre $p_1$ e $p_2$ escolha o que tem $n(x)$ par (como nosso oponente sempre caí em um ímpar garantimos que sempre vai ter essa opção).
• Quando for quebrar um número com $n(p)$ par, quebre ele em dois $p1, p2$ tal que $n(p_1) \equiv n(p_2) \equiv 1~(mod~2)$.

Assim, garantimos que nunca perdemos o jogo!

Clique aqui para ver o código.