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).
Dança de Quadrilha
Solução escrita por Otávio Pinheiro
Conhecimentos necessários:
Perceba que a direção do movimento de Elena alterna após cada anúncio do marcador. Ou seja, o primeiro movimento é marcado no sentido horário, o segundo no anti-horário, e assim sucessivamente.
Como Elena percorre 1 metro por segundo, a distância percorrida em cada movimento é exatamente igual ao intervalo de tempo correspondente. Dessa forma, podemos representar os movimentos no sentido horário como valores positivos e os movimentos no sentido anti-horário como valores negativos.
O problema também pede para imprimir a resposta final como módulo, então devemos retornar .
O código para implementar isso consta manter um inteiro S e iterar de 0 à N, sendo que se o iterador estiver em uma posição par iremos incrementar em S e, caso contrário, estiver numa posição ímpar, vamos decrementar em S.
Finalmente retornamos usando a função . Como percorremos o vetor apenas uma vez, a complexidade de tempo da solução é
Clique aqui para ver o código completo
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