Alpro

O problema proposto foi o seguinte:
A CIA só consegue se comunicar com a sua base por telefones públicos. Então para tentar confundir os agentes soviéticos os agentes chegam às cabines telefônicas da forma mais irregular possível para chamar menos atenção, mas seguem as regras abaixo: Para evitar a escuta o agente sempre prefere uma cabine que tenha suas duas vizinhas desocupadas (isto inclui as cabines das pontas, se for o caso). Se isto não é possível, ele prefere uma cabine com uma vizinha desocupada. Se isto também não é possível, ele escolhe qualquer cabine.
Uma figura de exemplo para ilustrar o caso acima:

Fig.1
A nossa missão é escrever um programa que conta quantas maneiras existem para que os espiões cheguem e ocupem as cabines.

Solução Proposta:

Entendido o problema, foi feito um desenho a mão de como deveriam os espiões entrar nas cabines como na imagem acima (fig.1). Para ser possível descobrir todas as possibilidades teríamos de fazer com que fosse identificado quando chega um novo espião, qual a cabine que ele ocupa e como isso afeta as demais cabines.
Foi decidido então por não usar nenhuma estrutura gerencial (filas, pilhas, vetor) apenas por um capricho para ver se isto poderia ser feito.
Nesse momento foi verificada a necessidade de usar um numero flutuante (Double) para operações com potências (pow) e também a necessidade da adoção de um padrão.
Foi feito então a seguinte combinação:

Se uma cabine está vazia e as suas vizinhas também, ela recebe o valor “2”;
Se uma cabine está vazia, mas uma de suas vizinhas está ocupada, ela recebe o valor “1”;
Se uma cabine está vazia e não tem nenhuma de suas vizinhas livres, então ela recebe o valor “0”;
Quando uma cabine é ocupada, é atribuído a ela o valor 9 (por convenção);
Quando uma cabine da ponta (que possui apenas um vizinho) tem o seu vizinho ocupado, seu valor é considerado como 1 (pois não há como ter um “agente soviético”