Torre defeituosa
Problema C - Torre defeituosa
A bonita cidade de Tondela está prestes a ser o centro de uma revolução tecnológica. Está a ser instalada uma enorme rede de torres de comunicação, que irão providenciar wi-fi gratuito de alta velocidade em qualquer zona da cidade!
O sistema é constituído por N torres de comunicação que estão interligadas com cabos de alta velocidade. Há exatamente N - 1 cabos bidirecionais a interligar torres, e cada um liga duas torres distintas. Além disso, sabe-se que o sistema de cabos é conexo, ou seja, é possível chegar de uma torre a uma qualquer outra torre seguindo apenas cabos.
As torres e os cabos estão todos em posição e está tudo pronto para ser lançado, mas aparentemente uma das torres tem um problema de conexão que está a afetar o sistema todo! O maior problema é que ninguém sabe qual é.
Para descobrir onde se encontra a torre defeituosa, os engenheiros do projeto conseguem investigar qualquer uma das torres e descobrir se é essa a torre defeituosa. Além disso, caso a torre não seja a defeituosa, os engenheiros conseguem determinar qual das torres ligadas com cabos à torre analisada está mais próxima da torre defeituosa (em termos de número de cabos que é necessário seguir para a atingir).
O tempo disponível pelos engenheiros não é muito, por isso só conseguem analisar no máximo D torres antes de atingirem o limite de tempo do projeto. Consegues ajudá-los a escolher as torres para analisar de modo a concluírem o projeto a tempo?
Dado um conjunto de N torres e os cabos que as ligam, determinar a torre defeituosa em menos de D tentativas.
Nota que a implementação do avaliador a usar nos testes oficiais será diferente, mas podes esperar o mesmo comportamento. Além disso, é garantido que o avaliador demora menos de 0.1 segundos a analisar D torres.
Deves submeter um único ficheiro que implementa a função resolver(N, D, Es, Et), que recebe um inteiro N, que representa o número de torres, um inteiro D que representa o número máximo de análises que podem ser efetuadas, e duas listas de torres Es e Et, cada uma com N - 1 elementos onde o i-ésimo elemento da lista Es representa um dos extremos do i-ésimo cabo e o de Et o outro extremo (ou seja, as duas listas representam os N - 1 cabos). Para isso deves usar o ficheiro resolver.{c,cpp,java,pas} que descarregaste, colocando no interior da função o teu código. Podes acrescentar outras funções, mas devem ficar todas neste ficheiro que é o único que deves submeter.
C++/C: void resolver(int N, int D, int Es[MAXN], int Et[MAXN]);
Java: void resolver(int N, int D, int[] Es, int[] Et);
Pascal: procedure resolver(N : longint, D : longint, Es : array of longint, Et : array of longint);
analisar(V) implementada pelo avaliador, que recebe uma torre V e devolve -1 caso esta seja a torre defeituosa, ou a torre U mais próxima da defeituosa caso contrário.
Nota que é importante que V esteja entre 1 e N. Também é importante notar que se excederes as D análises o programa será interrompido e a resposta será considerada incorreta.
C/C++/Java: int analisar(int V);
Pascal: function analisar(V : longint) : longint;
No caso do C e C++, o valor de MAXN está definido no ficheiro avaliador.h e é de 100 005 (mais que o valor máximo de N, definido em baixo).
No caso do Java, a função do avaliador está incluída na classe avaliador e por isso deve ser chamada escrevendo avaliador.analisar(V).
No caso do Pascal, o valor de MAXN está definido no ficheiro avaliadorlib.pas e é de 100 005 (mais que o valor máximo de N, definido em baixo).
O teu objetivo é descobrir a torre defeituosa. Para tal, deves chamar a função analisar(V) com a torre correta, ao qual esta irá retornar -1 e não deverás chamar mais nenhuma vez a função analisar(V).
Imagina que o sistema tem N = 6 torres, tens D = 5 análises e que há uma ligação entre as seguintes torres: (1, 2), (1, 3), (2, 4), (2, 5), (3, 6). A função resolver que deves implementar será chamada como resolver(6, 5, {1, 1, 2, 2, 3}, {2, 3, 4, 5, 6}).
analisar(2) 1 A torre 2 não é a defeituosa e a 1 é a mais próxima das 3 possíveis (1, 4, 5).
analisar(1) 3 A torre 1 não é a defeituosa e a 3 é a mais próxima das 2 possíveis (2, 3).
analisar(3) 6 A torre 3 não é a defeituosa e a 6 é a mais próxima das 2 possíveis (1, 6).
analisar(6) -1 É a torre 6!
Para este exemplo, a torre defeituosa era a número 6. A imagem seguinte mostra este exemplo.
1 ≤ N ≤ 100 000 Número de torres.
1 ≤ D ≤ N Número de tentativas.
1 10 N ≤ 100, D = N
2 20 N ≤ 100, D = N / 2
3 20 D = 20, as torres formam uma linha (ver imagem a baixo)
4 25 N ≤ 1 000, D = 12
5 25 D = 20
Este avaliador começa por receber como input um inteiro N e um inteiro D correspondendo, respetivamente, ao número de torres e ao número máximo de análises. Seguem-se N - 1 linhas, cada uma com 2 inteiros entre 1 e N que representam os extremos de cada cabo. Finalmente, segue-se uma linha com apenas um inteiro que representa o número da torre defeituosa.
O avaliador irá automaticamente invocar a função resolver(N, D, Es, Et) por vocês implementada e indicará se a resposta foi correta. Em caso afirmativo, também indicará o número de análises que foram efetuadas.