Preparação para o CodeJam - de uma fonte inesperada

Estou encontrando alguns exercícios de programação em um local inesperado - no The Daily WTF. Há poucas semanas iniciou uma nova série, a Programming Praxis. Toda quarta é apresentado um problema e as soluções vão sendo postadas nos comentários.

Até agora os problemas foram relativamente simples (e com solução facilmente encontrável no Google); a enfase tem sido nas soluções em linguagens exotéricas. Mesmo assim, é um bom exercício.

Apresento abaixo uma adaptação livre (e preguiçosa) do problema de ontem, "Nerds, Jocks, and Lockers". Recomendo tentar resolver antes de olhar os comentários no The Daily WTF. Amanhã publico uma pequena explicação da solução.

Cabeções, Marombeiros e Armários

Sr Zargas era o professor de matemática que todos gostavam. Fosse você um cabeção ou um marombeiro, ele deixava a matemática interessante, desafiadora e divertida de aprender. E na "Guerra dos Armários" os marombeiros podiam usar os músculos - e ganhavam sempre dos cabeções.

As regras da "Guerra dos Armários" são simples. Em um corredor abandonado da escola, existiam cem armários vazios, um ao lado do outro. O problema é determinar quais armarios ficariam abertos se todos os armários forem fechados e depois tocados da seguinte forma (cada toque abre um armário fechado e fecha um armário aberto):

• cada armário é tocado a partir do primeiro
• cada segundo armário é tocado a partir do segundo
• cada terceiro armário é tocado a partir do terceiro
• ...
• o centésimo armário é tocado

Os marombeiros resolviam o problema seguindo à risca as instruções acima e correndo de um lado para o outro contando armários.

Sua missão, jovem cabeção, é achar uma forma de determinar quais armários permanecem abertos sem fazer múltiplas passagens (ou seja, achar uma solução que não seja de "força bruta"), para o caso genérico de "n" armários.