Aula de Matemática
Solução escrita por Márcio Vitor
Conhecimentos necessários:
Dados inteiros $$A,B$$ o problema pede o máximo entre $$A + B$$ e $$A – B$$, podemos fazer isso lendo os dois inteiros e usando a função $$max$$ da biblioteca padrão (Note que também é possível usar um $$if$$ para verificar qual o maior entre os dois).
Fichas
Solução escrita por Enzo Hirota
Conhecimentos necessários:
Usaremos o seguinte algoritmo para resolver o problema:
- Pegaremos a maior quantidade de fichas de $$R$ 10 $$
- Pegaremos a maior quantidade de fichas de $$R$ 5 $$ do que sobrou
- Pegaremos a maior quantidade de fichas de $$R$ 2 $$, do que sobrou
- Pegaremos a maior quantidade de fichas de $$R$ 1 $$, do que sobrou
Executando esses passos nesta ordem, o problema será resolvido, agora resta provar que isso funciona:
Prova: Note que os números de $$1$$ até $$4$$ podem ser escritos, como as seguintes somas de fichas:
| $$1=1$$ | $$2=2$$ | $$3=2+1$$ | $$4=2+2$$ |
Terminaremos agora com um argumento da troca, suponha que na nossa solução possuímos as seguintes quantidades de fichas para cada valor: $$q_1, q_2, q_5, q_{10}$$.
Agora suponha que solução possui menos de $$q_{10}$$ fichas de $$R$10$$, então conseguimos somar um número entre $$10$$ e $$14$$, usando apenas as fichas de valor $$1, 2$$ e $$5$$, já que enquanto a soma não superar $$10$$, podemos adicionar uma ficha, e quando for maior ou igual a $$10$$, não será maior que $$14$$, já que pode-se adicionar no máximo $$5$$ por vez, assim:
- Se a soma for exatamente $$10$$, troca por uma ficha de $$R$10$$, assim diminuindo o número de fichas
- Se a soma for entre $$11$$ e $$14$$, note que usaremos no mínimo $$3$$ fichas, então se trocarmos por uma ficha de $$R$10$$, e o que sobrar por como está escrito na tabela, trocaremos por no máximo $$3$$ fichas, assim não piorando a resposta.
Usando argumento análogo para as fichas de $$R$5$$ e $$R$2$$, provamos que nossa resposta é pelo menos tão boa, quanto a suposta resposta ótima. Desse modo provamos que realmente utilizamos a menor quantidade de fichas.
Clique aqui para ver o código completo
Solução extra: O problema, se resume essencialmente a um knapsack, o resto é deixado ao leitor, pode se ler mais sobre em Problema da Mochila, tendo um código para solução
Transporte
Solução escrita por Julia Tiosso
Conhecimentos necessários:
O algoritmo que vamos realizar consiste em tentar agrupar o máximo de estudantes possível em um mesmo transporte. Assim, garantimos que usamos a quantidade mínima de ônibus.
Dessa maneira, vamos atribuir inicialmente o primeiro ônibus ao estudante de tempo $$t_1$$. Suponha que estamos atualmente preenchendo um ônibus que começa no estudante $$j$$ e queremos decidir se o estudante $$i$$ pode entrar nesse mesmo ônibus:
- Se $$t_i$$ $$-$$ $$t_j > K$$, então o estudante $$i$$ não pode embarcar nesse transporte, pois isso implicaria que $$j$$ esperaria mais de $$T$$ segundos. Então um novo ônibus que começa no estudante $$i$$ deve ser contratado.
- Senão, $$i$$ consegue entrar nesse transporte e seguimos tentando agrupar os próximos estudantes.