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?

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.

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.