Comentário NOIC OBI 2022 - Fase 3 - Programação Nível Júnior

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: X e T. Enquanto T \neq X (enquanto o jogador não acertar o número sorteado), o jogador vai tentar de novo até acertar. O problema diz:

  1. Se X<T, printe "menor"
  2. Se X>T, printe "maior"
  3. Se X=T, printe "correto" e não haverá mais tentativas

Assim, para ler as várias tentativas do jogador, vamos colocar a função de leitura (cin ou scanf no C++) dentro de um while que encerra quando T=X (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):

N=2

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 é dist=100*(|x_1-x_2| + |y_1-y_2|) km, e devemos checar se A \geq dist. Para facilitar a compreensão, vamos nos referir a A como se fosse \frac{A}{100} e a dist como se fosse |x_1-x_2| + |y_1-y_2|.

Parcial 2 (32 pontos):

Y=1 (todas as cidades estão na mesma linha), e é garantido que as cidades são dadas em ordem crescente de X (isto é, x_1<x_2<...<x_n).

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 x_i e x_{i+1} é 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 |x_i-x_{i+1}| > A.

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 Componentes-Arestas é constante. Como no caso inicial (componentes = 1) o número de arestas é Componentes-1, para qualquer número de componentes usaremos Componentes-1 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 v_i 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 N arestas. Como temos N vértices, teremos N*N arestas no total \Rightarrow O(N^2).

Complexidade de tempo: a complexidade de criar as N^2 arestas é O(N^2), enquanto a complexidade da DFS é O(V+E) = O(N+N^2). A complexidade final é O(N^2).

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 A e B, queremos encontrar o menor A que satisfaz a sequência. A ideia para o problema será checar todos os possíveis A's, de 1 até N 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  ini e busca, 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, ini + 1, ini + 2, ini + 3, e assim por diante. Sempre que acharmos o busca, 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:

N = 6 e S = {1, 2, 3, 1, 2, 4}

O primeiro número inicial que testaremos será o 1:
1 (ok)
1, 2 (ok)
1, 2, 3 (ok)
1, 2, 3, 1 (absurdo)

Depois, testaremos 12:
12 (ok)
12, 31 (absurdo)

Finalmente, testaremos 123:
123 (ok)
123, 124 (ok)
fim da sequência

Note que caso continuássemos, também seria válida a sequência que inicia com o número 123124, que só teria ele mesmo.

Clique aqui para conferir o código