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.
Podes começar por descarregar os ficheiros correspondentes à tua linguagem (ou um arquivo zip contendo tudo):
| Linguagem | Ficheiro a implementar | Ficheiro com avaliador exemplo | Ficheiros auxiliares | Input para avaliador exemplo |
| C | resolver.c | avaliador.c | avaliador.h | input.txt |
| C++ | resolver.cpp | avaliador.cpp | ||
| Java | resolver.java | avaliador.java | ------ | |
| Pascal | resolver.pas | avaliador.pas | avaliadorlib.pas |
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.
Função a implementar:
| 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); |
A tua função deve invocar a seguinte função:
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.
Funções do avaliador:
| C/C++/Java: | int analisar(int V); |
| Pascal: | function analisar(V : longint) : longint; |
avaliador.analisar(V).
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).
A vossa função não deve ler nem escrever para os canais de entrada/saída padrão.
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}).
Uma possível execução seria a seguinte (com a ordem das chamadas a ser de cima para baixo):
| Invocação | Resultado | Descrição |
| 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. |
Os casos de teste deste problema estarão agrupados em conjuntos de testes. Ao contrário dos restantes problemas, para obter pontuação é necessário acertar todos os casos de teste de um grupo de casos, nesse caso terão a pontuação completa relativa a esse grupo. Se falharem um ou mais casos de um grupo, a pontuação atribuída relativa a esse grupo será nula.
Cada grupo tem um número de pontos associado e um conjunto de restrições adicionais. Os grupos são os seguintes:
| Grupo | Número de Pontos | Restrições adicionais |
|---|---|---|
| 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 |
É disponibilizado um avaliador exemplo em cada linguagem (avaliador.{c,cpp,java,pas}) que pode ser utilizado para testar a vossa submissão. Para C/C++/Pascal está ainda disponível um ficheiro auxiliar (para C/C++ o avaliador.h e para Pascal o avaliadorlib.pas). Este avaliador não corresponde ao utilizado pelo sistema de avaliação.
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.
Disponibilizamos um ficheiro input.txt que contém o caso de exemplo referido a cima.
Um exemplo de teste na tua máquina (supondo que tens os compiladores oficiais instalados) seria o seguinte:
| Linguagem | Compilar | Executar com o exemplo |
| C | gcc -Wall avaliador.c resolver.c | ./a.out < input.txt |
| C++ | g++ -Wall avaliador.cpp resolver.cpp | ./a.out < input.txt |
| Java | javac avaliador.java resolver.java | java avaliador < input.txt |
| Pascal | fpc avaliador.pas | ./avaliador < input.txt |