East Central 2008/2009

Informações

A - Bordering on Madness

B - Jack of All Trades

Neste problema, os itens podem ser vistos como um grafo e as trocas como arestas cujo peso é a razão entre os itens da troca. O custo final de uma troca é a multiplicação dos pesos das arestas percorridas. A idéia, portanto, é encontrar um "menor caminho multiplicativo".

O truque é lembrar da seguinte propriedade: $\log (ab) = \log a + \log b$

Assim, um Bellman-Ford implementado cuidadosamente resolve o problema.

C - LCR

D - Party Party Party

E - Su-Su-Sudoku

Resolvedor de sudoku padrão, via backtracking. Os números válidos para cada posição vazia são aqueles que não aparecem nem na linha, nem na coluna, nem no quadrante da célula que queremos preencher. Se/Quando conseguirmos preencher todas, terminamos o puzzle.

Exercício: implementar a solução para este problema, e também um resolvedor para casos genéricos. Um tabuleiro mais vazio requer mais cuidado na hora de programar para que não fique lento demais.

F - Tanks a Lot

G - The Worm Turns

H - You'll be Working on the Railroad

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License