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

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

Post by tan_Yui » Wed Jul 27, 2005 4:41 am

I LIKE GN wrote: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
Learning poster
Posts: 57
Joined: Fri Oct 10, 2003 11:01 pm
Location: in front of PC
Contact:

ACCCCCCCCCCCCCCCCCCCCC

Post by I LIKE GN » Thu Jul 28, 2005 6:33 pm

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

nymo
Experienced poster
Posts: 149
Joined: Sun Jun 01, 2003 8:58 am
Location: :)

Post by nymo » Wed Aug 31, 2005 11:48 am

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
New poster
Posts: 33
Joined: Tue Jun 29, 2004 1:38 pm
Location: IITM,chennai,Tamil Nadu,India
Contact:

Post by Karthekeyan » Sun Dec 25, 2005 10:05 am

tan_Yui wrote: Karthekeyan, your code should consider about minus by getting absolute value.
thanks a lot....i got it ac now
Karthe

ayon
Experienced poster
Posts: 161
Joined: Tue Oct 25, 2005 8:38 pm
Location: buet, dhaka, bangladesh

Post by ayon » Wed Jan 18, 2006 1:50 pm

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");
   }
}
ishtiak zaman
----------------
the world is nothing but a good program, and we are all some instances of the program

Shuvra(CSE-BUET)
New poster
Posts: 19
Joined: Wed Jan 11, 2006 9:57 am
Location: Dhaka

10036(DIVISIBILTY) WA , mad judge?

Post by Shuvra(CSE-BUET) » Wed Aug 23, 2006 6:37 am

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");



}


}
Life is a challenge.

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

Re: 10036(DIVISIBILTY) WA , mad judge?

Post by I LIKE GN » Sat Sep 02, 2006 2:34 pm

Shuvra(CSE-BUET) wrote:... 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
There are two tragedies in life one is to lose your hearts' desire and another is to gain it --- GBS.

Artikali
Learning poster
Posts: 68
Joined: Wed Sep 21, 2005 5:27 pm

10036 RE please help

Post by Artikali » Wed Sep 20, 2006 4:31 pm

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
Experienced poster
Posts: 155
Joined: Sat Jul 10, 2004 12:41 am

Re: 10036 RE please help

Post by tan_Yui » Thu Sep 21, 2006 8:43 am

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

Best regards.

Labib
New poster
Posts: 12
Joined: Tue Mar 05, 2013 4:49 pm

Re: 10036 - Divisibility

Post by Labib » Fri Mar 08, 2013 1:36 pm

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

Code: Select all

AC :)
Last edited by Labib on Fri Mar 08, 2013 9:45 pm, edited 1 time in total.

lbv
Experienced poster
Posts: 128
Joined: Tue Nov 29, 2011 8:40 am

Re: 10036 - Divisibility

Post by lbv » Fri Mar 08, 2013 8:02 pm

Labib wrote: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
New poster
Posts: 12
Joined: Tue Mar 05, 2013 4:49 pm

Re: 10036 - Divisibility

Post by Labib » Fri Mar 08, 2013 9:43 pm

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

shikhar_at
New poster
Posts: 2
Joined: Sun May 27, 2012 7:37 pm

Re: 10036 - Divisibility

Post by shikhar_at » Tue Jun 11, 2013 10:53 pm

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10036 - Divisibility

Post by brianfry713 » Wed Jun 12, 2013 12:16 am

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
Check input and AC output for thousands of problems on uDebug!

just_yousef
New poster
Posts: 50
Joined: Tue Dec 17, 2013 11:01 pm

Re: 10036 - Divisibility

Post by just_yousef » Mon Jul 28, 2014 3:07 pm

Is there any algorithms faster than DP on index and mod ??
Last edited by just_yousef on Wed Jul 30, 2014 8:43 pm, edited 1 time in total.

Post Reply

Return to “Volume 100 (10000-10099)”