dthreatz's blog

By dthreatz, 10 years ago, In English

I'm getting WA on Test Case 11. Since we cannot see the test cases or other people's code (since it's a Gym problem), does anyone have any idea on what's wrong with my code?

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <map>
#include <algorithm>
#include <cstring>
#include <set>
#include <fstream>
#include <cmath>
#include <iomanip>

using namespace std;

bool dp[10005][105];
int main()
{
    long n, k;
    cin >> n >> k;
    vector <int> v(n);
    for(long i = 0; i < n; i++) {
        cin >> v[i];
    }
    dp[1][v[0] % k] = 1;
    for(long i = 1; i < n; i++){
        for(long j = 0; j < k; j++){
            if(dp[i][j]){
                dp[i+1][abs((j+v[i])%k)] = 1;
                dp[i+1][abs((j-v[i])%k)] = 1;
            }
        }
    }
    puts(dp[n][0] ? "Divisible" : "Not divisible");
    return 0;
}
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
10 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

you need reset array d at beginning as 0 at all.

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Try this test:

2 6
-3 3

We can get 6: -(-3) + 3 = 6

  • »
    »
    10 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Your test case made me see where the error was. Thanks!

    In case anyone cares, I forgot to use the absolute value when getting the remainder in this line of code: dp[1][v[0] % k] = 1;