Un problème d'optimisation

L’auteur de ce sujet a trouvé une solution à son problème.
Auteur du sujet

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 :)

+0 -0

Cette réponse a aidé l’auteur du sujet

En gros, à chaque tour cette condition sert à décider si acheter de nouvelles machines sera rentable ou non.

Une machine sera rentable si elle produira plus d’or qu’elle n’en a coûté : (100-i-1) * p est la quantité d’or qu’aura produit une machine achetée à l’itération i au 100e tour.

Si c’est rentable, alors il achète autant de machines que possible.

Édité par nohar

I was a llama before it was cool

+0 -0
Connectez-vous pour pouvoir poster un message.
Connexion

Pas encore membre ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte