hriss95's blog

Another thrilling problem
By hriss95, 12 years ago, In English

Hey guys, I've been solving this problem for a while but I still can't figure it out completely. So all we have given is the sum of the digits of a K-digit number and we have to find the smallest such number which when multiplied by D is a new number with sum of digits P. So the input is K,S,P,D where S is the sum of the digits of the number we are searching for. We have to print the smallest such number or print that there is no such number at all

Edit: Forgot to say that K is up to 100 and 1<=D<=9

  • Vote: I like it
  • +2
  • Vote: I do not like it

»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Please someone help! I am really eager to know the solution of this problem

→ Reply
»
12 years ago, # |
← Rev. 3   Vote: I like it +3 Vote: I do not like it

can we add trailing zeros? For example, the output for K = 0, S = 10, D = 1, P = 10. Should be 1009 or 0019?

UPD: i came up with a solution with complexity = (900^3), can you post the problem link to check it?

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    There aren't any leading zeros...K can't be 0 because K is the number of digits in the number we are searching for. The statement is in Bulgarian so the link won't work for you. The solution you figured out is DP i guess because i found one too in the moment I read the statement. However, I can't reduce one of dimensions because 900^3 is quite big for complexity of time and memory also.

    → Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I suppose you can solve it with

dp[i][j][k][l] — can you build an i-digit number with sum of digits j, sum of digits of number, multiplied by D so far equals to k and we have l carry in that number.

The idea is that we build the first number and simultaniously build the second one. And since the second one can be one digit greater than first, we must store that additional digit l.

Upd: Sorry :) forgot to count the complexity and it turns out 900^3

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yeah, don't worry...I thought of 2 solutions thinking that I had finally solved it and then it comes to calculating the complexity and it turned out I did nothing :D It happens a lot. Anyways...if something comes to your mind please write a reply. It truly is a thrilling problem

    → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think the idea to solve it is in this way, find a number with K+1 or K digits (such that when we divide it by D we get a K-digit number) such that it is minimal and is divisible by D. If we do that we've solved the problem. Now, to find such a number we must analyze different cases for different values of D (if D is even, or if it's a multiple of 3, or a multiple of 5), but as far I see all those cases are easy to check (there are simple rules of divisibility for all those numbers), and so I think that if the solution is feasible, it can be found very quickly just taking care of those different cases depending on D. I hope this helps you...

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What about sum of digits?

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      hmm, it seems I forgot that :( I will think it all over again and post if something new comes up, sorry...

      → Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it -8 Vote: I do not like it

I have another idea: f[a][b][t] is the minimum length of number which has sum of digits equals a, and sum of digits of new number (multiplied by D) equals b, t is the carry. Then we need to find f[S][P][0], if f[S][P][0] > K then no solution, else we just add some zeros to the result number to have exactly K digits. But I'm still thinking about how to compute this function.

→ Reply