OBI 2022 - Fase 2 - Programação Nível 1

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.

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

Tanque de Combustível

Escrito por Vitor Veiga

Conhecimento prévio necessário:

Números Decimais

No problema queremos calcular quanta gasolina é preciso comprar para concluir uma viagem. São dados o número de quilômetros por litro de gasolina $C$ , quantos quilômetros faltam para chegar no destino $D$ , e quantos litros de gasolina já estão no tanque $T$ . Assim, é fácil ver que a parte mais difícil desse problema é a matemática. Achando a fórmula para a resposta, o código fica muito simples.

Temos que o número de quilômetros que conseguimos rodar sem comprar nada de combustível, ou seja, o que conseguimos rodar só com o combustível que já está no tanque, será igual a $C * T$ . Agora, basta calcular quantos quilômetros faltam tirando os que já podem ser rodados com o tanque e depois converter esse valor para litros dividindo o resultado por $C$ .

Terminaremos com a seguinte equação: $\frac{D - (C*T)}{C}$ , quantos quilômetros faltam para chegar ao destino menos a quantidade de quilômetros que podemos correr sem comprar combustível dividido pela quantidade de quilômetros que são corridos com um litro. Caso seja possível percorrer todo o percurso só com a gasolina que já está no tanque, não é preciso comprar mais nada.

Clique aqui para conferir o código.

Câmeras

Escrito por Enzo Dantas

Conhecimento prévio necessário:

Busca em grafos

Primeiramente, iremos construir a matriz $N\times{M}$ e marcar quais posições são vigiadas por câmeras e quais estão livres. Se uma câmera posicionada em $(i, j)$ está apontada para o Oeste, por exemplo, vamos marcar todas as posições a direita de $(i, j)$ como vigiadas (todas as posições $(i, k)$ $|$ $j\leq{k}\leq{N}$ ). Em seguida, vamos fazer uma DFS começando do $(1, 1)$ e vamos conferir se a DFS chega na posição $(N, M)$ .

Confira o código