Martelo do Veigola
Comentário escrito por Arthur Lobo
Conhecimento prévio necessário:
Digamos que, depois de realizar as trocas, terminamos tendo $$D’$$ diamantes e $$G’$$ gravetos, então a quantidade de martelos que podem ser feitos seria $$min(\floor{D’/6},G’)$$, portanto, é isso que queremos maximizar.
A ideia vai ser passar por todos os pares $$D’,G’$$ possíveis de serem alcançados. Já que ambos $$D$$ e $$G$$ são menores ou iguais a $$100$$ e é fácil ver que serão feitas somente trocas de um dos dois tipos, podemos testar todas as quantidades de trocas de cada tipo.
Se realizamos $$x$$ trocas gravetos $$\rightarrow$$ diamante, então $$G’ = G-4*x$$ e $$D’ = D+x$$. Perceba que se algum dos dois virarem negativos, então $$min(\floor{D’/6},G’)$$, portanto não precisamos nos preocupar com números negativos.
Fazer $$x$$ trocas diamante $$\rightarrow$$ gravetos é a mesma coisa de fazer $$-x$$ trocas gravetos $$\rightarrow$$ diamante, então basta chegarmos o maior valor de $$min(\floor{D’/6},G’)$$ ao realizarmos $$x$$ trocas, para todo $$-100 \le x \le 100$$, o que pode ser feito com um for.