11361 - Investigating Div-Sum Property

[apurba]

my code is giving correct output for first two sample but not for the third one.
is that output is correct?

need more test cases.

Title Edited by Moderator

[Robert Gerbicz]

my code is giving correct output for first two sample but not for the third one.
is that output is correct?

need more test cases.

The sample input/output is good!

It's easier if you use unsigned int, because A and B can be as large as 2^31-1 to avoid overflow in int type. And perhaps a clever algorithm to avoid TLE, use a large precomputed hash table to avoid the big computation of the answer.
The tricky test cases are those where A or B is divisible by a large power of 10. (It's too easy to miscompute the bounds of some variables).

[apurba]

here is my code.
what wrong with that?

Code: Select all

cut without ac
				

anyone help.

[Robert Gerbicz]

here is my code.
what wrong with that?

Your program is completely wrong. You have to compute the sum of the digits like this way:

Code: Select all

unsigned int sumofdigits( unsigned int n)  {
    unsigned int k=n,sum=0;
    while(k)  sum+=k%10,k/=10;
    return sum;
}

And try to avoid TLE, because by only this simple sumofdigits function you'll get that.

[apurba]

here is my code.
what wrong with that?

Your program is completely wrong. You have to compute the sum of the digits like this way:

Code: Select all

unsigned int sumofdigits( unsigned int n)  {
    unsigned int k=n,sum=0;
    while(k)  sum+=k%10,k/=10;
    return sum;
}

And try to avoid TLE, because by only this simple sumofdigits function you'll get that.

this is not working!!!!!!!
wrong again.

[sclo]

You need some kind of DP solution if you want to get this problem.
The dimensions are 10x10xKxK. But that is way out of bound, you need something more clever

[sohel]

K < 10000 was a clever trick.

[Lomir]

I think that, maximal possible K is 82. Because there are no numbers in inteval with larger sum of digits then 82.

[sonyckson]

I cant get the "kind of DP" idea.... can anyone give me some hints?? thanks. eric

[sclo]

I cant get the "kind of DP" idea.... can anyone give me some hints?? thanks. eric

The dimensions for the DP:
length of number, first digit of number, sum of digit mod K, number mod K

[sohel]

The dimensions for the DP:
length of number, first digit of number, sum of digit mod K, number mod K

My one is also similar to yours..
.. int dp[ length ][ sum of digit mod K ][ number mod K ] [ 1/0 depending one whether the chosen digits is a prefix of the number or not]

[Eiger Yap]

I also get TLE, hmmm....

[sclo]

if you did the dp properly, you won't get TLE. Remember that there are no solution if K is too large.

[Wei-Ming Chen]

Hello, I tried to use DP (10*10*K*K) to solve these problem

but got WA

Can someone check the I/O below? thanks.

Input:

Code: Select all

6
234 4567 8
3421 4568976 3
1232 456965 7
9909 123444 5
11111 11111111 7
980364 2147483647 11

CORRECT output:

Code: Select all

69
1521852
9306
4542
226548
17737396

[greve]

You can check I/O on my page http://www.uvatoolkit.com.