10036 - Divisibility
Moderator: Board moderators
-
- Experienced poster
- Posts: 187
- Joined: Wed Dec 11, 2002 2:03 pm
- Location: Mount Papandayan, Garut
10036 - Divisibility
How to avoid time limit exceeded for this problem?
with love & light,
titid
with love & light,
titid
Kalo mau kaya, buat apa sekolah?
-
- Experienced poster
- Posts: 193
- Joined: Thu Sep 19, 2002 6:39 am
- Location: Indonesia
- Contact:
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-
The fear of the LORD is the beginning of knowledge (Proverbs 1:7).
-
- New poster
- Posts: 39
- Joined: Wed Jan 22, 2003 11:02 am
10036 Divisibility WA
[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=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?
-
- Experienced poster
- Posts: 192
- Joined: Sat Nov 30, 2002 5:14 am
10036:WA
#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:](./images/smilies/icon_cry.gif)
#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:](./images/smilies/icon_cry.gif)
-
- New poster
- Posts: 33
- Joined: Tue Jun 29, 2004 1:38 pm
- Location: IITM,chennai,Tamil Nadu,India
- Contact:
10036 - SIGSEGV - someone help!
Here's my code that gives runtime error - sigsegv....
Can anyone temme why?
thanx in advance for the help!
![:cry:](./images/smilies/icon_cry.gif)
Can anyone temme why?
Code: Select all
spoiler
![:cry:](./images/smilies/icon_cry.gif)
Last edited by Karthekeyan on Sun Dec 25, 2005 10:06 am, edited 1 time in total.
Karthe
-
- New poster
- Posts: 33
- Joined: Tue Jun 29, 2004 1:38 pm
- Location: IITM,chennai,Tamil Nadu,India
- Contact:
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
-
- New poster
- Posts: 33
- Joined: Tue Jun 29, 2004 1:38 pm
- Location: IITM,chennai,Tamil Nadu,India
- Contact:
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
Last edited by Karthekeyan on Sun Dec 25, 2005 10:06 am, edited 1 time in total.
Karthe
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)
Input :
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
-
- Learning poster
- Posts: 57
- Joined: Fri Oct 10, 2003 11:01 pm
- Location: in front of PC
- Contact:
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.
There are two tragedies in life one is to lose your hearts' desire and another is to gain it --- GBS.