OBI 2025 – Fase 1 Nível 2

Festa Junina

Solução escrita por Gustavo Nogueira Mendes

Conhecimentos prévios necessários:

O problema consiste em saber o menor caminho que sai de um ponto na reta (a escola), passa por outros dois pontos na reta (a lojinha e o supermercado) e volta ao ponto inicial (escola).

Primeiro, podemos notar que precisamos conseguir calcular a distância percorrida ao ir de um ponto a outro da reta. Então, criaremos uma função que fará isso. Note que há dois casos ao calcular a distância de A até B:

  • Se A está à esquerda de B (A < B), a distância é B – A
    • ex: A = 3, B = 5. distância = 5 – 3 = 2
  • Se A está à direita de B (A > B), a distância é A – B
    • ex: A = 7, B = 4. distância = 7 – 4 = 3

Agora que já temos essa função, podemos quebrar em dois casos e ver o melhor (de menor distância):

  • Caso 1: escola -> lojinha -> supermercado -> escola
  • Caso 2: escola -> supermercado -> lojinha -> escola

Clique aqui para ver o código completo.

Solução avançada

Podemos tornar a solução anterior mais curta ao conhecer um pouco mais dos recursos do c++. No caso, podemos notar que a distância entre dois pontos na reta é o valor absoluto (que pode ser calculado com a função abs) da diferença dos dois pontos. Além disso, ao pegar o “melhor” dos dois casos ao final, estamos pegando o de menor distância, que pode ser calculado com a função min, que retorna o mínimo entre dois valores.

Clique aqui para ver o código

Dieta

Solução escrita por João Pedro Castro

Conhecimentos necessários:

A ideia do problema é usar de um loop (while ou for) para passar por cada uma das N linhas e ao fim de cada refeição somar a uma variável T (começa como 0) que criamos o total de calorias nela, que é 4 \cdot P + 9 \cdot G + 4 \cdot C. Ao fim vamos imprimir M - T, que a é quantidade que ela ainda pode comer (o que falta para T chegar em M). Note que esse valor nunca vai ser negativo, já que pelas restrições o total de calorias na listas de refeições (que chamamos de T) não é maior que M.

Clique aqui para ver o código completo.

Cafeteria

Solução escrita por Otávio Pinheiro

Conhecimentos necessários:

Vamos iterar (fazer um loop usando for ou while) sobre todos os volumes de café possíveis, isto é, 0 \leq VolumeDeCafe \leq C .
Agora, sabemos que se a quantidade de leite estiver entre A e B, inclusive, teremos uma resposta válida e, então, podemos parar e dizer que encontramos uma resposta válida.
Como passamos por todo múltiplo de D de 0 a C, a nossa complexidade final é O(C \div D).

Curiosidade

Vamos comentar uma solução O(1) para esse problema.
O volume de leite é C - D \cdot x. Sabemos que A \leq C - D \cdot x \leq B, logo, (C - B) \leq D \cdot x \leq (C - A).
Queremos, então, saber se existe algum múltiplo de D no intervalo [C-B, C-A]. Para isso, deve-se cumprir o seguinte: \left\lceil \frac{(C - B)}{D}\right\rceil\times D \leq (C - A), e caso contrário, não existirá. Essa condição é verdadeira pois \left\lceil \frac{(C - B)}{D}\right\rceil\times D é o menor múltiplo de D maior ou igual a (C-B).

Clique aqui para ver o código completo.

Gráfico de Barras

Solução escrita por Márcio Vitor

Conhecimentos necessários:

Para esse problema, basta inicializar e preencher uma matriz, que representa o gráfico de barras, exatamente como o enunciado diz.

Perceba que a altura da matriz será exatamente igual a maior quantidade de votos entre os brinquedos e portanto o problema pode ser resolvido com o seguinte algoritmo:

  1. Inicialize m como uma matriz de dimensões HxN com 0’s, onde H é a maior contagem de votos entre os brinquedos

2. Percorra cada índice j da lista A de popularidade dos brinquedos. Para cada j, marque com 1 as últimas A[j] posições da coluna j de m, ou seja, as posições m[i][j] para todo H - A[j] \leq i \leq H - 1

Clique aqui para ver o código completo.