I really want to know how to solve this problem :
You are given two positive integers d and s. Find minimal positive integer n which is divisible by d and has sum of digits equal to s.
the link : https://mirror.codeforces.com/contest/1070/problem/A
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3773 |
| 3 | Radewoosh | 3646 |
| 4 | ecnerwala | 3624 |
| 5 | jqdai0815 | 3620 |
| 5 | Benq | 3620 |
| 7 | orzdevinwang | 3612 |
| 8 | Geothermal | 3569 |
| 8 | cnnfls_csy | 3569 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | awoo | 161 |
| 2 | maomao90 | 160 |
| 3 | nor | 157 |
| 4 | atcoder_official | 156 |
| 4 | cry | 156 |
| 6 | -is-this-fft- | 155 |
| 7 | maroonrk | 154 |
| 8 | adamant | 153 |
| 9 | Um_nik | 151 |
| 10 | djm03178 | 146 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 01.09.2024 05:19:16 (i1).
Десктопная версия, переключиться на мобильную.
При поддержке
The constraints are really important here, they are relatively small and may encourage some exploration techniques.
You can brute force every possible digit. Of course, this will lead to TLE unless you do some prunning.
Is it useful to insert a digit if it leads to the same sum and same value (mod d)?
You can solve it with BFS. Every node (or state) has two values, (number mod d, sum of digits)
Neighboring nodes are those possible values that can be obtained after inserting a digit to the right.
The target node is $$$(0, s)$$$. If this node is reachable, reconstruct the path and print answer. Otherwise, there is no number that satisfies both requirements.
I'd like to add an observation to the hint you gave:
"Is it useful to insert a digit if it leads to the same sum and same value (mod d)?" This can only happen is '0' is chosen. However, choosing '0' may not immediately lead to the same sum and same value (mod d), but it will eventually enter a cycle.
Therefore, the more general observation is that choosing '0' will always lead to a cycle, thus a straightforward dynamic programming solution won't work.