ccbeginner

UVa Q10036

Dec 31st, 2019
129
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //UVa Q10036
  2. #include<iostream>
  3. #include<string.h>
  4. using namespace std;
  5.  
  6. int arr[10001];
  7. bool dp[10001][101];
  8.  
  9. int main(){
  10.     int t,n,k;
  11.     cin>>t;
  12.     while(t--){
  13.         cin>>n>>k;
  14.         memset(dp,0,sizeof(dp));
  15.         for(int i = 1; i <= n; ++i){
  16.             cin>>arr[i];
  17.             arr[i] = abs(arr[i]%k);
  18.         }
  19.         dp[0][0] = 1;
  20.         for(int i = 1; i <= n; ++i){
  21.             for(int j = 0; j < k; ++j){
  22.                 if(!dp[i-1][j])continue;
  23.                 dp[i][(j+arr[i])%k] = 1;
  24.                 dp[i][(j+k-arr[i])%k] = 1;
  25.             }
  26.         }
  27.         if(dp[n][0])cout<<"Divisible\n";
  28.         else cout<<"Not divisible\n";
  29.     }
  30. }
RAW Paste Data