Festa Junina
Solução escrita por Gustavo Nogueira Mendes
Conhecimentos prévios necessários:
O problema consiste em saber o menor caminho que sai de um ponto na reta (a escola), passa por outros dois pontos na reta (a lojinha e o supermercado) e volta ao ponto inicial (escola).
Primeiro, podemos notar que precisamos conseguir calcular a distância percorrida ao ir de um ponto a outro da reta. Então, criaremos uma função que fará isso. Note que há dois casos ao calcular a distância de A até B:
- Se A está à esquerda de B (A < B), a distância é B – A
- ex: A = 3, B = 5. distância = 5 – 3 = 2
- Se A está à direita de B (A > B), a distância é A – B
- ex: A = 7, B = 4. distância = 7 – 4 = 3
Agora que já temos essa função, podemos quebrar em dois casos e ver o melhor (de menor distância):
- Caso 1: escola -> lojinha -> supermercado -> escola
- Caso 2: escola -> supermercado -> lojinha -> escola
Solução avançada
Podemos tornar a solução anterior mais curta ao conhecer um pouco mais dos recursos do c++. No caso, podemos notar que a distância entre dois pontos na reta é o valor absoluto (que pode ser calculado com a função abs) da diferença dos dois pontos. Além disso, ao pegar o “melhor” dos dois casos ao final, estamos pegando o de menor distância, que pode ser calculado com a função min, que retorna o mínimo entre dois valores.
Dieta
Solução escrita por João Pedro Castro
Conhecimentos necessários:
A ideia do problema é usar de um loop (while ou for) para passar por cada uma das $$N$$ linhas e ao fim de cada refeição somar a uma variável $$T$$ (começa como $$0$$) que criamos o total de calorias nela, que é $$4 \cdot P + 9 \cdot G + 4 \cdot C$$. Ao fim vamos imprimir $$M – T$$, que a é quantidade que ela ainda pode comer (o que falta para $$T$$ chegar em $$M$$). Note que esse valor nunca vai ser negativo, já que pelas restrições o total de calorias na listas de refeições (que chamamos de $$T$$) não é maior que $$M$$.
Cafeteria
Solução escrita por Otávio Pinheiro
Conhecimentos necessários:
Vamos iterar (fazer um loop usando for ou while) sobre todos os volumes de café possíveis, isto é, $$0 \leq VolumeDeCafe \leq C $$.
Agora, sabemos que se a quantidade de leite estiver entre A e B, inclusive, teremos uma resposta válida e, então, podemos parar e dizer que encontramos uma resposta válida.
Como passamos por todo múltiplo de $$D$$ de $$0$$ a $$C$$, a nossa complexidade final é $$O(C \div D)$$.
Vamos comentar uma solução $$O(1)$$ para esse problema.
O volume de leite é $$C – D \cdot x$$. Sabemos que $$A \leq C – D \cdot x \leq B$$, logo, $$(C – B) \leq D \cdot x \leq (C – A)$$.
Queremos, então, saber se existe algum múltiplo de D no intervalo $$[C-B, C-A]$$. Para isso, deve-se cumprir o seguinte: $$\left\lceil \frac{(C – B)}{D}\right\rceil\times D \leq (C – A)$$, e caso contrário, não existirá. Essa condição é verdadeira pois $$\left\lceil \frac{(C – B)}{D}\right\rceil\times D$$ é o menor múltiplo de $$D$$ maior ou igual a $$(C-B)$$.
Gráfico de Barras
Solução escrita por Márcio Vitor
Conhecimentos necessários:
Para esse problema, basta inicializar e preencher uma matriz, que representa o gráfico de barras, exatamente como o enunciado diz.
Perceba que a altura da matriz será exatamente igual a maior quantidade de votos entre os brinquedos e portanto o problema pode ser resolvido com o seguinte algoritmo:
- Inicialize $$m$$ como uma matriz de dimensões $$H$$x$$N$$ com 0’s, onde $$H$$ é a maior contagem de votos entre os brinquedos
2. Percorra cada índice $$j$$ da lista $$A$$ de popularidade dos brinquedos. Para cada $$j$$, marque com 1 as últimas $$A[j]$$ posições da coluna $$j$$ de $$m$$, ou seja, as posições $$m[i][j]$$ para todo $$H – A[j] \leq i \leq H – 1$$