파일 업로드

우유 상환

profile
실행 시간 제한메모리 제한
2 초512 MB
📃 해결할 문제

윤재는 친구에게 NN 갤런의 우유를 빌렸습니다 (1N10121 \le N \le 10^{12}). 그는 KK일 안에 친구에게 빌린 우유를 갚아야 합니다. 하지만 윤재는너무 빨리 우유를 갚고 싶지 않습니다. 한편으로는 상환에 대한 의지를 보여주어야 하므로, 그는 매일 최소한 MM 갤런의 우유를 친구에게 돌려줘야 합니다 (1M10121 \le M \le 10^{12}).

윤재가 친구에게 우유를 갚는 방법은 다음과 같습니다. 

그는 첫 번째로 양의 정수 XX를 선택하고, 매일 다음의 절차를 반복합니다:

  1. 윤재가 이미 친구에게 GG 갤런의 우유를 준 것으로 가정하고, NGX\frac{N-G}{X}를 계산하여 내림합니다. 이 숫자를 YY라고 부릅니다.
  2. 만약 YYMM보다 작다면, YYMM으로 설정합니다.
  3. 친구에게 YY 갤런의 우유를 돌려줍니다.

윤재가 위의 절차를 따랐을 때,  KK일 후에 친구에게 최소한 NN 갤런의 우유를 갚는 XX를 가장 큰 값으로 결정하십시오 (1K10121 \le K \le 10^{12}).

💻 입력

입력의 유일한 줄에는 세 개의 공백으로 구분된 양의 정수 NN, KK, MM이 있으며, KM\ltNK \cdot M\ltN을 만족합니다.

🖨️ 출력

윤재가 위의 절차를 사용하여 친구에게 최소한 NN 갤런의 우유를 줄 것으로 예상되는 가장 큰 양의 정수 XX를 출력하라.


💻 예제 입력 1
10 3 3
🖨️ 예제 출력 1
2

💡 힌트

첫 번째 테스트 케이스에서 X=2X=2일 때 윤재는 첫 날에 5 갤런의 우유를 친구에게 갚고, 

그 다음 두 날에는 각각 M=3M=3 갤런의 우유를 갚습니다.

이 문제에서 다루는 정수의 큰 크기 때문에 64비트 정수 데이터 타입의 사용이 필요할 수 있습니다 (예: C/C++의 "long long").


출처: USACO 2020 January Contest, Silver Problem 2. Loan Repayment