• Revista PROGRAMAR: Já está disponível a edição #53 da revista programar. Faz já o download aqui!

mogers

Marcha dos Pinguins - nivel Muito Alto

6 mensagens neste tópico

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.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

É 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).

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Podes ir escrevendo, e quando tiver concluido, envias para a revista :)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!


Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.


Entrar Agora