szamsor_pluszminusz

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

/*
Tekintsünk egy egészekbők álló számsort. A számok közé a + és - jelet tehetjük.
A műveleti jelek választásától függően számtalan végeredményt állíthatunk elő.
A 17, 5, -21, 15 számokat tekintve az alábbi eredményre juthatunk.
17 + 5 + -21 + 15 = 16
17 + 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
Egy ilyen számsort D-vel oszthatónak nevezünk, ha van olyan műveletsor,
amelynek eredménye D-vel osztható. A fenti számsor ennek megfelelően osztható 7-tel,
de nem osztható 5-tel.
Feladat:
Írj programot, amely megállapítja, hogy egy számsor osztható-e egy adott számmal.

Bemenet:
A bemeneti állomány N tesztesetet tartalmaz. Az állomány első sorában az N értéke kap helyet.
A tesztesetek első sorában két egész szám található egyetlen szóközzel elválasztva, a K és a D.
(1<=K<=10000, 2<=D<=100). A teszteset második sorában K darab egész szám szerepel, köztük
szóközök vannak. Minden egész 10000-nél nem nagyobb abszolútértékű.

Kimenet:
A kimeneti állományba tesztesetenként egyetlen szót kell írni: "Divisible", ha a végeredmények
közül bármelyik osztható D-vel, illetve "Not divisible", ha a végeredmények közül egyetlen szám
sem osztható D-vel.

 */

bool van_e_oszthato_variacio(int osszeg, int *szamok, int k, int d)
{
    // Rekurziv fuggveny: eddig mar valahany szam variacioi megszulettek, azok
    // pluszos vagy minuszos osszege az elso parameter. Azon kivul meg k darabot kell
    // minden variacioban kiprobalni, azok kozul az elsore a szamok pointer mutat.

    if (k == 0) {
        // minden szamot osszeadtunk (illetve kivontunk), oszthato-e d-vel?
        return (osszeg % d == 0);
    }

    // megprobaljuk a kovetkezo szamot hozzaadni. Sikerul-e ugy valamelyik folytatas?
    // A folytatas: szamok+1 helyen van a kovetkezo k-1 darab szam, amit varialni kell
    int vane = van_e_oszthato_variacio(osszeg + *szamok, szamok+1, k-1, d);
    if (vane)
        return true;    // sikerult, nem is kell tovabb csinalni a rekurziot

    // megprobaljuk a kovetkezo szamot kivonni. Sikerul-e ugy valamelyik folytatas?
    return van_e_oszthato_variacio(osszeg - *szamok, szamok+1, k-1, d);
}

int main()
{
    FILE *input = fopen("bemenet.txt", "r");
    if (!input) {
        printf("Nincs bemenet.txt\n");
        exit(1);
    }

    FILE *output = fopen("kimenet.txt", "w");
    if (!output) {
        printf("Nem tudom letrehozni: kimenet.txt\n");
        exit(1);
    }

    // Elso sor: tesztszetek szama
    int n = 0;
    fscanf(input, "%d", &n);

    for (int szet=0; szet<n; szet++) {
        // Tesztszet elso sora: szamok darabszama, oszto
        int k=0, d=0;
        fscanf(input, "%d %d", &k, &d);

        // Masodik sor: a K darab szam, max 10000
        int szamok[10000];
        for (int i=0; i<k; i++)
            fscanf(input, "%d", &szamok[i]);

        if (van_e_oszthato_variacio(0, szamok, k, d)) {
            fprintf(output, "Divisible\n");
        } else
            fprintf(output, "Not divisible\n");
    }

    fclose(input);
    fclose(output);

    return 0;
}