10036 - Divisibility

[tan_Yui]

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)

Hi.
It's difficult to paste such huge files.
One solution is to paste your code and generator code.

Best regards.

[I LIKE GN]

helloooooooooo
i just get it ACCCCCCC!!!
i had a stupid mistake not handling the tribial case of only 1 number...
and also a silly bug in coding.
so now the game is over...
thanks a LOTTTTTTT for ur appriciating helps
well friend see u.....
regards
RSS

[nymo]

I 've tried to solve this problem with dp, my code is producing WA. This is the portion of my code which incorporates the recurrence. I 've checked several inputs ... it seems okay. Anyway, any suggestions, bugs in my code or tricky inputs ???

Code: Select all

CODE REMOVED AFTER ACC, while subtracting, i better be a bit more careful  :D

Thanks everybody.

[Karthekeyan]

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

thanks a lot....i got it ac now

[ayon]

i am getting wa and wa, i tested all the inputs in the board. i used dp, i cannot find my mistake. if you can, please give me some more test cases. and what is the input for
1
1 5
-5

my program gives Divisible. is it correct, i guess it's correct because in the sample test cases, thay said -14 is divisible by 7.

Code: Select all

#include <stdio.h>
#include <string.h>

int x[10036];

void main()
{
	int test, tc, i, k, n, r, f, t, stack[1009], p, add, sub;
   bool flag[109];
	scanf("%d", &test);
   for(tc = 0; tc < test; ++tc)
   {
   	scanf("%d%d", &n, &k);
      for(i = 0; i < n; ++i)
      {
      	scanf("%d", &x[i]);
         if(x[i] < 0)
         	x[i] = -x[i];
      }
      if(n == 1)
      {
      	if(x[0] % k != 0)
         	puts("Not divisible");
         else
         	puts("Divisible");
         continue;
      }
      r = f = 0;
      stack[f++] = x[0] % k;
      for(i = 1; i < n; ++i)
      {
      	memset(flag, 0, sizeof(flag));
         t = f;
         while(r < t)
         {
         	p = stack[r++];
            add = (p + x[i]) % k;
            sub = (p + k - x[i] % k) % k;
            if(!flag[add])
            {
            	flag[add] = 1;
               stack[f++] = add;
            }
            if(!flag[sub])
            {
            	flag[sub] = 1;
               stack[f++] = sub;
            }
         }
      }
      if(flag[0])
      	puts("Divisible");
      else
      	puts("Not divisible");
   }
}

[Shuvra(CSE-BUET)]

Hey, what's the hell there?I can't find any tricky input ,and what I think is absolutely right. I read all the previous posts. But I am too fool realise what is my mistake. Pls help me. (I tried also with a newline after the last case .Don't tell me about this.)
.........................................................................................................

#include <stdio.h>
#include <math.h>
bool a[10005][105];
long int d[10005];

void main(){

long int m,n,k,i,j,flag=0;
scanf("%ld",&m);
while(m-->0){

scanf("%ld%ld",&n,&k);
for(i=1;i<=n;i++)
scanf("%ld",&d);

for(i=1;i<=n;i++)
for(j=0;j<k;j++){
a[j]=0;
}
a[1][abs(d[1])%k]=1;

for(i=2;i<=n;i++)
{
for(j=0;j<k;j++)
{
if(a[i-1][j]==1)
{
a[(j+abs(d)) % k] = 1 ;
a[(j+k-abs(d)) % k] = 1;
}

}//for


}//for
if(flag==0)
flag=1;
else
printf("\n");

if(a[n][0]==1)
printf("Divisible");
else
printf("Not divisible");



}


}

[I LIKE GN]

... what I think is absolutely right. I read all the previous posts...

i did not go through ur code but if u r too sure u r doing the right job, i would like to advice u to make a "random" input file and take a view of how ur program responses.

also check the tribial case of only 1 number... (i got WA for this).

RSS

[Artikali]

here is my code, In my computer it ran properly.

Code: Select all

#include <iostream>
#include <cstdio>
#include <string>
#include <cassert>
using namespace std;
int c[100050][1100];
#define N 999999
int modul(int n,int m){
    while(n < 0)
	n += m;
	int tmp=n%m;
	//assert(tmp>=0 && tmp<m);
    return tmp;

}
int main(){
	//freopen("agrinet.in","r",stdin);
	int count;
	cin>>count;
	int n,k,a,b;
	int tmp;
	while(count--){
		cin>>n>>k;
		for(int i=0;i<n;i++)
			for(int j=0;j<k;j++)
				c[i][j]=0;
		cin>>a>>b;

		tmp=modul(a+b,k);
		c[1][tmp]=1;

		tmp=modul(a-b,k);
		c[1][tmp]=1;

		for(int i=2;i<n;i++){
			cin>>a;
			for(int j=0;j<k;j++){
				if (c[i-1][j]==1){

					tmp=modul(j+b,k);
					c[i][tmp]=1;

					tmp=modul(j-b,k);
					c[i][tmp]=1;
				}
			}
		}
		if (c[n-1][0]==1) cout<<"Divisible"<<endl;
		else cout<<"Not divisible"<<endl;
	}
	return 0;
}

thanks.

[tan_Yui]

Hi,
the range of N is 1 <= N <= 10000.
So, you have to assume the special case N = 1.

Best regards.

[Labib]

I don't see whats wrong with my code...
Getting WA. plz help, someone?
thanks in advance...

Code: Select all

AC :)

[lbv]

I don't see whats wrong with my code...
Getting WA. plz help, someone?

You may try these cases:

Input

Code: Select all

3
3 13
51 -74 -81
12 18
-83 -53 -76 -54 18 61 55 80 -80 66 55 1
10 27
-10 -52 36 96 -59 97 -74 -63 -44 -5

Output

Code: Select all

Divisible
Divisible
Divisible

[Labib]

Thanks a lot bro
that was really helpful.. learnt something new!!

[shikhar_at]

Code: Select all

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
#include<stack>
#include<map>
#include<cctype>
#include<sstream>
#define L long long int
#define U unsigned long long int
#define INF 10000000
using namespace std;

vector<int> v[10010];
int a[10010];
int dp[10010][110];
int main()
{
	int t;
	cin>>t;
	int n,k;
	while(t--)
	{
		scanf("%d %d",&n,&k);
		for(int i=0;i<n;i++)
		{
			v[i].clear();
			for(int j=0;j<2*k-1;j++)
			{
				dp[i][j]=0;
			}
			scanf("%d",&a[i]);
		}
		int x=a[0]%k;
		int y=-a[0]%k;
		if(x<0)x=abs(x)+k;
		if(y<0)y=abs(y)+k;
		dp[0][x]=1;
		dp[0][y]=1;
		int flag=0;
		for(int i=1;i<n;i++)
		{
			for(int j=0;j<k;j++)
			{
				if(dp[i-1][j])
				{
					x=(a[i] + j)%k;
					y=(-a[i] + j)%k;
					if(i==n-1 && (x==0 || y==0))
					{
						flag=1;
						break;
					}
					if(x<0)
					{
						x=abs(x) + k;
					}
					if(y<0)
					{
						y=abs(y) + k;
					}
					dp[i][x]=1;
					dp[i][y]=1;
				}
			}
			if(flag)break;
			for(int j=k;j<2*k-1;j++)
			{
				if(dp[i-1][j])
				{
					x=(a[i] - (j-k))%k;
					y=(-a[i] - (j-k))%k;
					if(i==n-1 && (x==0 || y==0))
					{
						flag=1;
						break;
					}
					if(x<0)
					{
						x=abs(x) + k;
					}
					if(y<0)
					{
						y=abs(y) + k;
					}
					dp[i][x]=1;
					dp[i][y]=1;
				}
			}
			if(flag)break;
		}
		
		if(flag)
		{
			printf("Divisible\n");
		}
		else printf("Not divisible\n");
	}
}

I am getting WA...can someone help me plz...

[brianfry713]

Input:

Code: Select all

20
27 43
6853 -7696 -8682 -8558 1701 8863 -1596 5422 -5284 1735 535 1258 -1949 9763 -8717 -2359 3952 3650 -2409 -4225 4523 4761 4310 7889 -7100 -1542 -8696
8 78
-693 584 9 1611 5623 1451 -6688 8207
26 80
-3357 5310 6710 -8379 -2919 -9808 -7096 8444 4145 6554 -3966 -6360 1076 -5485 7951 2686 -2585 129 7711 3969 -6715 739 -1727 3295 -7651 -2384
24 63
-4178 -1679 5558 2465 -2649 2267 4087 4433 2460 -9289 6597 325 7266 -7370 3965 2062 -2855 1915 -1532 8281 -4236 -3821 5970 -950
17 29
-7656 -7013 5579 810 6091 -8599 9131 1648 7587 203 -2365 5394 -1644 -6185 6106 -5048 4140
17 57
-1895 -847 8448 -6260 -8658 -9552 -495 -2479 6418 -7725 -1841 -5620 -5381 4867 9959 9150 4678
23 70
46 -7333 2204 7682 -8219 -9441 -4783 7887 -4489 -6922 8699 6814 1183 1573 5261 8644 2915 9430 1869 -5844 5847 4144 6036
12 100
902 -6095 -8367 -4420 2707 -6366 5626 5374 5838 7028 -9125 6397
20 100
-4372 -956 -8819 -7559 -9774 2754 -8578 -7410 -4332 -9149 4460 3545 -9582 -1397 -420 -1914 1087 -9518 5712 6441
25 86
-9926 -4592 -2488 5912 -3843 -1612 6029 2123 871 -8344 -8834 2052 -2182 -4887 -1473 2961 -2297 4195 7533 -4117 -2260 7951 4487 7320 -243
13 63
-4532 -4266 1305 3887 -471 -9566 -8602 -4560 312 -214 -4811 -7566 -9344
30 83
6430 8384 2434 -5044 1344 -9864 -7129 -1124 -259 4332 547 -2052 5373 -9697 7242 6895 -4229 -3304 1921 9658 9946 6076 -8944 -4615 -3613 4563 574 2542 8941 -8861
18 33
9523 2296 -9675 866 6153 -6804 -6538 -4107 7529 4009 3841 2901 4312 4803 3516 -6197 -4781 -843
1 30
-4768
8 58
1619 -3479 -5157 -2119 -4539 -297 -2257 -9170
28 64
-5124 -6189 6192 1794 -2727 -7916 3043 -4998 9647 -336 -6966 4449 -6821 -3162 -6611 2337 4020 -1447 -8711 -4022 -7177 6630 6220 1387 -5490 -8319 -8910 2254
8 70
2292 4830 -8432 2204 344 2562 4289 -6614
10 81
3050 -5681 2104 9950 1157 9214 6007 -1103 -2233 7297
15 66
3926 8537 -4303 8436 -9783 508 4410 170 -5456 -3298 -1280 -167 8906 9064 -7606
20 97
9959 4570 9220 -5722 395 -7110 9156 -392 8897 1774 -8905 6193 4090 5406 3839 2626 -5176 5996 6564 5332

AC output:

Code: Select all

Divisible
Divisible
Not divisible
Divisible
Divisible
Divisible
Not divisible
Not divisible
Not divisible
Divisible
Divisible
Divisible
Divisible
Not divisible
Not divisible
Not divisible
Not divisible
Divisible
Divisible
Divisible

[just_yousef]

Is there any algorithms faster than DP on index and mod ??