Hi, I am trying to solve the problem for a while but couldn't finish. Can anyone please help me in details that how can I solve the problem.
Problem Link: https://ibb.co/b5DgKwN
Thanks in advance. :) Sorry for my poor english. :)
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
Hi, I am trying to solve the problem for a while but couldn't finish. Can anyone please help me in details that how can I solve the problem.
Problem Link: https://ibb.co/b5DgKwN
Thanks in advance. :) Sorry for my poor english. :)
Name |
---|
I think that this problem can be solved using binary search. If a number X is divisible by M, then X = F * M. And we can binary search this F.
In function cnt we just count amount of digits in our number like this:
Are you considering here that N can be 10^100? If N was <= 10^18 then we can compute without binary search
Ohh, sry. Didn't notice the constrains
Let's say number of digits in N is x therefore you have to find smallest multiple of M which is greater than 10^(x-1). Let's call the number to be multiplied as K and number of digits in M as y. If M is perfect power of 10 then K will be 10^(x-y)(i.e if N = 100, M=10, K = 10), otherwise K will have (x-y) digits(i.e if N = 100(=10^2), M = 5(=5x10^0) then K = 20 which has 2 digits). Now as you know number of digits in K, now start from most significant digit and for each digit position i find largest number which when multiplied with M gives number smaller than 10^(x-1) and set that value there. Then finally add 1 to K to get the number just greater than 10^(x-1) as number K which we had found gives multiple just less than 10^(x-1). code to multiply strings https://www.geeksforgeeks.org/multiply-large-numbers-represented-as-strings/
You misunderstood the statement. The priority is to minimize the number of different digits.
Oh! seems like i didn't read it properly :p
The problem can be reduced to knapsack mod $$$M$$$ : define $$$dp_{i,j}$$$ as the minimal number of digits to change, knowing that first $$$i$$$ digits of $$$X$$$ are fixed, and that the current value of $$$X \bmod M$$$ is $$$j$$$.
Let $$$D \leq 100$$$ the number of digits in $$$N$$$. There will be $$$O(D \cdot M)$$$ states and $$$10$$$ transitions. Reconstruction of $$$X$$$ is easy. Final number of operations will be around $$$10^9$$$, my code works in less than 200ms on custom invocation of Codeforces (optimize cache usage, don't use long long, substract instead of using modulo operator).
Thanks :) Can you provide me the source code :)
https://ideone.com/KHhdgi