종이 접기

면접 대비

시간 제한2초메모리 제한512 MB

요약

W×H 종이를 한 변에 평행하게 접을 때마다 그 변의 길이가 두 조각 중 긴 쪽으로 줄어든다. 넓이가 정확히 A가 되는 최소 접기 횟수를 구하고, 불가능하면 -1을 출력한다.

난이도: 보통10점 중 6점
유형: 수학, 그리디, 정수론, 구현
정답자: 아직 제출이 없습니다

문제

W×H 크기의 직사각형 종이가 있다. 현정이에게 필요한 종이는 넓이가 A인 종이다. 그래서 이 종이를 접어서 넓이가 A인 종이를 만들려고 한다.

종이는 직선을 기준으로 접으며, 다음 두 조건을 지켜야 한다.

접는 기준선은 직사각형의 한 변과 평행하다.
접은 뒤에도 가로 길이와 세로 길이가 모두 정수다.

가로 길이가 $w$ 인 종이를 세로 방향 기준선에서 접으면 가로가 길이 $x$ 와 $w-x$ 인 두 조각으로 나뉘고, 접은 뒤의 가로 길이는 더 긴 쪽인 $\max(x, w-x)$ 가 된다. 세로 길이를 접을 때도 같은 방식이다. 접은 종이는 다시 직사각형이 되고, 접지 않은 쪽 길이는 그대로다.

예를 들어 5×3 종이를 가로 4가 되는 선에서 접으면 4×3 종이가 된다. 같은 5×3 종이를 세로 1이 되는 선에서 접으면 5×2 종이가 된다.

W, H, A가 주어졌을 때 넓이가 A인 종이를 만들 수 있는지 판정하고, 만들 수 있으면 접어야 하는 횟수의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 W, H, A가 공백으로 구분되어 주어진다. ( $1 \le W, H \le 10^9$ , $1 \le A \le 10^5$ )

출력

W×H 크기의 종이를 접어서 넓이가 A인 종이를 만들 수 있으면 접는 횟수의 최솟값을, 만들 수 없으면 -1을 출력한다.

예제6

예제 1
입력
```
5 3 12
```
예상 출력
```
1
```
예제 2
입력
```
2 2 3
```
예상 출력
```
-1
```
예제 3
입력
```
4 4 1
```
예상 출력
```
4
```
예제 4
입력
```
127 129 72
```
예상 출력
```
8
```
예제 5
입력
```
1 100000 100000
```
예상 출력
```
0
```
예제 6
입력
```
1 1 2
```
예상 출력
```
-1
```