OBI 2022 - Fase 3 - Programação Nível Júnior
Para se preparar para a OBI, confira o nosso Roteiro de Estudos, nele você vai encontrar um direcionamento completo de como estudar!
Para conferir a prova na íntegra, clique aqui.
Jogo
Escrito por Enzo Dantas
Conhecimento prévio necessário:
Temos dois tipos de numero: e . Enquanto (enquanto o jogador não acertar o número sorteado), o jogador vai tentar de novo até acertar. O problema diz:
- Se , printe "menor"
- Se , printe "maior"
- Se , printe "correto" e não haverá mais tentativas
Assim, para ler as várias tentativas do jogador, vamos colocar a função de leitura ( ou no C++) dentro de um que encerra quando (ou um while que funciona enquanto houver tentativas).
Clique aqui para conferir o código
Teste de Redação
O problema está indisponível por enquanto, então não conseguimos fazer o comentário dele. Assim que ele ficar disponível fazemos seu tutorial.
Carro Elétrico
Escrito por Enzo Dantas
Conhecimento prévio necessário:
Parcial 1 (37 pontos):
Para essa subtask, devemos apenas calcular se é possível ir de uma cidade à outra usando o carro, ou seja, se a autonomia dos carros é maior ou igual à distância entre as duas cidades. A distância entre dois pontos é km, e devemos checar se . Para facilitar a compreensão, vamos nos referir a como se fosse e a como se fosse .
Parcial 2 (32 pontos):
(todas as cidades estão na mesma linha), e é garantido que as cidades são dadas em ordem crescente de (isto é, ).
Perceba que, ao simular imaginariamente um caso qualquer, vão se formar algumas "regiões" conectadas por carro.
Vamos chamar essas "regiões" de "componentes".
Perceba que, se a distância entre e é maior que A, eles fazem parte de componentes diferentes e é preciso usar o avião para conectá-las. Assim, para contar quantos aviões precisamos usar, vamos contar quantas vezes .
Parcial 3 (31 pontos):
Nenhuma restrição adicional
Nota: esse é um problema conhecido, no qual se deve contar o número de componentes conexas em um grafo.
Similarmente a subtask anterior, algumas componentes conectadas por carro vão se formar ao simular um caso qualquer.
Se temos N componentes, qual o número mínimo de aviões necessários para conectar todas elas?
Lema: o número mínimo de arestas necessárias para conectar N componentes = N-1
Imagine que temos uma componente só. Nesse caso, não precisamos de nenhuma nova aresta para conectar todas as componentes (1 componente, 0 arestas). Se adicionarmos mais uma componente, precisaremos adicionar uma aresta (2 componentes, 1 aresta), mais outra componente, mais outra aresta (3 componentes, 2 arestas), e assim em diante. Ou seja, para cada nova componente adicionada, precisaremos de mais uma aresta, então a subtração é constante. Como no caso inicial (componentes = 1) o número de arestas é , para qualquer número de componentes usaremos arestas.
Sendo assim, para construir o grafo e achar as componentes, vamos criar uma aresta entre todos os pares de pontos tal que a distância entre eles é menor ou igual a A. Feito isso, vamos realizar várias DFS's: vamos iterar pelos vértices e, se o vértice não tiver sido visitado, vamos adicionar 1 ao contador de componentes, vamos rodar uma DFS e vamos marcar todos os vértices da componente como visitado. Ao fim, devemos printar (quantidade de componentes - 1).
Complexidade:
Complexidade de memória: para cada vértice criaremos no máximo arestas. Como temos vértices, teremos arestas no total .
Complexidade de tempo: a complexidade de criar as arestas é , enquanto a complexidade da DFS é . A complexidade final é .
Clique aqui para conferir o código
Dígitos
Escrito por Vitor Veiga
Conhecimento prévio necessário:
Dada uma sequência de todos os dígitos presentes entre dois números quaisquer e , queremos encontrar o menor que satisfaz a sequência. A ideia para o problema será checar todos os possíveis , de até algarismos, até achar um termo inicial que satisfaz as restrições da sequência.
Para isso, utilizaremos as strings para nos auxiliar, pela maior facilidade em adicionar e remover algarismos. Começamos com duas strings e , que armazenam o número inicial e o próximo número que temos que achar para haver uma sequência válida, ou seja, , , , e assim por diante. Sempre que acharmos o , adicionamos uma unidade no número contido nele e continuamos nosso loop.
Para melhor entendimento da ideia, o passo a passo do primeiro caso teste:
e
O primeiro número inicial que testaremos será o :
(ok)
(ok)
(ok)
(absurdo)
Depois, testaremos :
(ok)
(absurdo)
Finalmente, testaremos :
(ok)
(ok)
fim da sequência
Note que caso continuássemos, também seria válida a sequência que inicia com o número , que só teria ele mesmo.