10036 - Divisibility

All about problems in Volume 100. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut

10036 - Divisibility

Post by titid_gede » Wed May 28, 2003 5:19 pm

How to avoid time limit exceeded for this problem?

with love & light,

titid
Kalo mau kaya, buat apa sekolah?

turuthok
Experienced poster
Posts: 193
Joined: Thu Sep 19, 2002 6:39 am
Location: Indonesia
Contact:

Post by turuthok » 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-
The fear of the LORD is the beginning of knowledge (Proverbs 1:7).

erfan
New poster
Posts: 44
Joined: Tue Apr 15, 2003 4:31 pm
Location: Chittagong,Bangladesh
Contact:

Post by erfan » 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.

SilVer DirectXer
New poster
Posts: 39
Joined: Wed Jan 22, 2003 11:02 am

10036 Divisibility WA

Post by SilVer DirectXer » 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?

Red Scorpion
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am

Post by Red Scorpion » Mon Aug 04, 2003 6:35 am

my code gives "Divisible".

doggn
New poster
Posts: 1
Joined: Sat Mar 13, 2004 3:08 pm

10036:WA

Post by doggn » 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 ..... :cry:

Karthekeyan
New poster
Posts: 33
Joined: Tue Jun 29, 2004 1:38 pm
Location: IITM,chennai,Tamil Nadu,India
Contact:

10036 - SIGSEGV - someone help!

Post by Karthekeyan » Wed May 18, 2005 6:14 pm

Here's my code that gives runtime error - sigsegv....
Can anyone temme why?

Code: Select all

spoiler
thanx in advance for the help!
:cry:
Last edited by Karthekeyan on Sun Dec 25, 2005 10:06 am, edited 1 time in total.
Karthe

User avatar
dumb dan
Learning poster
Posts: 67
Joined: Tue Aug 05, 2003 1:02 am

Post by dumb dan » Thu May 19, 2005 11:27 am

int a[105][105]={0};
...
for(int i=1;i<N;i++)
...
a[temp]=1;

N might be much larger than 105

Karthekeyan
New poster
Posts: 33
Joined: Tue Jun 29, 2004 1:38 pm
Location: IITM,chennai,Tamil Nadu,India
Contact:

Post by Karthekeyan » Thu May 19, 2005 5:22 pm

u r rite "dan"....
but i changed
a[105][105]
to
a[10001][105]
and now I get WA......ne reasons?
Karthe

User avatar
dumb dan
Learning poster
Posts: 67
Joined: Tue Aug 05, 2003 1:02 am

Post by dumb dan » Thu May 19, 2005 6:21 pm

this input:

Code: Select all

1
4 9
8 2 3 4
should yield this output:

Code: Select all

Divisible
since 8+2+3-4=9

Karthekeyan
New poster
Posts: 33
Joined: Tue Jun 29, 2004 1:38 pm
Location: IITM,chennai,Tamil Nadu,India
Contact:

Post by Karthekeyan » Sat May 21, 2005 4:21 pm

here's the changed code....
see the change done in the code...

Code: Select all

removed after getting ac
Last edited by Karthekeyan on Sun Dec 25, 2005 10:06 am, edited 1 time in total.
Karthe

qndel
New poster
Posts: 13
Joined: Tue Feb 03, 2004 11:00 am
Location: Opole

10036

Post by qndel » 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.
NOthing special

I LIKE GN
Learning poster
Posts: 57
Joined: Fri Oct 10, 2003 11:01 pm
Location: in front of PC
Contact:

IO needed

Post by I LIKE GN » Tue Jul 19, 2005 1:02 pm

i amm getting WA
Need some IO...
please help
There are two tragedies in life one is to lose your hearts' desire and another is to gain it --- GBS.

tan_Yui
Experienced poster
Posts: 155
Joined: Sat Jul 10, 2004 12:41 am

Post by tan_Yui » 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 :
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
Output should be :
Divisible
Not divisible
Divisible
Not divisible
Not divisible
Divisible
Divisible
Best regards.

I LIKE GN
Learning poster
Posts: 57
Joined: Fri Oct 10, 2003 11:01 pm
Location: in front of PC
Contact:

Post by I LIKE GN » 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.
There are two tragedies in life one is to lose your hearts' desire and another is to gain it --- GBS.

Post Reply

Return to “Volume 100 (10000-10099)”