Arara!
Solução escrita por Márcio Vitor
Conhecimentos Necessários:
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
Conhecimentos necessários:
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
Conhecimentos necessários:
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)
Solução escrita por Gustavo Nogueira Mendes
Conhecimentos prévios necessários:
- STL: pair e set / multiset
- Artigo sobre multiset
- obs: para remover é usado para um multiset
s: s.erase(s.find(valor));porques.erase(val);em um multiset apaga todas as ocorrências e queremos apagar apenas uma, então usamos os.find(valor), que retorna um iterator, fazendo apenas um elemento ser apagado, como ems.erase(s.begin()), pois os.begin()é um iterator que referencia o primeiro elemento.
O problema consiste em descobrir uma informação (o somatório do preço dos produtos vendidos) relacionada a um estoque / conjunto de $$N$$ produtos (com dado tipo e preço, que podem se repetir) que sofre $$C$$ alterações. As alterações são de dois tipos:
- 1: Venda do produto de menor preço
- 2: Venda do produto de menor preço de um tipo específico
Como a quantidade de alterações é relativamente grande, notamos que a dificuldade é encontrar uma estrutura eficiente para manter esse conjunto (o estoque) e lidar com as alterações.
Em específico, precisamos manter tanto uma estrutura para descobrir o menor preço de todos os produtos, quanto descobrir o menor preço dentre os produtos de um determinado tipo. Note que uma estrutura não irá interferir na outra, basta usar uma para pesquisar o produto e apagá-lo em ambas.
As nossas estruturas serão:
- Um multiset guardando todos os produtos, com um par de preço (valor pelo qual queremos ordenar os produtos) e tipo (não importa sua ordem, mas precisamos dessa informação para identificar o produto e apagá-lo na outra estrutura). Ele será usado para responder queries do tipo 1.
- Uma lista, onde a posição $$i$$ será um multiset guardando o preço (valor pelo qual os produtos serão ordenados) dos produtos do tipo $$i$$. Note que ao buscar o produto que será “resposta” (será vendido) de uma query do tipo 2, teremos seu tipo e preço, conseguindo indentificá-lo na estrutura 1.