# UVa 11150

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