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

Jogo da Ponte (SPOJ - WAYHOME)

Na semana passada, vi um problema engraçado no SPOJ chamado WAYHOME e decidi resolvê-lo, sendo o meu problema #698 para o ranking (759 resolvidos no total).
O problema baseia-se num puzzle que já tinha ouvido falar e que dá para fazer aos amigos:

Um grupo de pessoas pretende atravessar uma ponte usando uma lamparina. A ponte é perigosa e só 2 pessoas podem atravessá-la ao mesmo tempo. As pessoas caminham a velocidades diferentes, por isso, se 2 pessoas estão a atravessar a ponte, deslocam-se à velocidade da mais lenta. Além disso, está escuro, por isso uma das pessoas tem de levar a lamparina enquanto atravessam a ponte. 

Dadas as velocidades das pessoas, qual é o tempo mínimo para passar todas as pessoas de um lado para o outro? E.g. 3 pessoas com velocidades 1, 1 e 2, demoram 4min a atravessar (ver figura seguinte). Se forem 4 pessoas com velocidades 1, 2, 4, 8, demoram 15min. Porquê? E se forem N pessoas, que abordagem garante o menor tempo possível?

MIUP 2013 - Um problema de Grafos

Não tive oportunidade de escrever no blog nas últimas semanas. Para compensar, hoje vou falar de um problema um pouco mais difícil do o habitual: o problema B da MIUP 2013 - Say Geese.

Objectivo do problema:

Dado um grafo não-dirigido com N (<= 11) vértices e E (<= 45) arestas (edges), quantos subconjuntos de arestas formam um grafo conexo?