Puc Rio Treino I

Informações

  • Colocar link pra prova

A - Claustrophobic Cows

Determinar os dois pontos mais próximos do plano.

B - Job Hunt

Cria um grafo onde os nós são as cidades e as arestas o caminho entre cidades. O peso de uma aresta é $-100 - custo$, onde custo é 0 se for de graça utilizar aquela aresta ou o preço cobrado por John se aquela aresta é controlada por ele.
Cria um nó "dummy" onde vc iria começar tal que tem arestas saindo para todos os outros nós com valor 0.

Faz um Bellman-Ford partindo do nó "dummy" para todos os outros
Se este grafo possuir um ciclo negativo significa que é possível sair de uma cidade i, visitar outras e voltar à i com mais dinheiro. Nesse caso responde -1.
Se não existe ciclo negativo imprime o menor caminho encontrado de "dummy" para um outro nó.

C - The Chivalrous Cow

Gera um grafo onde cada nó é uma posição do tabuleiro. Existe uma aresta entre dois nós (i e j) se i e j não são pedras E se é possível fazer um movimento do cavalo do nó i para o nó j.
Faz uma BFS da posição inicial para a final.

D - The Grand Farm-off

Ordena as vacas primeiro em função da utilidade (U[i]) e como critério de desempate o seu peso (W[i]). Pega as N primeiras vacas de acordo com esse critério. Cuidado pois os limites estouram o int, procure utilizar long long e aplicar o módulo sempre que possível.

E - A Coin Game

F - Cow Pinball

Comentários

Os problemas foram retirados do USACO, contest Elite November 2009 (Bronze e Silver). A análise oficial está disponível aqui.

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