C+= (C+=)

Nguồn: Codeforces

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho hai số nguyên dương $a,b$ và ngưỡng $n$ với $a,b\le n$. Mỗi thao tác, bạn chỉ được chọn một trong hai phép: a += b hoặc b += a. Hãy tìm số thao tác ít nhất để ít nhất một trong hai số trở nên lớn hơn hẳn $n$. Có thể đạt ít bước nhất bằng cách luôn cộng số lớn hơn vào số nhỏ hơn, rồi tăng số thao tác. Ví dụ $a=1,b=2,n=3$ cần 2 bước.

Input

Một dòng chứa đúng ba số nguyên $a,b,n$; $1\le a,b\le n\le10^9$. Bản PHOJ xử lý một bộ $(a,b,n)$, không có số lượng bộ thử $t$ ở đầu.

Output

In số thao tác ít nhất.

Subtask

• Subtask 1 (20%): $1\le a,b\le n\le 20$.

• Subtask 2 (30%): $1\le a,b\le n\le 100000$.

• Subtask 3 (50%): $1\le a,b\le n\le 1000000000$.

Ví dụ

Ví dụ 1

Input:

1 2 3

Output:

2

Giải thích:

Ngưỡng n=3. Các trạng thái (a,b) sau mỗi bước: 1: (3,2); 2: (3,5). Sau 2 bước, ít nhất một giá trị >n.

Ví dụ 2

Input:

5 4 100

Output:

7

Giải thích:

Ngưỡng n=100. Các trạng thái (a,b) sau mỗi bước: 1: (5,9); 2: (14,9); 3: (14,23); 4: (37,23); 5: (37,60); 6: (97,60); 7: (97,157). Sau 7 bước, ít nhất một giá trị >n.