3.1 Naman the Explorer - II
Naman is back exploring the ancient underground mine. This time, he notices that the tunnels between chambers have different resistances to sound.
> Each tunnel has a weight w, meaning it reduces the strength of sound by w units when sound passes through it.
> Sound starts at strength S in the initial chamber.
> The sound can only travel to a neighboring chamber if the remaining strength is greater than 0 after passing through the tunnel.
Your task is to calculate: given a distance n (number of steps allowed), initial sound strength S, and tunnel resistance w, how many chambers in total will hear the shout?
Constraints
1 ≤ n ≤ 10^9
1 ≤ S ≤ 10^9
1 ≤ w ≤ 10^4
Input Format
A single line containing three integers:
n S w
Output Format
Output the total number of chambers that will hear the shout.
Example 1
Input:
1 10 5
Output:
7
Explanation:
Sound strength = 10. Each tunnel reduces it by 5.
Current chamber hears it.
6 neighbors also hear it since strength remains 5 after passing one tunnel
Log In to solve the Question