Определите, можем ли мы поставить «+» и «-» между числами, чтобы результат делился на число: где моя ошибка?

Question

У нас есть howmanynums номера. Мы должны определить, есть ли способ поместить '+' и '-' между ними таким образом, чтобы результат делился на заданное число mod.

(предпочтительно делать это с помощью динамического программирования, но я просто считаю каждую последовательность с нуля, потому что очень мало времени и просто нужно, чтобы она работала).

int howmanynums, mod;

int ring(int num) {
    if ((num >= 0) && (num <= mod - 1))
        return num;
    if (num >= mod) {
        while (num >= mod)
            num -= mod;
        return num;
    }
    if (num < 0) {
        while (num < 0)
            num += mod;
        return num;
    }
}

long int p(int n) {
    long int t = 1;

    while (n > 0) {
        t *= 2; 
        n--;
    }
    return t;
}

int sequence[10000][2];

int main() {
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    scanf("%d%d%d", &howmanynums, &mod, &sequence[0][0]);
    sequence[0][0] = ring(sequence[0][0]);
    int temp;
    int k = 1;
    while (k < howmanynums) {
        scanf("%d", &temp);
        sequence[k][0] = ring(temp);
        sequence[k][1] = ring(-temp);
        k++;
    }

    long int x = (p(howmanynums - 1)); 
    while (x > 0) {
        long int a = sequence[0][0];
        long int permutation = x;
        long int insidePermutation = x % 2;
        int l = 1;
        while (l < howmanynums) { 
            a += sequence[l][insidePermutation]; 
            l++; 
            permutation = permutation / 2; 
            insidePermutation = permutation % 2; 
        }
        if (a % mod == 0) {
            printf("%s", "Divisible");
            goto e;
        }
        x--;
    }
     printf("%s", "Not divisible");

 e:
    return 0;
}

Проходит 10 тестов из 20. Я не знаю тестов.

Я также попытался заменить все целые на длинные, но результат тот же.

Где моя ошибка?

Answer 1

Я упростил твой код, и он выглядит хорошо для меня.Это должно сделать работу.Мое единственное беспокойство - эффективность.Требуется около 20 секунд, чтобы найти ответ «Не делится» для следующей последовательности из 30 чисел: 30 2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0. Каждый дополнительный номер удваивается в предыдущий раз.Таким образом, тесты, которые ваш код не прошел, могут быть из-за допустимого времени тестирования.

Динамическое программирование обязательно для прохождения тестов.

#include <stdio.h>
#pragma warning(disable : 4996)

int howmanynums, mod, sequence[64];

int main() {
    freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    scanf("%d%d", &howmanynums, &mod);
    if (howmanynums > 64)
    {
        printf("Too many %d", howmanynums);
    }
    int k = 0;
    while (k < howmanynums)
        scanf("%d", &sequence[k++]);
    int x = (2 << (howmanynums - 2)) - 1;
    bool divisible = false;
    while (!divisible && x >= 0)
    {
        int a = sequence[0], bit = 1;  k = 1;
        while (k < howmanynums)
        {
            a += x & bit ? sequence[k] : -sequence[k];
            k++;
            bit *= 2;
        }
        divisible = a % mod == 0;
        x--;
    }
    printf("%s", divisible ? "Divisible": "Not divisible");
    return 0;
}