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:
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