RiseOJ – 대출 상환

설명

농부 존은 베시에게 우유 $$N$$ 갤런( $1\le N\le 10^{12}$ )을 빚졌다. 그는 $$K$$ 일 안에 베시에게 우유를 갚아야 한다. 하지만 우유를 너무 빨리 내주고 싶지는 않다. 한편으로는 대출 상환에 진전이 있어야 하므로, 매일 베시에게 적어도 $$M$$ 갤런( $1\le M\le 10^{12}$ )의 우유는 주어야 한다.

농부 존이 베시에게 갚기로 한 방식은 다음과 같다. 먼저 양의 정수 $$X$$ 를 하나 고른다. 그런 다음 매일 다음 절차를 반복한다.

농부 존이 지금까지 베시에게 $$G$$ 갤런을 주었다고 할 때, $\frac{N-G}{X}$ 를 내림한 값을 계산한다. 이 수를 $$Y$$ 라고 하자.
$$Y$$ 가 $$M$$ 보다 작으면, $$Y$$ 를 $$M$$ 으로 정한다.
베시에게 우유 $$Y$$ 갤런을 준다.

농부 존이 위 절차를 따랐을 때 $$K$$ 일( $1\le K\le 10^{12}$ ) 후 베시에게 적어도 $$N$$ 갤런의 우유를 주게 되는 가장 큰 $$X$$ 를 구하여라.

문제 제공: Nick Wu

제약

점수 배점

테스트 케이스 2-4는 $K\le 10^5$ 을 만족한다.
테스트 케이스 5-11은 추가 제약이 없다.

문제 제공: Nick Wu

입력 형식

입력은 한 줄로, $$K\cdot M을 만족하는 공백으로 구분된 세 양의 정수 \(N$, $K$, $M$이 주어진다.$

출력 형식

위 절차를 사용해 농부 존이 베시에게 적어도 $$N$$ 갤런을 주게 되는 가장 큰 양의 정수 $$X$$ 를 출력한다.

Standard input / output

This problem is judged over standard input/output. The original contest used named files — if you prefer the classic interface, tick “File I/O” on the submit form and read/write these files instead:

입력을 읽을 파일 loan.in · 출력을 쓸 파일 loan.out

예제 1

입력

10 3 3

출력

설명

For the first test case, when $$X=2$$ Farmer John gives Bessie $$5$$ gallons on the
first day and $$M=3$$ gallons on each of the next two days.

Note that the large size of integers involved in this problem may require the use of 64-bit integer
data types (e.g., a "long long" in C/C++).

문제 정보

riseoj 작성

출처 올림피아드 > USACO > 2019-2020 > January > Silver

올림피아드 > USACO > 2019-2020 > January > Silver

태그

JudgeUSACO

대출 상환

평가 및 의견

풀이 제출