Aiuto Lotteria di Quadri 15/100

Aiuto
1

Ho fatto il mio algoritmo lotteria dei quadri e in locale sembra funzionare tutto a meraviglia. Riesco a fare i subtask 1 e 2, ma a partire dal subtask 3, la sottoposizione ritorna un valore errato in alcune task, mentre in altre il mio codice viene considerato come esatto. Come posso risolvere? Prendo 15/100
Allego il mio codice:
int quadri(int N, long long M, int V[]) {

// Scrivete qui la vostra soluzione

long long B, sum = 0, j = 0, i = 1, Fino = N;

bool accettato = false;

while(Fino > 0){

    j = 0;

    sum = 0;

    for(i = 0; i < N - Fino; i++){

        sum = 0;

        //cout << " i = " << i << endl;

        while(sum <= M && j <= Fino){

            sum += V[i + j];

            j++;

        }

        if(sum > M) break;

    }

    if(Fino == N){

        for(i = 0; i < N; i++){

            sum += V[i];

        }

    }

    //cout << "Somma = " << sum << endl;

    if(sum <= M){

        return Fino;

    } else {

        Fino--;

    }

}

return Fino;

}

2

Ciao, prova con questo input:
8 15
3 1 3 2 3 1 3 2

4

Restituisce in output 5, è sbagliato?
Aggiornamento: sono riuscito a migliorare il codice, grazie al tuo output ho capito l’errore, ora resta soltanto il migliorare la velocità

5

La risposta corretta è 6 come che si può verificare anche manualmente. una buona idea, suggerita anche dal testo dell’esercizio, è quella di usare una sliding window che ti permette, anche, di risolvere il problema in maniera lineare.

6

sisi ti ringrazio, avevo sbagliato una condizione nel while

7

Devo studiare ancora lo sliding window come algoritmo, ora vedrò come farlo

8

di pomeriggio ho implementato l’algoritmo da te consigliato, ora prendo 45/100, il programma impiega troppo per eseguire vari testcase, qualcuno sa se è possibile implementare una ricerca binaria? E se possibile, come dovrei fare?

9

Il tuo programma va in TLE perché iteri ogni possibile valore che può assumere B, la ricerca binaria ti consente di scartare una grande quantità di soluzioni sicuramente sbagliate, ora devi solo implementare l’algoritmo della BS nel tuo codice e utilizzare il valore middle che ti calcoli come una possibile soluzione da testare e poi salire o scendere sulla base dell’esito del test.

1 Mi Piace
10

Scusa ma la corretta non dovrebbe essere 5? 3 +3+3+3+2 fa 14 e siamo a 5 numeri.Se metti 6 numeri tra le possibili combinazioni c’è anche 14+2 che supera 15 …

11

Le somme considerano solamente intervalli contigui di B elementi - dal testo:

potrà scegliere a propria discrezione un “blocco” consecutivo di B opere (non di più né di meno).

Le somme dei subarray di lunghezza 6 nell’input proposto sono:
3+1+3+2+3+1 = 13
1+3+2+3+1+3 = 13
3+2+3+1+3+2 = 14

Quindi per B = 6, non ci sono blocchi di somma S > M.