La boutique de chocolat
Il y a n personnes qui font la queue devant un magasin. Ce magasin ne vend que du chocolat. Chaque fois qu’un client entre dans la boutique, le magasin reçoit 1 kg de chocolat. Lorsque le client arrive à la caisse, ce kilogramme est déjà prêt à être vendu.
Nous connaissons la quantité de chocolat souhaitée par chacune des personnes dans la file. Si un client entre dans le magasin et qu’il n’y a pas assez de chocolat, il retourne à la fin de la file et attend son tour pour réessayer. S’il peut acheter la quantité dont il a besoin, il repart aussitôt avec son chocolat et quitte le magasin.
Vous devez déterminer combien de fois chaque personne devra entrer dans la boutique pour acheter la quantité de chocolat désirée.
Au départ, le magasin ne dispose d’aucune réserve de chocolat.
Entrée
La première ligne de l’entrée contient un entier n (1 ≤ n ≤ 10 000).
La ligne suivante contient n entiers séparés par des espaces, représentant la quantité de chocolat que chaque personne souhaite acheter: c1, c2, ..., cn (1 ≤ ci ≤ 20).
Sortie
Le programme doit afficher n entiers séparés par des espaces, indiquant le nombre de fois où chaque personne entre dans la boutique pour obtenir la quantité de chocolat voulue.
Exemples
Input | Output |
3
1 3 2 | 1 4 1 |
Explication
- Le premier client entre dans la boutique → la boutique reçoit 1 kg de chocolat ⇒ elle peut vendre ce kg immédiatement au premier client, qui repart satisfait.
- Le deuxième client se présente → la boutique reçoit 1 kg de chocolat. Le client veut 3 kg, donc il n’y en a pas assez. Il retourne donc à la fin de la file.
- Le troisième client entre → la boutique reçoit encore 1 kg de chocolat (2 kg au total) ⇒ elle peut vendre ces 2 kg au troisième client, qui quitte alors la boutique satisfait.
- Le deuxième client revient → la boutique reçoit 1 kg de chocolat. Elle n’a qu’1 kg disponible alors que le client en veut 3. Il doit ressortir.
- Le deuxième client entre à nouveau → la boutique reçoit 1 kg de chocolat. Elle n’a maintenant que 2 kg, alors que le client en veut toujours 3. Il doit repartir.
- Le deuxième client revient encore → la boutique reçoit 1 kg de chocolat (3 kg au total) ⇒ elle peut enfin vendre les 3 kg au client, qui repart satisfait.
Ainsi, le premier client est entré dans la boutique 1 fois, le deuxième client y est entré 4 fois, et le troisième client 1 fois.
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB