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