### 10036 - Divisibility

Posted:

**Wed May 28, 2003 5:19 pm**How to avoid time limit exceeded for this problem?

with love & light,

titid

with love & light,

titid

Page **1** of **3**

Posted: **Wed May 28, 2003 5:19 pm**

How to avoid time limit exceeded for this problem?

with love & light,

titid

with love & light,

titid

Posted: **Wed May 28, 2003 7:40 pm**

Dynamic Programming, tid ...

Start from the leftmost. Perform both addition and subtraction with the next integer and get the modulus ... The result will be between 0 -> k-1. Create a flag-array to mark that this position is valid.

In the next iteration, use that flag-array and for every valid position, perform both addition and subtraction like before with the next integer. And don't forget to get the modulus ... use another flag-array and mark the valid positions.

Do it repeatedly and when the last flag-array has its first element marked valid, that means it is divisible.

-turuthok-

Start from the leftmost. Perform both addition and subtraction with the next integer and get the modulus ... The result will be between 0 -> k-1. Create a flag-array to mark that this position is valid.

In the next iteration, use that flag-array and for every valid position, perform both addition and subtraction like before with the next integer. And don't forget to get the modulus ... use another flag-array and mark the valid positions.

Do it repeatedly and when the last flag-array has its first element marked valid, that means it is divisible.

-turuthok-

Posted: **Thu May 29, 2003 7:25 am**

It is DP problem.

such input of data is in p[]; divident is k;

Firstly s=p[0]%k;store it in two dimensional array in a[0][s]=1.

Then s=s+p[1]%k,a[1][s]=1 & s=s-p[1]%k,a[1][s]=1 in this way proceed

until end of p[];In last if a[last][0] is 1 then divisible else not.

I think you can realize.

such input of data is in p[]; divident is k;

Firstly s=p[0]%k;store it in two dimensional array in a[0][s]=1.

Then s=s+p[1]%k,a[1][s]=1 & s=s-p[1]%k,a[1][s]=1 in this way proceed

until end of p[];In last if a[last][0] is 1 then divisible else not.

I think you can realize.

Posted: **Sun Jul 20, 2003 3:11 pm**

[cpp]

#include <iostream>

#include <math.h>

using namespace std;

int n,k,i,j,l;

int input[10005];

int oper[10005];

int apv;

int sum;

int carry;

int ncase;

int ok;

void main(void)

{

cin>>ncase;

for (l=1;l<=ncase;l++)

{

for (i=1;i<=10001;i++)

oper*=0;*

apv=0;

cin>>n>>k;

for (i=1;i<=n;i++)

{

cin>>input*;*

apv+=input*;*

}

ok=0;

for (j=1;j<=(int)pow((int)2,(int)(n-1));j++)

{

carry=0;

oper[n-1]++;

for (i=n-1;i>=1;i--)

{

oper*+=carry;*

if (oper*==2)*

{

carry=1;

oper*=0;*

}

else

{

carry=0;

}

}

sum=apv;

for (i=1;i<=n-1;i++)

{

if (oper*==1)*

{

sum-=2*input[i+1];

}

}

if (sum % k==0 && sum!=0)

{

ok=1;

break;

}

}

if (ok==1)

cout<<"Divisible"<<endl;

else

cout<<"Not divisible"<<endl;

}

}

[/cpp]

i got a WA but i dont know why...pls help ....

and, if the input like this:

1 <---number of case

2 3 <---n and k

1 1

what will be the answer?

#include <iostream>

#include <math.h>

using namespace std;

int n,k,i,j,l;

int input[10005];

int oper[10005];

int apv;

int sum;

int carry;

int ncase;

int ok;

void main(void)

{

cin>>ncase;

for (l=1;l<=ncase;l++)

{

for (i=1;i<=10001;i++)

oper

apv=0;

cin>>n>>k;

for (i=1;i<=n;i++)

{

cin>>input

apv+=input

}

ok=0;

for (j=1;j<=(int)pow((int)2,(int)(n-1));j++)

{

carry=0;

oper[n-1]++;

for (i=n-1;i>=1;i--)

{

oper

if (oper

{

carry=1;

oper

}

else

{

carry=0;

}

}

sum=apv;

for (i=1;i<=n-1;i++)

{

if (oper

{

sum-=2*input[i+1];

}

}

if (sum % k==0 && sum!=0)

{

ok=1;

break;

}

}

if (ok==1)

cout<<"Divisible"<<endl;

else

cout<<"Not divisible"<<endl;

}

}

[/cpp]

i got a WA but i dont know why...pls help ....

and, if the input like this:

1 <---number of case

2 3 <---n and k

1 1

what will be the answer?

Posted: **Mon Aug 04, 2003 6:35 am**

my code gives "Divisible".

Posted: **Sat Mar 13, 2004 3:13 pm**

#include <iostream>

#include <vector>

#include <math.h>

using namespace std;

int main(void)

{

int CaseNum;

cin >> CaseNum;

for(int i=0;i<CaseNum;i++)

{

int n,k;

cin >> n >> k;

vector< vector<int> > arr;

for(int p=0;p<n;p++)

{

vector<int> temp;

for(int p2=0;p2<k;p2++)

temp.push_back(0);

arr.push_back(temp);

}

vector<int> input;

for(int j=0;j<n;j++)

{

int in;

cin >> in;

if(j==0)

input.push_back(in);

else

input.push_back(abs(in));

}

if(input[0] < 0 )

arr[0][k-(abs(input[0])%k)]=1;

else

arr[0][input[0]%k]=1;

for(int scan=0;scan<n-1;scan++)

{

for(int s=0;s<k;s++)

if(arr[scan][s]==1)

{

int next=scan+1;

int ar=input[next];

arr[next][(s+ar)%k]=1;

arr[next][(s+k-(ar%k)) % k]=1;

}

}

if(arr[n-1][0]==1)

cout << "Divisible";

else

cout << "Not divisible";

if(i<CaseNum-1)

cout << endl;

}

return 0;

}

I got a WA. please help me .....

#include <vector>

#include <math.h>

using namespace std;

int main(void)

{

int CaseNum;

cin >> CaseNum;

for(int i=0;i<CaseNum;i++)

{

int n,k;

cin >> n >> k;

vector< vector<int> > arr;

for(int p=0;p<n;p++)

{

vector<int> temp;

for(int p2=0;p2<k;p2++)

temp.push_back(0);

arr.push_back(temp);

}

vector<int> input;

for(int j=0;j<n;j++)

{

int in;

cin >> in;

if(j==0)

input.push_back(in);

else

input.push_back(abs(in));

}

if(input[0] < 0 )

arr[0][k-(abs(input[0])%k)]=1;

else

arr[0][input[0]%k]=1;

for(int scan=0;scan<n-1;scan++)

{

for(int s=0;s<k;s++)

if(arr[scan][s]==1)

{

int next=scan+1;

int ar=input[next];

arr[next][(s+ar)%k]=1;

arr[next][(s+k-(ar%k)) % k]=1;

}

}

if(arr[n-1][0]==1)

cout << "Divisible";

else

cout << "Not divisible";

if(i<CaseNum-1)

cout << endl;

}

return 0;

}

I got a WA. please help me .....

Posted: **Wed May 18, 2005 6:14 pm**

Here's my code that gives runtime error - sigsegv....

Can anyone temme why?
thanx in advance for the help!

Can anyone temme why?

Code: Select all

```
spoiler
```

Posted: **Thu May 19, 2005 11:27 am**

...

...

N might be much larger than 105

Posted: **Thu May 19, 2005 5:22 pm**

u r rite "dan"....

but i changed

but i changed

toa[105][105]

and now I get WA......ne reasons?a[10001][105]

Posted: **Thu May 19, 2005 6:21 pm**

this input:
should yield this output:
since 8+2+3-4=9

Code: Select all

```
1
4 9
8 2 3 4
```

Code: Select all

`Divisible`

Posted: **Sat May 21, 2005 4:21 pm**

here's the changed code....

see the change done in the code...

see the change done in the code...

Code: Select all

```
removed after getting ac
```

Posted: **Tue May 31, 2005 1:01 pm**

I solved this problem using simply DP but i'm not satisified with my time( over 2 seconds). I would be vary happy if anybody would tell me some faster algorithm.

Posted: **Tue Jul 19, 2005 1:02 pm**

i amm getting WA

Need some IO...

please help

Need some IO...

please help

Posted: **Wed Jul 20, 2005 5:55 am**

Hi, 'Karthekeyan', 'I LIKE GN'.

Karthekeyan, your code should consider about minus by getting absolute value.

In this case :

5 15

-1 -2 -3 -4 -5

-1 + -2 + -3 + -4 + -5 = -15 (-15 is divisible by 15)

**Input :**

Karthekeyan, your code should consider about minus by getting absolute value.

In this case :

5 15

-1 -2 -3 -4 -5

-1 + -2 + -3 + -4 + -5 = -15 (-15 is divisible by 15)

Output should be :7

4 7

17 5 -21 15

4 5

17 5 -21 15

10 30

9 -97 3 5 -1 0 11 -46 19 17

10 97

9 -97 3 5 -1 0 11 -46 19 17

12 16

-11 7 -73 40 5 -2 66 21 -64 16 16 16

5 15

-1 -2 -3 -4 -5

5 9

-5 -4 2 -2 0

Best regards.Divisible

Not divisible

Divisible

Not divisible

Not divisible

Divisible

Divisible

Posted: **Tue Jul 26, 2005 5:43 pm**

hello

thx for reply

i checked all ur i/o..

they are ok...

one thing

i made a random huge file with several test cases where

the inputs were like

10000 41

10000 randomly generated numbers...

10000 93

...

...

the most suspectable matter is my program gives

"Divisible" for ALL inputs...

so perhaps i amm missing something and

also i don know how to post such huge files here(i.e. as a link or

others)

thx.

thx for reply

i checked all ur i/o..

they are ok...

one thing

i made a random huge file with several test cases where

the inputs were like

10000 41

10000 randomly generated numbers...

10000 93

...

...

the most suspectable matter is my program gives

"Divisible" for ALL inputs...

so perhaps i amm missing something and

also i don know how to post such huge files here(i.e. as a link or

others)

thx.