7253번 - Skaitmens keitimas 서브태스크다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 8 | 6 | 6 | 100.000% |
문제
Dovydas pasakė Justui du natūraliuosius skaičius N ir M. Justo užduotis – iš N padaryti kuo didesnį skaičių. Tą jis gali padaryti keisdamas po vieną N skaitmenį taip, kad po kiekvieno keitimo skaičiaus dalybos iš M liekana padidėtų. Keičiant skaitmenį neleidžiama pirmojo skaitmens pakeisti nuliu (0).
Pavyzdžiui, jei N = 1399 ir M = 11, tai N dalybos iš M liekana iš pradžių yra 1399 mod 11 = 2. Jei Justas pirmuoju žingsniu keistų paskutinįjį N skaitmenį, tai jį rinktųsi iš 0, 1, . . . , 6, nes šie variantai padidina liekaną:
| N | 1390 | 1391 | 1392 | 1393 | 1394 | 1395 | 1396 | 1397 | 1398 | 1399 |
|---|---|---|---|---|---|---|---|---|---|---|
| liekana | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 0 | 1 | 2 |
Sakykime, kad jis pasirenka 3, taigi N dabar yra 1393. Jei Justas dabar keistų pirmąjį skaitmenį, tai vienintelis variantas yra 9 (atkreipkite dėmesį, kad neleidžiama pirmojo skaitmens pakeisti į 0):
| N | 1393 | 2393 | 3393 | 4393 | 5393 | 6393 | 7393 | 8393 | 9393 |
|---|---|---|---|---|---|---|---|---|---|
| liekana | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 | 10 |
Skaičiaus 9393 daugiau keisti negalima, nes jau gauta didžiausia įmanoma dalybos iš 11 liekana (9393 mod 11 = 10). Tai būtų Justo rezultatas.
Tačiau tai nėra geriausias įmanomas rezultatas. Geriausias rezultatas yra 9899, kurį galima pasiekti atliekant, pavyzdžiui, tokius žingsnius:
| N | 1399 → 1899 → 9899 |
|---|---|
| liekana | 2 → 7 → 10 |
Nustatykite, kokį didžiausią skaičių Justas gali pasiekti.
입력
Vienintelėje eilutėje pateikiami skaičiai N ir M.
출력
Išveskite didžiausią skaičių, kokį Justas gali pasiekti.
제한
- 1 ≤ N < 1017
- 1 ≤ M ≤ 109
서브태스크
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 5 | N < 10, M < 10 |
| 2 | 15 | N < 1000, M = 9 |
| 3 | 50 | N < 106, M ≤ 106 |
| 4 | 30 | Nėra |
예제 입력 1
1399 11
예제 출력 1
9899
Sąlygoje aprašytas pavyzdys.
예제 입력 2
123 10
예제 출력 2
129
Kitų skaitmenų keisti negalima, nes dalybos iš 10 liekana nesikeičia.
예제 입력 3
89 7
예제 출력 3
89
Pradinio skaičiaus padidinti neįmanoma.
출처
Olympiad > Lithuanian Olympiad in Informatics > Lithuanian Olympiad in Informatics 2021/2022 > National Round (2) > 7-9 Classes ?번
Olympiad > Lithuanian Olympiad in Informatics > Lithuanian Olympiad in Informatics 2021/2022 > National Round (2) > 10-12 Classes ?번
채점 및 기타 정보
- 예제는 채점하지 않는다.