Saleh127

UVA 10036 / Using Recursion

Oct 21st, 2021
1,037
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /***
  2.  created: 2021-10-22-03.25.15
  3. ***/
  4.  
  5. #include <bits/stdc++.h>
  6. using namespace std;
  7. #define ll long long
  8. #define test int tt; cin>>tt; for(int cs=1;cs<=tt;cs++)
  9. #define get_lost_idiot return 0
  10.  
  11. ll dp[10005][102];
  12. ll a[20005];
  13. ll n,k,ans=0;
  14.  
  15. void solve(ll i, ll sum)
  16. {
  17.      if(i==n+1)
  18.      {
  19.           if(sum%k==0) ans=1;
  20.           return;
  21.      }
  22.  
  23.      ll rem=sum+k;
  24.  
  25.      rem%=k;
  26.  
  27.      if(dp[i][rem]!=-1) return ;
  28.  
  29.      dp[i][rem]=1;
  30.  
  31.      rem=sum+a[i];
  32.  
  33.      solve(i+1,rem);
  34.  
  35.      rem=sum-a[i];
  36.  
  37.      solve(i+1,rem);
  38.  
  39. }
  40.  
  41. int main()
  42. {
  43.    ios_base::sync_with_stdio(0);
  44.    cin.tie(0);cout.tie(0);
  45.  
  46.  
  47.    test
  48.    {
  49.         ll i,j;
  50.  
  51.         cin>>n>>k;
  52.  
  53.         for(i=1;i<=n;i++) cin>>a[i];
  54.  
  55.         memset(dp,-1,sizeof dp);
  56.  
  57.         ans=0;
  58.  
  59.         solve(0,0);
  60.  
  61.         if(ans) cout<<"Divisible"<<endl;
  62.         else cout<<"Not divisible"<<endl;
  63.    }
  64.  
  65.  
  66.    get_lost_idiot;
  67. }
  68.  
RAW Paste Data