OBI 2025 – Fase 2 Nível 2

Placar do Jogo

Solução escrita por Julia Tiosso

Nesse problema, são dadas duas listas com os momentos em que Paulo e Camila marcaram gol ao longo de um jogo, em ordem crescente. O objetivo é determinar a situação do placar após cada gol.

Dado isso, e considerando que o problema garante que não há dois gols no mesmo instante, podemos pensar em utilizar um vetor de marcação, indicando, para cada minuto, quem fez o gol.

Assim, inicialmente passamos pelos minutos dos gols de Paulo e marcamos todos eles com o valor $1$. Em seguida, fazemos o mesmo com Camila, marcando o valor $2$. Ao final, podemos fazer a simulação do jogo e, para cada minuto $t$ em que houve gol, atualizamos a pontuação do respectivo jogador e imprimimos o placar atual.

A complexidade dessa solução é $O(max_t)$, pois percorremos todos os minutos possíveis.

Clique aqui para ver o código completo.

Solução alternativa:

Há ainda uma outra maneira interessante de resolver esse problema, utilizando a ideia de manter “dois ponteiros”:

• $l$, apontando para o último gol de Paulo
• $r$, apontando para o último gol de Camila

Enquanto ainda tiverem gols a serem processados, podemos comparar os tempos de Paulo e Camila e decidir quem marcará o próximo gol. Após isso, atualizamos o devido ponteiro e a pontuação do jogador.

Dessa forma, como cada ponteiro avança $P$ ou $C$ posições no total, esse algoritmo tem complexidade $O(P + C)$.

Clique aqui para ver o código completo.

Mania de Ímpar

Solução escrita por Pedro Rey

Primeiro, vamos analizar quais propriedades uma bandeja deve ter para que ela seja organizada. Considere duas posições adjacentes na matriz. Como a soma delas é ímpar, isso significa que as duas posições tem paridades diferentes. A partir disso, é facil ver que $G_{i, j} \equiv i + j + G_{1, 1} (\text{mod $2$})$. Ou seja, as paridades das casas da matriz formam um “xadrez”.

Note que só há dois modos de escolher as paridades das posições de uma matriz organizada, e estas são dependentes na paridade de $G_{1, 1}$. Vamos testar as duas alternativas. Para cada posição em que a paridade é diferente da paridade desejada, adicionamos um para alterar a paridade. Agora, basta escolher a menor quantidade de gotas necessarias dentre os dois modos de escolher as paridades.

Clique aqui para ver o código completo.

Um Desafio Muito Distinto

Solução escrita por Otávio Pinheiro

Vamos resolver cada partida como sendo uma query independente.

A primeira observação que vamos fazer para resolver esse problema é que a decisão ótima é sempre pegar o menor inteiro disponível no intervalo para ser o próximo. Para qualquer $x$, tal que $A \leq x \leq B$ vamos sempre pegar um intervalo $[A, x]$. Veja também que a soma dos valores em $[a, b]$, por P.A (Progressão Aritmética), será $\frac{(b + a)(b - a + 1)}{2}$.

Note que, se $x < B$ e a soma dos valores em um intervalo $[A, x]$ for menor que $L$, então certamente será possível pegar o intervalo $[A, x + 1]$. Portanto, podemos fazer uma binary search que encontra o maior valor de $x$ válido.

Clique aqui para ver o código completo.

Feira de artesanato (p1-pS)