Final ONI 2005: Problema B - A máquina do Professor ONI

Tem sido difícil arranjar tempo para escrever no blog. Hoje continuo a análise de problemas, desta vez sugiro o problema B da final de 2005 - A máquina do Professor ONI.

Neste problema, temos uma máquina que é constituída por um conjunto de tubos que se bifurcam em L níveis (1 < L < 20). No final dos tubos do último nível, existem baldes, numerados a partir de 1. Existe uma patilha em cada bifurcação. Quando lançamos uma bola no início do primeiro tubo, esta segue a orientação das patilhas. Inicialmente, todas as patilhas estão orientadas para a direita, mas quando uma bola passa numa patilha, a sua orientação inverte-se (direita -> esquerda e vice-versa).

Exemplo de uma máquina com 2 níveis e o resultado do lançamento de 4 bolas.

Assim, o objectivo do problema é saber, após o lançamento de N bolas (1 ≤ N ≤ 1 000 000) numa máquina com L níveis, em que balde é que a N-ésima bola cai.

Análise

Este problema é bastante engraçado. Aqueles que conhecem algumas estruturas de dados, rapidamente reparam que esta máquina é nada mais, nada menos, do que uma árvore binária completa com L níveis. Assim, o número de baldes é 2^L. Apesar disso, este exercício não requer nenhum conhecimento especial e é um bom puzzle para resolver com papel e caneta.

Em primeiro lugar, podemos ver na figura acima que após o lançamento de 2^L bolas, as patilhas voltam ao estado inicial. Assim, podemos procurar apenas a bola cujo número é o resto da divisão de N por 2^L.

Posto isto, podemos percorrer os níveis do topo para o fundo. Quais são as bolas que vão para a direita da primeira patilha? As bolas com número ímpar!
E nas patilhas do nível a seguir? É semelhante, mas devemos remover o número de baldes que já descartamos.

Tomem a figura seguinte como exemplo em que L = 3 e N = 5.

Estado de uma máquina com 3 níveis, após o lançamento de 4 bolas

Como N = 5 é ímpar, sabemos que a bola 5 vai para a direita na primeira patilha. Assim, existem 4 baldes onde a bola não pode calhar: 1 a 4.
Sabemos que as bolas 2 e 4 foram para a esquerda (2 bolas é metade de 5 arredondado para baixo pois uma bola ímpar vai para a direita), por isso, apenas 3 bolas passam na patilha direita do nível 2. Como 3 é ímpar, sabemos que a bola vai para a direita (não pode calhar nos baldes 5 e 6).
Como anteriormente apenas passou uma bola no na patilha mais à direita do nível 3, a bola 5 vai para a esquerda, caindo no balde 7.

Apenas percorremos os níveis da árvore. Assim, o algoritmo tem uma complexidade temporal de O(L).