A edição deste ano das Olimpíadas Nacionais de Informática (ONI) está prestes a arrancar. Estive a olhar para a página com os problemas de edições passadas e reparei que não existe uma página de discussão da maioria dos problemas. Como a análise aos problemas pode ser útil para quem está a praticar, decidi tentar fazê-la aqui no blog, começando no ano do meu 10º ano - 2003. Ao contrário de outros posts, a minha intenção é descrever as ideias principais e não postar o código, pois é importante que quem esteja a treinar seja capaz de implementar essas ideias por si.
O problema A da final nacional de 2003 chama-se Pizzapolis. Neste problema, estamos perante uma cidade com estradas perpendiculares umas às outras (chamamos ruas às estradas horizontais e avenidas às verticais). Existem milhares de pizzarias, situadas no cruzamento de uma rua com uma avenida, mas Pizzapolis contém 100 ruas e 100 avenidas, numeradas de 0 a 99.
Assim, dada a localização (rua e avenida) e a produção diária de cada pizzaria, o objectivo é determinar quais são as ruas e/ou avenidas com produção máxima de pizzas.
Análise
A chave do problema é que existem apenas 100 ruas e 100 avenidas. Assim, podemos usar um array para contabilizar a produção de cada rua e cada avenida. Para cada pizzaria, basta-nos adicionar a sua produção à rua e avenida correspondente.
Posto isto, podemos percorrer os 2 arrays para determinar qual é a produção máxima.
Por fim, percorremos os 2 arrays novamente para imprimir as ruas e/ou avenidas com a produção máxima.
Nota final: o problema é bastante simples. Penso que será notório que a dificuldade das ONI foi subindo ao longo dos anos, à semelhança do que tem acontecido com outras provas.
Sem comentários:
Enviar um comentário