Modular Problem: Mod of a negative number ..llike -16%3 = 2
It is DP problem.
such input of data is in p[]; divident is k;
let , s=a[0]%k;
and s=-a[0]%k;
if any of s <0
then s =s+k [see mod of a negative number]
keep track in 2D array in a[0][s]=1.
s=s+p[1]%k,
for each s check this:
if any of s <0
then s =s+k [see mod of a negative number]
a[1][s]=1 &
s=s-p[1]%k,
a[1][s]=1…and so on
until end of input array
and last if a[last][0] is 1 then divisible else not.
[highlight]Solultion:[/highlight]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 |
#include <iostream> #include <stdio.h> //#include <stdlib.h> #include <fstream> using namespace std; int in[10010]; int a[10010][111]; int main() { int t,n,k; int p,f; cin>>t; //ofstream out; //out.open("o.txt"); while(t--) { cin>>n>>k; f=0; for(int i=0;i<10010;i++) for(int j=0;j<111;j++) a[i][j]=-1; for(int i=0;i<n;i++) { cin>>in[i]; if(i==0) { p=in[i]%k; //in[i]=p; if(p<0) p=p+k; a[i][p]=p; p=-in[i]%k; if(p<0) p=p+k; continue; } for(int j=0;j<k;j++) { if(a[i-1][j]!=-1) { p = (a[i-1][j]+in[i])%k; if(p<0) p=p+k; a[i][p]=p; if(i==n-1 && p==0) f=1; p = (a[i-1][j]-in[i])%k; if(p<0) p=p+k; a[i][p]=p; if(i==n-1 && p==0) f=1; } } } if(n==1) { if(abs(in[0])%k==0) cout<<"Divisible\n"; else cout<<"Not divisible\n"; continue; } if(f) cout<<"Divisible\n"; else cout<<"Not divisible\n"; } //out.close(); return 0; } |