Help me to solve this problem : Find minimal k which sum of k's digit's square equals to N where N<=5000. For example: if N=100 then k=68 || if N=345 then k=277999.
Note: I think this problem is DP, but i couldn't do it.
№ | Пользователь | Рейтинг |
---|---|---|
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 |
Help me to solve this problem : Find minimal k which sum of k's digit's square equals to N where N<=5000. For example: if N=100 then k=68 || if N=345 then k=277999.
Note: I think this problem is DP, but i couldn't do it.
Название |
---|
I think you can make the dp D[i] = { (n, a1, a2, ... , a9) | n <= N }, a list of all the numbers that can be generated with the digits from 1 to i, with the digits they need (for your sample D[9] will contain (345, 0, 1, 0, 0, 0, 0, 2, 0, 3) ) So for each number i from 1 to 10 you have a list of all possible n you can obtain with numbers from 1 to i. We have D[0] = { (0, 0, 0, 0, 0, 0, 0, 0, 0, 0 } For passing from D[i] to D[i + 1], we first set D[i + 1] = D[i], and for each element in D[i + 1] (each pair of 10 numbers), we verify if by adding digit i + 1 we can create a new number, or optimize an existing one.
this works because: — it will calculate all possible numbers — it will only keep the ones with less digits — it will always try to minimise digits
You can solve it with DP by making DP[d][s] = is it possible to make a sum of s with a number of d digits?. The first step is to find the minimum digits that can lead to N. After that, you can perform greedily, assigning the smallest possible digit at each step. I attach code.
Let's denote dp[i] as the minimum number, which sum of digits' square is i. We can keep it as a string or a BigIntger, which length doesn't exceed 100 (ez to prove).
dp[0] = 0; others are infinity. Consider we are at dp[i]. Now let's iterate over the digits, we will add to the current, say j. Then we update dp[i + j * j] = min(dp[i + j * j], dp[i] * 10 + j)
The answer is dp[N].