# UVa 11150

## Summary

A simulation problem with some tricks.

## Explanation

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 ${\displaystyle O(\log N)}$ 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.

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

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