| № | Пользователь | Рейтинг |
|---|---|---|
| 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 |
How to handle 0's in this problem. Like when you have input like 230005450569. When there is no 0's the answer will be 2^n-1 when C is infinity. Now for C we will count how many numbers we have to subtract from answer which are >= length of C. But how to handle 0's in this case like sample input above.
Why don’t you just count the answer itself with DP? The length of possible number is maximum 10, so for every position you’d only need to check 10 possible numbers for validity.
How can we do that. When we look for C length then what about rest of digits. How we will handle them . And specially zeros.
Since 12 can be answer but 00 can't be.
Can you describe your approach in more detail.
$$$a_i$$$ – the amount of splits considering only the first $$$i$$$ digits.
$$$a_0 = 1$$$
$$$a_i = \sum_{j=\max(0, i-10)}^{i-1} a_j$$$, if number formed by digits $$$[j..i)$$$ is valid (has no leading zeroes and is $$$\leq C$$$)
if the number formed by digits[j..i) is not valid then a[i] = 0. is it correct?
I think you meant $$$a_j$$$, but yes, for that it’s enough to check first digit. Don’t forget that you still need to compare the whole number as well though.
yes, sorry. if j to i-1 is not valid then a[ j ] = 0. and by max(0,i-10) you mean max(0,i-C).
Please correct me if wrong.
C is not the boundary of the length of a number. It is a boundary of a number. 10 is coming from the fact that the maximum allowed value of C has 10 digits.
can you provide problem link?
I don't trust authors who use Latex but still manage to write $$$<=$$$ instead of $$$\le$$$.