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.

Feirinha de Artesanato

Solução escrita por Márcio Vitor

Precisamos de uma forma rápida de saber qual é o menor preço entre cada tipo de produto vamos usar o fato de que $t_i \le 2$ e manter dois vetores ordenados em ordem decrescente $P[1]$ e $P[2]$, contendo respectivamente os preços dos item de tipo 1 e 2.

Agora fica fácil manter a variável $S$ da soma dos produtos comprados por cada cliente, se for decidido de tipo $t$: se o vetor $P[t]$ não estiver vazio remova o último elemento e adicione a $S$, caso seja indeciso verifique qual vetor tem o menor elemento no fim e remova dele caso ambos não estejam vazio.

Nota: você também pode fazer isso com outras estruturas de dados da stl como a pilha.

A complexidade final desse algoritmo é $O(N\log_2{N} + C)$.

Clique aqui para ver o código completo.