Page 1 of 2

11361 - Investigating Div-Sum Property

Posted: Sat Nov 24, 2007 9:45 pm
by 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

Re: 11361-- are there all correct outputs?

Posted: Sat Nov 24, 2007 10:11 pm
by Robert Gerbicz
apurba wrote: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).

what wrong with my code?

Posted: Sat Nov 24, 2007 10:22 pm
by apurba
here is my code.
what wrong with that?

Code: Select all

cut without ac
				
anyone help.

Re: what wrong with my code?

Posted: Sat Nov 24, 2007 11:28 pm
by Robert Gerbicz
apurba wrote: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.

Re: what wrong with my code?

Posted: Sun Nov 25, 2007 12:28 am
by apurba
Robert Gerbicz wrote:
apurba wrote: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.

Posted: Sun Nov 25, 2007 3:59 am
by 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 :)

Posted: Mon Nov 26, 2007 9:50 am
by sohel
K < 10000 was a clever trick. :wink:

Posted: Mon Nov 26, 2007 10:01 am
by Lomir
I think that, maximal possible K is 82. Because there are no numbers in inteval with larger sum of digits then 82.

Posted: Mon Nov 26, 2007 6:59 pm
by sonyckson
I cant get the "kind of DP" idea.... can anyone give me some hints?? thanks. eric

Posted: Mon Nov 26, 2007 8:39 pm
by sclo
sonyckson wrote: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

Posted: Tue Nov 27, 2007 1:07 pm
by sohel
sclo wrote: 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]

Posted: Thu Dec 06, 2007 3:42 pm
by Eiger Yap
I also get TLE, hmmm....

Posted: Fri Dec 07, 2007 3:28 am
by sclo
if you did the dp properly, you won't get TLE. Remember that there are no solution if K is too large.

Posted: Wed Jan 23, 2008 9:34 pm
by 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

Posted: Thu Jan 24, 2008 12:35 am
by greve
You can check I/O on my page http://www.uvatoolkit.com.