International Olympiad in Informatics 2011
22–29 July 2011, Pattaya City, Thailand
Competition Tasks – Day 1
GARDEN
Portuguese 1.5
Tropical Garden
Somhed, um botânico, leva regularmente grupos de estudantes para passear num dos maiores
jardins tropicais da Tailândia. O jardim é composto de N fontes (numeradas 0, 1,..., N-1) e M trilhas
(caminhos). Cada trilha conecta um par diferente de fontes distintas, e pode ser percorrida em
qualquer direção. Há pelo menos uma trilha partindo de cada fonte. Essas trilhas passam por lindas
coleções botânicas que Somhed gostaria de ver. Cada grupo pode iniciar seu passeio em qualquer
fonte.
Somhed adora belas plantas tropicais. Portanto, em qualquer fonte ele e seus estudantes vão tomar a
trilha mais bonita que parte dessa fonte, a menos que essa seja a trilha tomada mais recentemente e
exista uma trilha alternativa. Nesse caso, eles irão tomar a segunda trilha mais bonita. Obviamente,
se não há alternativa, eles vão voltar, percorrendo a mesma trilha uma segunda vez. Note que como
Somhed é um botânico profissional, ele não considera duas trilhas igualmente bonitas.
Seus estudantes não têm muito interesse em plantas. No entanto, eles adorariam almoçar em um
restaurante especial localizado na fonte P. Somhed sabe que seus estudantes vão ter fome após
percorrer exatamente K trilhas, onde K pode ser diferente para cada grupo de estudantes. Somhed
se pergunta quantas rotas distintas ele poderia escolher para cada grupo, dado que:
• cada grupo pode iniciar em qualquer fonte;
• trilhas sucessivas devem ser escolhidas como descrito acima; e
• a rota de cada grupo deve terminar na fonte P após percorrer exatamente K trilhas.
Note que eles podem passar pela fonte P antes do final de sua rota, embora ainda necessitem
terminar sua rota na fonte P.
Sua tarefa
Dada a informação sobre fontes e trilhas, você deve encontrar as respostas para Q grupos distintos
de estudantes; isto é, Q valores de K.
Escreva um procedimento count_routes(N,M,P,R,Q,G) que tem os seguintes parâmetros:
 N – o número de fontes. As fontes são numeradas de 0 a N-1.
 M – o número de trilhas. As trilhas são numeradas de 0 a M-1. As trilhas serão dadas em
ordem decrescente de beleza: para 0 ≤ i < M-1, a trilha i é mais bonita do que a trilha i+1.
 P – a fonte na qual se localiza o restaurante especial.
 R – um vetor bidimensional representando as trilhas. Para 0 ≤ i < M, a trilha i conecta as
fontes R[i][0] e R[i][1]. Lembre que cada trilha liga um par de fontes distintas, e nenhum
par de trilhas liga o mesmo par de fontes.
 Q – o número de grupos de estudantes.
 G – um vetor unidimensional de inteiros contendo os valores de K. Para 0 ≤ i < Q, G[i] é o
número de trilhas K que o i-ésimo grupo deve percorrer.
Para 0 ≤ i < Q, seu procedimento deve encontrar o número de rotas possíveis com exatamente G[i]
trilhas que o grupo i poderia percorrer para chegar à fonte P. Para cada grupo i, seu procedimento
deve chamar o procedimento answer(X) para relatar que o número de rotas é X. As respostas devem
ser dadas na mesma ordem do que os grupos. Se não há rotas válidas, seu procedimento deve dar a
resposta X=0.
Page 1 of 3
International Olympiad in Informatics 2011
22–29 July 2011, Pattaya City, Thailand
Competition Tasks – Day 1
GARDEN
Portuguese 1.5
Exemplos
Exemplo 1
Considere o caso mostrado na Figura 1, onde N=6,
M=6, P=0, Q=1, G[0]=3, e
1
0
0
R=
3
4
1
2
1
3
4
5
5
Note que as trilhas são listadas na ordem
decrescente de beleza. Ou seja, a trilha 0 é a mais
bonita, a trilha 1 é a segunda mais bonita, e assim
por diante.
Figura 1.
Há apenas duas rotas válidas possíveis de comprimento 3:
 1 → 2 → 1 → 0, e
 5 → 4 → 3 → 0.
A primeira rota inicia na fonte 1. A trilha mais bonita a partir desse ponto leva à fonte 2. Na fonte 2,
o grupo não tem escolha, devendo retornar utilizando a mesma trilha. De volta à fonte 1, o grupo
agora evita a trilha 0, por ser a mais recentemente utilizada, e escolhe a trilha 2. Esta trilha
realmente os leva à fonte P=0.
Portanto, o procedimento deve chamar answer(2).
Exemplo 2
Considere o caso mostrado na Figura 2, N=5, M=5, P=2,
Q=2, G[0]=3, G[1]=1, e
1
1
R= 3
1
4
0
2
2
3
2
Para o primeiro grupo, há apenas uma rota válida que chega à
fonte 2 em após percorrer 3 trilhas: 1 → 0 → 1 → 2.
Figura 2.
Para o segundo grupo, há duas rotas válidas que chegam à fonte 2 após percorrer 1 trilha: 3 → 2, e 4
→ 2.
Portanto, a implementação correta de count_routes deve primeiro chamar answer(1) para relatar a
resposta para o primeiro grupo, e então chamar answer(2) para relatar a resposta para o segundo
grupo.
Page 2 of 3
International Olympiad in Informatics 2011
22–29 July 2011, Pattaya City, Thailand
Competition Tasks – Day 1
GARDEN
Portuguese 1.5
Subtarefas
Subtarefa 1 (49 pontos)
 2 ≤ N ≤ 1 000
 1 ≤ M ≤ 10 000
Q=1
 cada elemento de G é um inteiro entre
1 e 100, inclusive.
Subtarefa 3 (31 pontos)
 2 ≤ N ≤ 150 000
 1 ≤ M ≤ 150 000
 1 ≤ Q ≤ 2 000
 cada elemento de G é um inteiro entre 1 e
1 000 000 000, inclusive.
Subtarefa 2 (20 pontos)
 2 ≤ N ≤ 150 000
 1 ≤ M ≤ 150 000
Q=1
 cada elemento de G é um inteiro entre
1 e 1 000 000 000, inclusive.
Detalhes de implementação
Limites
 Tempo limite de CPU : 5 segundos
 Limite de memória: 256 MB
Nota: Não há limite explícito para o tamanho da memória de pilha. Memória de pilha é
contada no total de memória utilizada.
Interface (API)
 Diretório de implementação: garden/
 Para ser implementado pelo competidor: garden.c ou garden.cpp ou garden.pas
 Interface do competidor: garden.h ou garden.pas
 Interface do corretor: gardenlib.h ou gardenlib.pas
 Exemplo de corretor: grader.c ou grader.cpp ou grader.pas
 Exemplo de entrada para o corretor: grader.in.1, grader.in.2, ...
Nota: O exemplo de corretor lê a entrada no seguinte formato:
 Linha 1: N, M, e P.
 Linhas 2 a M+1: descrição das trilhas; i.e., Linha i+2 contém R[i][0] e R[i][1],
separados por um espaço, para 0 ≤ i < M.
 Linha M+2: Q.
 Linha M+3: vetor G como uma sequência de inteiros separados por espaços.
 Linha M+4: vetor de soluções esperadas como uma sequencia de inteiros separados
por espaços.
 Saída esperada para a entrada exemplo do corretor: grader.expect.1, grader.expect.2, ...
Para esta tarefa, cada um desses arquivos deve conter precisamente o texto “Correct”.
Page 3 of 3