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.

Final ONI 2005: Problema A - Futebol

Já estão apurados os finalistas das Olimpíadas de Informática 2014. A final é já na próxima semana :)

Mas hoje vou continuar a análise dos problemas que tenho vindo a fazer. Começo a final de 2005, ano do meu 12º, com o problema A - Futebol.

Neste problema, é-nos dada a dimensão de um terreno rectangular com Y linhas e X colunas (1 ≤ Y, X ≤ 1000). Em cada célula do mapa existe relva ou uma árvore. Queremos construir um campo de futebol com L linhas e C colunas. Em que posição do mapa devemos construir o campo, de modo a termos de cortar o mínimo de árvores possível?

Exemplo do enunciado: mapa com 5 linhas e 8 colunas, para um campo de futebol 2x3 basta cortar 1 árvore

Qualificação ONI 2005: Problema C - Descobrindo Anagramas

O último problema da qualificação das ONI 2005 chama-se Descobrindo Anagramas.

Uma classe de anagramas é um conjunto de palavras com as mesmas letras mas por outra ordem. Exemplo: caras, casar e sacar são anagramas, fio e foi formam outra classe.

Dado um texto com no máximo 20 000 palavras distintas, pretende-se saber quantas classes de anagramas existem.

Nos dias de hoje, esta este problema muito frequente em entrevistas de emprego.

Qualificação ONI 2005: Problema B - Dizimação Completa

O problema B da qualificação das ONI 2005 chama-se Dizimação Completa.
Dados A e B com 0 < A < B e B ≤ 1024, o problema consiste em determinar a representação do número A / B. Alguns números têm representação exacta, mas outros têm dizimas infinitas.
Dos que não têm representação finita, alguns têm uma parte fixa e outros não.

Exemplos:

• 1 / 2 = 0.5
• 127 / 128 = 0.9921875
• 1 / 7 = 0.142857142857... não tem parte fixa e o período “142857” repete­-se indefinidamente.
• 19 / 44 = 0.43181818... a parte fixa é “43” e a parte periódica é “18”.

Assim, o objectivo é apresentar o número no formato "parte_fixa#período".

Qualificação ONI 2005: Problema A - Tiro ao Alvo

Agora passamos para as ONI 2005. Desta vez, temos disponíveis os problemas da qualificação.
O problema A chama-se Tiro ao Alvo e é provavelmente dos problemas mais simples que já vi nas ONI.

São-nos dadas as coordenadas do centro de N (<= 100) círculos e o respectivo raio e até 10000 pontos correspondentes a dardos. O objectivo é determinar a pontuação de cada dardo: o número de círculos que contêm esse dardo, agregar o número de dardos com a mesma pontuação e mostrar o output ordenado por pontuação.

Análise
O problema envolve simplesmente testar cada dardo contra cada um dos círculos, usando a equação do círculo (x-x₀)² + (y-y₀)² <= r².
Note-se que este algoritmo tem uma complexidade na ordem de 100*10 000 = 1 000 000 operações, sendo seguramente suficientemente eficiente.
Só podem existir N+1 (no máximo 101) pontuações diferentes, por isso nem é necessário utilizar um algoritmo muito eficiente para a ordenação.

War story - Final ONI 2004

Nos posts anteriores, fiz a análise aos problemas das ONI 2004. Infelizmente, já não encontro online o link para os resultados da prova. Se bem me lembro, 22 dos 30 finalistas tiveram 0 pontos, eu incluído.

Pessoalmente, houve várias coisas que correram mal, descontando a óbvia falta de conhecimentos de algoritmos:

• Não tinha uma estratégia bem definida para atacar os problemas. 
• Estava a concorrer usando uma linguagem, Pascal, que tinha aprendido no ano anterior mas que usava pouco nessa altura, visto que no 11º usava essencialmente Visual Basic.
• O editor que sempre tinha usado para programar em Pascal, Turbo Pascal, não funcionava nos computadores da prova e tive de usar outro editor. Apesar de não ser muito grave, ainda perdi 30+ minutos já com a prova em curso para saber que editor poderia usar, como usar, como compilar, etc.

No fundo, tudo se resume a má preparação. Não se vai a um evento importante sem a devida preparação dos detalhes importantes.
A falta de experiência pode levar-nos a pensar coisas como "o Turbo Pascal tem de estar disponível, é o editor que sempre usei!", mas é importante aprender que tanto nos concursos como em todas as coisas coisas da vida, não devemos assumir nada, por mais evidente que possa parecer.

Durante a prova, fui deambulando de problema para problema e as 4h passam bem depressa para quem não tem uma ideia clara do que está a fazer!

No problema A, penso que na altura não compreendi bem o enunciado e tive dificuldades com os centros das quadrículas, não conseguindo determinar correctamente quais eram as quadrículas abrangidas pelas crateras.

Gastei a maior parte do meu tempo no problema B. Não tinha (ou não conhecia) um algoritmo eficiente na biblioteca standard do Pascal. Por isso tentei implementar um Quick Sort à mão e penso que não correu bem. Isto foi numa altura em que eu tentava memorizar a implementação de alguns algoritmos e despejar caso me lembrasse..

Penso que não ataquei muito o problema C. Provavelmente tentei alguma coisa mas penso que tive problemas com a geração recursiva dos números possíveis.

A prova acabou por correr bastante mal a toda a gente da minha escola. Para mim, valeu pela experiência e para aprender com os erros. Infelizmente, não tenho fotos desta prova.

Final ONI 2004: Problema C - Em busca dos números perdidos

O último problema da final das ONI 2004 é bem mais interessante do que os outros. Este problema chama-se Em busca dos números perdidos.

Neste problema, são-nos dados 2 números parcialmente definidos, e.g. "?3" e "?", e temos de determinar quantas maneiras possíveis existem de substituir os '?' por um digito 0-9, de modo a que a soma dos 2 números seja um número primo (e.g. "03" + "0" = 3 que é primo).

Os números parcialmente definidos têm até 4 caracteres, i.e. "????" + "????" é um input válido, assim como "1234" + "5678" também. Existem até 100 casos de teste em cada execução.

Final ONI 2004: Problema B - Analisador de Textos

O problema B das finais das ONI 2004 chama-se Analisador de Textos.

Neste problema, é-nos fornecido um texto composto por L (<= 10 000) linhas de até 100 caracteres e temos de produzir uma de 4 possíveis estatísticas:

1. Calcular o número de palavras no texto e o número de palavras diferentes.
2. Contar as ocorrências de cada letra do alfabeto no texto.
3. Listar as palavras por ordem de frequência decrescente.
4. Listar as palavras por ordem de comprimento decrescente.

Não há mais de 60000 palavras no texto, nem mais de 5000 palavras diferentes. Cada palavra tem no máximo 30 letras.

Final ONI 2004: Problema A - Base Lunar

Em 2004, as finais nacionais das ONI passaram para o formato actual: 3 problemas para resolver em 4 horas. O problema A destas finais foi o Base Lunar.

Neste problema, temos um mapa lunar de dimensão máxima 20x20 quadrículas e um conjunto de N (<= 50) crateras. As crateras são círculos e são-nos fornecidas as coordenadas do seu centro e raio. Uma quadrícula considera-se dentro da cratera se o centro da quadrícula estiver contido no circulo.
Disto isto, o objectivo é determinar qual é a maior linha horizontal e vertical de quadrículas não abrangidas pelas crateras.

ONI 2003 - Alcunhas

O segundo problema das finais das ONI 2003 chama-se Alcunhas. Neste problema, temos um dicionário com N palavras (N <= 1000) com até 30 letras. Posto isto, é dado um número indeterminado de nomes de pessoas na mesma linha separados por espaços e temos de terminar quais os nomes cujas iniciais formam palavras do dicionário. Exemplo: as iniciais de "Rita Inês Costa Almeida" formam a palavra "rica".

ONI 2003 - Pizzapolis

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.