Receita Revolucionária
Solução escrita por Levi Oliveira
Conhecimentos necessários:
Seja $$P$$ quantidade de pães e $$O$$ a quantidade de ovos. Por dia, Murilo come exatamente $$2$$ pães e $$4$$ ovos.
Se ele só comesse pães, a quantidade de cafés da manhã que ele conseguiria fazer seria $$\left\lfloor \frac{P}{2} \right\rfloor$$.
Se ele só comesse ovos, a quantidade de cafés da manhã que ele conseguiria fazer seria $$\left\lfloor \frac{O}{4} \right\rfloor$$.
Como em um café da manhã completo ele precisa comer pães e ovos, a resposta será o mínimo entre $$\left\lfloor \frac{P}{2} \right\rfloor$$ e $$\left\lfloor \frac{O}{4}\right\rfloor$$. Para computar esse valor, podemos ou usar a função $$min(a, b)$$ da biblioteca <algorithm>, a qual compara dois valores e retorna o menor deles, ou guardar dois valores em variáveis auxiliares e imprimir o menor usando ifs.
Clique aqui para ver o código completo.
Encontro de Amigas
Solução escrita por Márcio Vitor
Conhecimentos necessários:
Subtarefa 2 – ($$A_1 = A_2$$):
Perceba que a resposta é no máximo 1 pois Ana permanecera apenas 1 dia no Brasil, então basta checar se esse dia esta dentro dos outros dois intervalos de tempo, se sim retorne 1, caso contrario retorne 0.
Para verificar se um tempo x esta dentro de um intervalo $$[L,R]$$ basta checar se $$x >= L$$ e $$x <= R$$.
Subtarefa 3 – (sem restrições adicionais):
Usando as ideias da subtarefa 2, vamos manter um contador $$cnt$$, e iremos iterar pelos possíveis dias $$D$$ de 1 a 31 e ver se ele esta dentro de todos os intervalos que as garotas estarão no Brasil, se sim adicionamos 1, ao final de tudo $$cnt$$ será a resposta.
Clique aqui para ver o código completo.
Mercadinho
Solução escrita por Malu Azevedo
O problema nos pede o menor tempo em segundos para que todos os idosos () fiquem no início da fila. A cada segundo, múltiplos idosos podem dar um passo à frente simultaneamente, desde que ultrapassem uma pessoa jovem ().
Ideia Central
A observação crucial para resolver este problema de forma ótima é notar que um idoso nunca é atrasado por outro idoso de modo a gastar segundos adicionais.
Como todos os idosos elegíveis se movem ao mesmo tempo, se houver um bloco de idosos juntos, eles se deslocam para a frente em “bloco” assim que o primeiro idoso desse grupo encontrar e ultrapassar um jovem. Portanto, o tempo que um idoso leva para chegar à sua posição final depende única e exclusivamente da quantidade de jovens que estão inicialmente à sua frente.
Se um idoso possui J jovens à sua esquerda na fila original, ele precisará de exatamente J segundos para ultrapassar todos eles.
Como todos os movimentos ocorrem em paralelo, o tempo total necessário para organizar toda a fila será determinado pelo idoso que estiver na pior situação possível. Logo, a resposta é o máximo de jovens à frente de qualquer idoso. Caso não haja nenhum idoso na fila, a resposta é 0.
Subtarefa 2 – (40 pontos)
Com um limite de pequeno, uma solução que simule o processo segundo por segundo (realizando as trocas no vetor manualmente até que nenhum idoso precise se mover) é aceitável. Uma simulação direta custaria no máximo operações, o que roda tranquilamente dentro do tempo para .
Subtarefa 3 – Existe um único idoso na fila (20 pontos)
Como há apenas um idoso, basta percorrer a fila até encontrá-lo. Todas as pessoas antes dele serão obrigatoriamente jovens. Portanto, a resposta é simplesmente o número de elementos avaliados antes de achar o idoso (o seu índice 0-indexado). Resultando em uma complexidade
Subtarefa 4 – Nenhuma restrição adicional ()(40 pontos)
Para garantir os 100 pontos, precisamos de uma abordagem linear . Utilizando a nossa ideia central, podemos resolver o problema em uma única passada pelo vetor:
Mantemos um contador jovens=0 e uma variável tempomax=0.
Percorremos a fila do início ao fim:
- Se a pessoa atual for jovem, incrementamos
jovens. - Se a pessoa atual for idosa, ela precisará passar por todos os jovens acumulados até ali. Atualizamos
tempomax = max(tempomax, jovens).
Ao final da leitura, tempomax terá a resposta correta.