ICPC 스퀘어

시간 제한1초메모리 제한2048 MB

요약

N, D, S가 주어질 때 층 x에서 x의 배수 y로 y-x가 D 이하이면 이동하는 규칙으로 S층에서 도달할 수 있는 가장 높은 층을 구합니다.

난이도: 보통10점 중 6점
유형: 정수론, 동적 계획법, 수학
정답자: 아직 제출이 없습니다

문제

ICPC Square는 ICPC 위원회가 참가자의 숙박을 위해 마련한 호텔이다. 이 호텔은 $N$ 개의 층으로 이루어져 있으며, 층은 1번부터 $N$ 번까지 번호가 매겨져 있다. 호텔에는 특이한 엘리베이터가 있다. $x$ 층에 있는 사람은 $y$ 가 $x$ 의 배수이고 $y - x ≤ D$ 를 만족할 때에만 엘리베이터를 한 번 타고 $y$ 층으로 갈 수 있다.

현재 $S$ 층에 있다. 엘리베이터를 0번 이상 탈 수 있다. 도달할 수 있는 가장 높은 층을 구하라.

입력

한 줄에 세 정수 $N$ , $D$ , $S$ 가 주어진다 ( $2 ≤ N ≤ 10^{12}$ ; $1 ≤ D ≤ N - 1$ ; $1 ≤ S ≤ N$ ).

출력

엘리베이터를 0번 이상 타서 도달할 수 있는 가장 높은 층을 한 정수로 출력한다.

예제2

예제 1
입력
```
64 35 3
```
예상 출력
```
60
```
예제 2
입력
```
2024 2023 1273
```
예상 출력
```
1273
```