UVa 11150

From Algorithmist
Jump to navigation Jump to search

11150 - Cola[edit]

Summary[edit]

A simulation problem with some tricks.

Explanation[edit]

If we aren't allowed to borrow any bottles, then this problem is straightforward - simply simulate each stage, which will work up to very large numbers since this runs time. The trick is knowing how to optimally borrow bottles.

The "trick" is noticing that borrowing more than two bottles does not help - you would have to return the extra bottles without trading it in, and that the borrowing should be done in the beginning, since it would cascade down otherwise. With that in mind, we only need to borrow either 0, 1, or two bottles. We can easily take the best out of the three simulations.

Solutions[edit]

Input[edit]

1
2
3
4
5
6
7
8
9
10
15
20
30
40
50
100
150
190
199
200

Output[edit]


1
3
4
6
7
9
10
12
13
15
22
30
45
60
75
150
225
285
298
300