SIGKILL misterioso

Ciao. Ho appena scritto il teorema dei quattro quadrati, tuttavia a parte nei primi due casi di test, il programma riceve un sigkill da linux (nonostante non vado a violare i limiti di memoria). Idee?

#include <iostream>
#include <fstream>
#include <cmath>

using namespace std;

int cache[202][4] = {{}};


int calcola(int n, int index, int prev)
{
    //if (cache[n][index] != 0)
    //    return cache[n][index]-1;
    int rad = sqrt(n);
    int s = 0;
    if (index == 0)
    {
        if (rad*rad == n)
        {
            if (prev < rad)
                return 0;
            //for (int i=0; i<3-index; i++)
            //    cout << " ";
            //cout << rad << endl;
            cache[n][index] = 2;
            return 1;
        }

        else
        {
            cache[n][index] = 1;
            return 0;
        }
    } else {
        for (int i=rad; i>=0; i--)
        {
            if (prev < i)
                continue;
            //for (int i=0; i<3-index; i++)
            //    cout << " ";
            //cout << i << endl;

            s += calcola(n-i*i, index-1,i);
        }
        cache[n][index] = s+1;
        return s;
    }



}


int main()
{
    ifstream input("input.txt");
    ofstream output("output.txt");

    int n;
    int t;
    input >> n;
    for (int i=0; i<n; i++)
    {
        input >> t;
        output << calcola(t, 3,t);
        if (i < n-1)
            output << " ";
    }

    return 0;
}

Stai allocando cache[202][4], presumo forte del fatto che N \le 200.
Il parametro n che riceve la funzione calcola(n, index, prev) ha un nome fuorviante: è in realtà uno dei valori che vengono forniti in input (V[i]) che può arrivare fino a 2^{15}.

1 Mi Piace

Perchè ha un nome fuorviante? n è l’input, dopo viene tolto un quadrato n-a² e quindi a² + (nuovo n)

A proposito ma io ti conosco!

Chiaramente puoi usare la nomenclatura che preferisci per le tue variabili. Provo a essere un po’ più chiaro.

Ricapitoliamo i dati in ingresso del problema: vengono forniti un intero N (non più grande di 200) e N interi, ciascuno dei quali non più grande di 2^{15}.
Il primo parametro della funzione calcola viene usato come indice per la riga della matrice cache (composta da 202 righe e 4 colonne).

Osserviamo ora la chiamata nel main calcola(t, 3,t). È evidente che t è uno dei valori V[i] e può quindi arrivare fino a 2^{15}. All’interno della funzione tu accedi alla $n-$esima riga della matrice cache: essa ha solo 202 righe, ma potenzialmente il tuo “indice di riga” arriva fino a 2^{15}.

Compatibilmente con i limiti di memoria è quindi necessario che innalzi opportunamente il numero di righe della matrice.

Ho tenuto gli incontri in preparazione alle territoriali al Paleocapa :wink:

Ah ok ho capito. Mi sono confuso N(come numero di Vi) e N come intero da processare (quindi ho letto male il testo.

Ho tenuto gli incontri in preparazione alle territoriali al Paleocapa

ci scommettevo