1/8 ICPC Azerbaijan Qualification Preparation

Accurate Movement

Amelia is studying modeling. She is interested in models with moving parts.

As her first task, she made a rectangular box of size 2 × n, which contains two parallel rails and a rectangular bar on each of them. The short bar has size 1 × a, and the long one has size 1 × b. The long bar has a stopper at each end, and the short one is always between these two stoppers.


The bars can be moved along the rails, one bar at a time, as long as the short bar is between the stoppers. So, on each move Amelia selects one of the bars and moves it, while the other one stays in place.

Initially, both bars are aligned to one side of the box, and Amelia wants them to be aligned to the other side in as few moves as possible. What is the minimal number of moves she should do to achieve her goal?


Three integers a, b and n (1a < bn107).


The only output line should contain a single integer - the minimal number of moves Amelia needs to do.


A possible solution for the first example is shown below.


Time limit 1 second
Memory limit 128 MiB
Input example #1
1 3 6
Output example #1
Input example #2
2 4 9
Output example #2
Source 2019 ACM NEERC, Northern Subregion, October 26, Problem A