XXVI Olimpíada Brasileira de Informática

Novas Estradas

O rei na Nlgônia decidiu povoar uma ilha inabitada do reino, construindo na ilha cinco novas cidades. O rei quer construir estradas entre as cinco cidades. Duas cidades são consideradas desconectadas se não houver caminho formado por estradas entre elas. Por exemplo, se houver uma estrada ligando a cidade A à cidade B e outra estrada ligando a cidade B à cidade C, então a cidade A está conectada à cidade C, pois é possível ir de A para C passando pela cidade B. O rei tem o seguinte plano: enquanto houver um par de cidades desconectadas, serão sorteadas duas cidades da ilha; se já não houver uma estrada entre as duas cidades sorteadas, uma nova estrada será construída entre essas duas cidades.

Questão 1. Qual é o número mínimo de estradas que podem ser construídas seguindo o plano do rei?
3
4
5
8
10

Questão 2. Qual é o número máximo de estradas que podem ser construídas seguindo o plano do rei?
5
6
7
9
10

Tarefas Iniciação Nível Júnior
Promoção
logo sbc
Patrocínio
Apoio
Coordenação