문제
우주왕자 VITAS는 지구인들과 친해지기 위해 사교파티를 열었다. VITAS는 포도주 $A$병과 빵 $B$개를 가지고 있고, 포도주 한 병을 빵 한 개로 바꾸거나 빵 한 개를 포도주 한 병으로 바꾸는 마법을 최대 $K$번 부릴 수 있다.
VITAS는 초대한 모든 지구인에게 각각 동일한 수의 포도주와 빵을 나눠 줄 것이다. 한 종류를 아무에게도 나눠 주지 않는 것도 가능하다. 단, 포도주와 빵을 나눠주고 난 뒤 남은 것이 있으면 안 된다.
VITAS가 위 조건을 만족시키면서 초대할 수 있는 지구인의 수의 최댓값을 구하여라.
입력
첫째 줄에 정수 $A$, $B$, $K$가 공백을 사이에 두고 주어진다. $(1 \le A, B, K \le 10^{10})$
출력
VITAS가 조건을 만족시키면서 초대할 수 있는 지구인의 수의 최댓값을 출력한다.
예제 입력 1
3 9 1
예제 출력 1
4
빵 $1$개를 포도주 $1$병으로 바꾸면, $4$명의 지구인에게 각각 포도주 $1$병과 빵 $2$개씩을 나눠줄 수 있게 된다.
예제 입력 2
5 10 3
예제 출력 2
5
마법을 사용하지 않는 것이 최적인 경우도 있다.
예제 입력 3
7 8 7
예제 출력 3
15
가진 포도주를 모두 빵으로 바꾸면, $15$명의 지구인에게 빵을 $1$개씩 나눠줄 수 있다. 모든 지구인이 포도주를 받지 못하는 경우도, 공평하게 포도주가 분배되었고 남는 포도주가 없으므로 문제의 조건에 부합함에 유의하라.
힌트
출처
Contest > BOJ User Contest > 월간 향유회 > 월간 향유회 2023. 10. B번
- 문제를 만든 사람: pjshwa
- 문제를 검수한 사람: bnb2011, chogahui05, heeda0528, kiwiyou, rustiebeats, snrnsidy, utilforever