Bonjour à tous,
Depuis quelques temps je m’amuse un peu avec les Battle de code sur Condingame.
Ce matin le sujet était le suivant :
Machines produce gold. Every machine costs C gold to buy and then produces P gold per turn, starting the next turn after it is bought. You start at turn 0 with 1 machine and 0 gold. You can buy as many machines as you can afford. What is the maximum amount of gold you can reach at turn 100 ?
Ex : C = 10 and P = 1 At turn 1 you have 1 gold … 2 gold at turn 2 … 3 gold at turn 3… If you buy another machine at turn 10, you end up with 0 gold at turn 10 (because you spent 10) At turn 11 you’ll have 2 gold (because both machines produce 1) Producing 2 gold from turn 11 to 100, you’ll end up with 180 gold. But you can certainly do better…
Naïvement, et un peu pressé par le temps (on a 15mn pour résoudre), je me dis : c’est simple, il suffit que j’achète le maximum de machines.
Sauf qu’après quelques temps, je me rends compte qu’en faisant ça, certes ma production de Gold augmente très fortement, mais mon stock lui reste très faible. Ce qui fait que je ne réponds pas à la question, à savoir optimiser le nombre de Gold dont on dispose au tour 100.
Naïvement encore, je me dis qu’il faut peut-être arrêter d’acheter un tour avant pour laisser la production maximale se faire. Mais non, je suis largement en deçà de ce qu’il faut trouver (avec les paramètres C = 10 et P = 1, il fallait trouver 39 000 gold et des poussières).
Je ne trouve donc pas la solution, et à la fin, je regarde le programme du premier. Il est le suivant :
I=input
c=int(I())
p=int(I())
m=1
g=0
for i in range(100):
g+=m*p
if (100-i-1)*p>c:
x=g//c
g-=x*c
m+=x
print(g)
Je comprends donc que tout tien dans la condition (100 - i - 1) * p > c, le reste est tout à fait identique à mon approche naïve. Mais impossible de comprendre d’où vient cette condition.
Quelqu’un pourrait-il m’aider ? J’ai l’impression que c’est un problème assez classique, et je suis curieux d’en savoir plus !
Merci d’avance 
