The Chocolate Store
npeople standing in front of a store. The store sells only chocolates. Every time a client enters the chocolate store, the store receives 1kg of chocolate. By the time the client approaches the cashier, they can already sell that 1kg.
We know how much chocolate each of the people in the line wants. If a person enters the store and there isn’t enough chocolate, they get to the very end of the line and wait to get inside again. If they buy the chocolate, they get it and leave the store.
You are asked to find the number of times each person will enter the shop to buy the desired amount of chocolate.
Initially, the store has no chocolate.
The first line of the input contains a single integer
n(1 ≤ n ≤ 10 000).
The next line contains
nspace-separated integers representing the amount of chocolate each person needs
(1 ≤ ≤ 20).
The program should print
nspace-separated integers representing the number of times each person will enter the shop.
3 1 3 2
1 4 1
- The first customer enters the store → the store gets 1kg of chocolate ⇒ they can sell 1kg to the first customer, so the customer leaves satisfied.
- Then the second customer approaches → the store gets 1kg of chocolate. Yet, the customer wants 3kg, so he gets back to the end of the queue.
- The third customer enters the store → the store gets another 1kg of chocolate (2kg in total) ⇒ they can sell 2kg to the customer, so the customer leaves satisfied.
- Then the second customer enters again → the store gets 1kg of chocolate. The store only has 1kg, while the customer wants 3. So, the customer gets out of the store.
- The second customer enters the store again → the store gets 1kg of chocolate. The store only has 2kg now, while the customer wants 3kg. So, the customer gets out again.
- The second customer enters the store again → the store gets 1kg of chocolate (3kg in total) ⇒ they sell 3kg to the customer and the customer leaves satisfied.
So, the first customer entered the store only 1 time. The second customer entered the store 4 times, while the third one entered the store once.
Time limit: 1 seconds
Memory limit: 512 MB
Output limit: 1 MB