| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
Hi,
Can someone please help me with the following problem? https://atcoder.jp/contests/abc155/tasks/abc155_e
I found this dp solution, am unable to understand what does dp state denote and how transitions are made? https://atcoder.jp/contests/abc155/submissions/10154214
Or any other solution?
Refer this comment
Hi, thanks for the reply. I did check out that comment but I am unable to understand it. Can you please elaborate a bit on what does dp state denote (as in what does carry mean?).
Can you please shed more light on the solution?
As in what's the intuition/logic behind it? What are we trying to do exactly?
Start considering from the least significant position. Here either you can choose to pay that position's value or increase the amount so that the clerk returns the number of notes for that position as (10-that value) with your next higher significant payment increased by one (i.e you are paying on more note for the next higher position and expecting the desired return for this position).
This happens for every digit from right to left and we have the options of giving the value or expecting a change by giving some extra money.
Finally, at the most significant position, you come to know whether at each digit you ask for change there or give the amount in case you want to know the number of notes of each type which is not required though.