| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 10598 | Accepted: 3787 |
Description
Consider an arbitrary sequence of integers. One can place + or - operators between integers in the sequence, thus deriving different arithmetical expressions that eva luate to different values. Let us, for example, take the sequence: 17, 5, -21, 15. There are eight possible expressions: 17 + 5 + -21 + 15 = 1617 + 5 + -21 - 15 = -14
17 + 5 - -21 + 15 = 58
17 + 5 - -21 - 15 = 28
17 - 5 + -21 + 15 = 6
17 - 5 + -21 - 15 = -24
17 - 5 - -21 + 15 = 48
17 - 5 - -21 - 15 = 18
We call the sequence of integers divisible by K if + or - operators can be placed between integers in the sequence in such way that resulting value is divisible by K. In the above example, the sequence is divisible by 7 (17+5+-21-15=-14) but is not divisible by 5.
You are to write a program that will determine divisibility of sequence of integers.
Input
The first line of the input file contains two integers, N and K (1 <= N <= 10000, 2 <= K <= 100) separated by a space.The second line contains a sequence of N integers separated by spaces. Each integer is not greater than 10000 by it's absolute value.
Output
Sample Input
4 7 17 5 -21 15
Sample Output
Divisible
Source
Northeastern Europe 1999题目链接：http://poj.org/problem?id=1745
题目大意：给n个数，让他们通过加减运算，判断结果可不可能被k整除
题目分析：用dp[i][j]表示通过前i个数的运算得到的余数为j可不可能，先看求a % k，如果a > k，则a ＝ n * k + b，(n * k + b) % k == 0 + b % k = a % k，所以当a > k时，对求余数有影响的部分是不能被整除的部分，因此对于每个数我们可以做a[i] = a[i] > 0 ? (a[i] % k) : -(a[i] % k)的预处理，然后就是在dp[i - 1][j]的情况下，推出下一状态，下一状态有两种可能，加和减，减的时候防止出现负数加上个k再取余，初始化dp[0][a[0]] = true最后只要判断dp[n - 1][0]及前n个数通过加减运算能否得到被k整除的值
#include#include int const MAX = 10005; bool dp[MAX][105]; int a[MAX]; int main() { int n, k; while(scanf("%d %d", &n, &k) != EOF) { memset(dp, false, sizeof(dp)); for(int i = 0; i < n; i++) { scanf("%d", &a[i]); a[i] = a[i] > 0 ? (a[i] % k) : -(a[i] % k); } dp[0][a[0]] = true; for(int i = 1; i < n; i++) { for(int j = 0; j <= k; j++) { if(dp[i - 1][j]) { dp[i][(j + a[i]) % k] = true; dp[i][(k + j - a[i]) % k] = true; } } } printf("%s\n", dp[n - 1][0] ? "Divisible" : "Not divisible"); } }