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.
Elevador
Solução escrita por Levi Oliveira
Seja $$N$$ o número de elevadores e $$A_1, A_2, A_3, \dots, A_n$$ os andares pelos quais temos que passar. Inicialmente, note que demoramos 1 segundo para percorrer 1 andar, então caso percorramos $$k$$ andares, demoraremos $$k$$ segundos para realizar tal façanha.
Agora suponha que estamos no andar $$A_i$$ e que queremos ir pro andar $$A_{i+1}$$.
Se $$A_i < A_{i+1}$$, nós precisaremos subir andares. A quantidade de andares que subiremos será $$A_{i+1} – A_i$$, o que, como vimos, leva $$A_{i+1} – A_i$$, segundos.
Se $$A_i > A_{i+1}$$, nós precisaremos descer andares. A quantidade de andares que desceremos será $$A_i – A_{i+1}$$, o que, como vimos, leva $$A_i – A_{i+1}$$, segundos.
Note que nos dois casos, a quantidade de andares que nos deslocamos – e portanto a quantidade de tempo que levou – é o módulo de $$A_i – A_{i+1}$$, isso é, o valor positivo. Para computar esse valor, podemos usar a função $$abs(valor)$$ da biblioteca cmath do C++, que retorna o módulo de um valor dado.
Assim, guardamos uma variável resp que guarda o tempo necessário para nos locomovermos entre os andares, e para cada i entre $$0$$ e $$n-2$$ – vetor 0-indexado -, incrementamos em resp $$abs(A_i – A_{i+1})$$
Clique aqui para ver o código completo.
Restaurante
Solução escrita por Theo Sampaio
Conhecimentos necessários:
Esse problema pode ser resolvido usando um algoritmo guloso para agrupar os grupos em mesas de forma ótima.
Deixe que $$ans$$ seja a quantidade de mesas necessárias para agrupar todos os grupos, e as variáveis $$G_1$$ a $$G_4$$ o número de grupos de cada tipo.
Parcial 1 – Todos os grupos são de tamanho 1 ($$G_2$$, $$G_3$$, $$G_4$$ = 0) (20 pontos)
Sabemos que a divisão de um número $$n$$ por outro número $$k$$ representa quantos grupos de tamanho $$k$$ cabem em $$n$$. Logo, $$\frac{G_1}{4}$$ representa o número de mesas necessárias para alocar os clientes, desde que arredondado para cima. Como a divisão no C++ arredonda para baixo, usamos a seguinte identidade:
$$\Large
\left\lceil \frac{n}{k} \right\rceil
=
\left\lfloor \frac{n+k-1}{k} \right\rfloor
$$
E a resposta é, então:
$$(G_1 + 3)/4$$
Parcial 2 – Sem restrições adicionais
É trivial que os grupos de 4 pessoas deverão ocupar mesas inteiras, logo somamos $$G_4$$ a $$ans$$. Além disso, como um grupo não pode ser dividido entre mesas, grupos de 3 pessoas necessariamente ocupam uma mesa também, desde que contabilizemos o número de espaços vazios, que poderão ser usados por grupos de 1 pessoa posteriormente.
Grupos de 2 pessoas, por sua vez, podem ser pareados com grupos de 2 pessoas. Caso o número de grupos de 2 pessoas seja ímpar, teremos uma mesa com 2 lugares sobrando também.
Logo, podemos agrupar os grupos de 1 nas mesas com sobra, e caso ainda tenham grupos de 1 pessoa, alocamo-los em mesas usando o resultado da parcial 1. Para isso, definimos $$K$$ como a quantidade de grupos de 1 pessoa que ainda restam após preencher todos os lugares vagos.
Isso pode ser resumido com as seguintes operações:
$$K = \max\left(0,\:G_1\:-\:G_3\:-\:2*(G_2\:\bmod\:2)\right)$$
$$ans = G_4 + G_3 +\left\lceil \frac{G_2}{2} \right\rceil + \left\lceil \frac{K}{4} \right\rceil$$