Jump to content
Sign in to follow this  
mogers

Marcha dos Pinguins - nivel Muito Alto

Recommended Posts

mogers

Este foi o problema B do ACM Northwestern European Programming Contest 2007. Pode ser submetido num judge online aqui

Acho que estava a faltar a esta secção um desafio muito dificil :)

Titulo:

Marcha dos Pinguins

Enunciado:

Algures perto do pólo sul, um conjunto de pinguins encontram-se sobre alguns blocos de gelo. Sendo animais sociais, os pinguins gostariam de se juntar no mesmo bloco de gelo.

Os pinguins não se querem molhar, assim eles têm de usar a sua capacidade de salto limitada para saltar de bloco em bloco de gelo. Contudo, ultimamente as temperaturas têm sido elevadas, fragilizando o gelo e os blocos de gelo são danificados pela força que os pinguins exercem para saltar desses blocos para outros. Felizmente, os pinguins são especialistas em quebrar blocos de gelo, por isso, sabem exactamente quantos saltos podem ser efectuados a partir de cada bloco de gelo sem que este fique destruido. Aterrar num bloco de gelo não o danifica.

Objectivo:

Encontrar todos os blocos de gelo onde os pinguins se podem encontrar.

p3972.png

Um exemplo de um conjunto de blocos de gelo com 3 pinguins (1º caso de teste do sample input)

Explicação do Input:

Na primeira linha vem um número inteiro positivo: o número de casos de teste (no máximo 100). A seguir, para cada caso de teste:

    * Uma linha com um inteiro N (1 ≤ N ≤ 100) e um número décimal D (0 ≤ D ≤ 100000), que significam o número de blocos de gelo e a distância máxima (euclidiana) que um pinguim consegue saltar.

    * N linhas, cada uma contendo xi, yi, ni e mi, ou seja, a coordenada X e Y de cada bloco de gelo, o número de pinguins em cima dele e o número máximo de vezes que um pinguim pode saltar a partir desse bloco antes que ele fique destruido (-10000 ≤ xi, yi ≤ 10000, 0 ≤ ni ≤ 10, 1 ≤ mi ≤ 200).

Explicação do Output:

Para cada caso de teste:

    * Uma linha contendo uma lista dos índices dos blocos (índices começam em 0) onde todos os pinguins se podem encontrar. Se não existir nenhuma solução, imprime -1.

Sample Input:

2

5 3.5

1 1 1 1

2 3 0 1

3 5 1 1

5 1 1 1

5 4 0 1

3 1.1

-1 0 5 10

0 0 3 9

2 0 1 1

Sample Output:

1 2 4

-1

Explicação do Sample Output:

No primeiro caso de teste, os pinguins podem-se encontrar em 3 blocos com os índices 1, 2 e 4, ou seja, coordenadas 2,3 ; 3,5 e 5,4. Para se encontrarem no bloco:

  • 1, os pinguins nos blocos 0 e 2 podem saltar directamente para o bloco 1. Enquanto que o pinguin no bloco 3 necessita de saltar primeiro para o bloco 4 e depois para o 1.
  • 2, o pinguim no bloco 2 já se encontra lá. Enquanto que os pinguins nos blocos 0 e 3 têm de saltar primeiro para os blocos 1 e 4, respectivamente, antes de saltar para o 2.
  • 4, os pinguins nos blocos 2 e 3 podem saltar directamente para o bloco 4. Enquanto que o pinguin no bloco 0 necessita de saltar primeiro para o bloco 1 e depois para o 4.

No segundo caso, não há solução. O bloco mais próximo de 2,0 é 0,0 que se encontra a uma distância 2 > 1,1. O pinguim neste bloco não pode saltar para nenhum bloco, nem os pinguins dos outros blocos podem atingir este. Conselho: não tratar isto como caso especial. Há mais situações em que é impossivel.

Material de apoio:

Distância euclidiana na wikipedia.

Restrições:

A solução deve ter um tempo de execução polinomial.


"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Share this post


Link to post
Share on other sites
mogers

Se alguém estiver a pensar no problema, eu posso dar algumas dicas se quiserem.


"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Share this post


Link to post
Share on other sites
Warrior

Parece-me semelhante a um problema que vi há uns tempos no topcoder (dadas duas matrizes binárias saber o número mínimo de swaps para que fiquem iguais)

É um problema de flow?

PS: Ainda estou no Algarve, assim que voltar para casa talvez lhe dê uma olhadela mais aprofundada.

Share this post


Link to post
Share on other sites
mogers

É um problema de flow?

É sim ;)

PS: por isso é um exercício de nível universitário. Os problemas de flow não constam no syllabus das IOI, por isso não podem sair (acho eu).


"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Share this post


Link to post
Share on other sites
mogers

alguém interessado na solução? Se bem que isto era capaz de ser giro num artigo da revista programar sobre fluxo máximo em grafos e suas extensões (o problema é sobre uma extensão). Mas eu não me vejo com tempo para escrever um artigo desses nos próximos tempos :x


"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
Sign in to follow this  

×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.