Month to Reach a Growth Target

Source: Phước Hưng OJ

Version: Phuoc Hung OJ Extended

Problem Statement

An initial amount of capital is $v$. At the end of each month, it grows by $p$ percent of its value at the beginning of that month; each increase is reinvested before the next month. Find the smallest number of months $k$ from $0$ through $1000$ such that the capital after $k$ months is at least the target $T$. If the initial amount already meets the target, the answer is $0$. If it is still below the target after $1000$ months, print $-1$.

Input

One line contains three real numbers $v$, $T$, and $p$: the initial capital, the target, and the monthly percentage growth rate, in that order.

Output

Print one integer: the minimum $k$ with $0\le k\le1000$ and capital after $k$ months at least $T$; print $-1$ if no such $k$ exists.

Subtasks

• Subtask 1 (20%): $0\le v,T\le10^6,\ T\le v,\ 0<p\le100$.
• Subtask 2 (30%): $0\le v,T\le10^6,\ 1\le p\le100$.
• Subtask 3 (50%): $0\le v,T\le10^6,\ 0<p\le100$.

Examples

Example 1

Input:

100 121 10

Output:

2

Explanation: At month $0$, the capital is $100<121$. After month $1$ it is $110$. After month $2$ it is $121$, meeting the target for the first time. Print $2$.

Example 2

Input:

150 100 5

Output:

0

Explanation: The initial amount $150$ is already at least $100$, so no month is needed.

Example 3

Input:

0 1 100

Output:

-1

Explanation: The capital remains $0$ after every month, so it never reaches $1$ within $1000$ months.