Arara!

Solução escrita por Márcio Vitor

Vamos iterar usando um loop for ou while pelas M gaiolas e descobrir qual é a maior quantidade de araras que podem ser abrigadas.

Perceba que a primeira arara deve ir para posição 1, pois em posições mais a frentes vamos desperdiçar o espaço que está a esquerda dela que poderia ser usado para por mais araras mais a frentes. Então pulamos cinco posições e colocamos uma arara na posição 6 depois na 11, 16, 21, …. já que dessa forma garantimos que há exatamente 4 espaços entre as araras.

Enquanto fazemos isso mantemos uma variável cnt que é incrementada em uma unidade em cada iteração no final a resposta é “S” se $N \le cnt$, assim concluindo o problema com um algoritmo $O(M)$.

Clique aqui para ver o código completo.

Solução alternativa

na solução acima a $i$-ésima arara vai para gaiola $p=1+5*(i-1)=1+5i-5=5i-4$, queremos o último i tal que $5i-4 \le M \implies i \le \frac{M+4}{5}$ ou seja a quantidade de iterações será $i=\lfloor \frac{M+4}{5} \rfloor$(onde $\lfloor x \rfloor$ é $x$ arredondado pra baixo).

Portanto, similarmente, basta retornar “S” caso $N \le \lfloor \frac{M+4}{5} \rfloor$ que pode ser feito em $O(1)$.

Nota: o operador “/” do c++ já arredonda pra baixo quando se trabalha com divisão de inteiros

Clique aqui para ver o código completo.

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.

Feira de artesanato (p1-pS)