OBI 2022 - Fase 2 - 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.

Troféu

Escrito por Vitor Veiga

Conhecimento prévio necessário:

Dadas cinco pontuações em uma competição, queremos saber o número de competidores empatados com a maior pontuação e com a segunda maior pontuação. Assim, teremos que achar o valor dessas duas pontuações, utilizando um loop, e depois checar quantos participantes obtiveram cada uma delas.

Ordenando o vetor dos valores em ordem decrescente, a primeira posição será o maior número, e o segundo maior será o primeiro número do vetor diferente do maior. Basta agora contar quantas vezes esses valores se repetem utilizando um simples loop, e depois retornar essas quantidades.

Confira o código.

Caminho

Escrito por Arthur Lobo

Conhecimento prévio necessário:

Loops

Para sabermos se o trecho de $i$ até $i+1$ está escuro, podemos testar se $P_i+P_{i+1} < 1000$ , e para o trecho de $n$ até $1$ , basta checarmos se $P_N+P_1 < 1000$ .

Primeiros vamos checar trechos escuros que vão desde um poste $A$ até um poste $B$ , com $A < B$ , ou seja, não passa pelo trecho do poste $N$ até o $1$ . Para esse caso, vamos iterar pelos postes da esquerda para direita e manter uma variável $consecutivos$ e $resposta$ que guardará a quantidade de trechos escuros consecutivos até $i$ . Quando $P_{i-1}+P_{i} < 1000$ , aumentamos o valor de $consecutivos$ em $1$ ; e quando $P_{i-1}+P_{i} \geq 1000$ , fazemos $resposta = max(resposta,consecutivos)$ e $consecutivos = 0$ .

O segundo caso é quando os trechos escuros consecutivos passam pelo trecho de $n$ até $1$ . Nesse caso, vamos primeiro checar se $P_N+P_1 < 1000$ . Se sim, então veremos qual a maior quantidade de trechos consecutivos escuros começando em $1$ , chamaremos esse número de $comeco$ , e qual a maior quantidade de trechos consecutivos escuros terminando em $n$ , chamaremos esse número de $fim$ . Estão uma das possibilidades de resposta é $comeco+fim+1$ , e computamos ela fazendo $resposta = max(resposta,comeco+fim+1)$ .

Clique aqui para ver o código.

Pirâmide

Escrito por Enzo Dantas

Conhecimento prévio necessário:

Ao visualizar a pirâmide em 3D, a ideia mais intuitiva é construir a pirâmide camada por camada. Começamos pela base da pirâmide e vamos subindo, adicionando um bloco em cada posição de cada camada. Cada camada tem cerca de $N^2$ blocos e temos $N/2$ camadas, então a complexidade final fica $O(N^3)$ . Como $N=100$ , essa solução é rápida o suficiente.

Confira o código para melhor entendimento

Entretanto, existe uma solução mais rápida em $O(N^2)$ . É interessante que o leitor tente achar essa solução antes de ler o restante do editorial. Ao analisar casos pequenos, percebe-se o seguinte padrão: a altura de uma posição qualquer é a a distância da posição a uma das quatro bordas da pirâmide (a menor entre as quatro distâncias). O código consiste em percorrer todas as posições e fazer o mínimo entre as 4 distâncias.

Confira o código para melhor entendimento