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.