Lotteria di quadri (execution killed)

Chiarimenti
1 
#include <bits/stdc++.h>
using namespace std;

vector<int> s;
bool babbo;
int c=0, u, B=0;

int quadri(int N, long long M, int V[]) {
    int i=0;
    
    if(!babbo){
        u=N;
        babbo=true;

        for(int x=0; x<N; x++) s[x]=V[x];
    }

    for(int x=0; x<u; x++) if(s[i]>M) return B;
       
    B++;
    c++;
    u--;

    while((c+i)<(N-1)){
        s[i]+=V[c+i];
        ++i;
    }

    return quadri(N, M, V);
}

l’algoritmo crusha appena chiama la funzione, oppure quando returna dentro se stessa.
sono abbastanza sicuro di aver fatto una cosa illegalissima, solo che è il primo esercizio che faccio sulla ricerca o quello che è. Sarei molto felice se mi faceste capire l’errore in modo da capire meglio l’argomento, grazie in anticipo.

2

Più che lavorare direttamente sul codice, puoi spiegare passo passo cosa fa il tuo algoritmo?

3

i = indice, B = soluzione, M = massimale da non superare, babbo= bool per fare le istruzioni sotto la condizione una sola volta, u= N che ogni volta diminuisce per evitare che l’algoritmo confronti un elemento, già confrontato, inutilmente, vector s = vettore parallelo su cui verrà istituita la somma per andare di coppie fino a gruppi da n, c = metodo per far partire V[i] più avanti (servirà quando la funzione ritornerà se stessa)

la prima condizione nel for in realtà sarà l’operazione fondamentale per il ritorno della funzione, essendo che solo quando sarà vera la funzione terminerà ritornando il valore B. La prima volta quel for confronterà con M i quadri singoli, e nel caso, ritornerà 0 essendo che anche vendere solo un quadro porterebbe una perdita a Fabio. Dopo il for siamo sicuri che almeno un quadro possa essere comprato senza perdite, quindi incrementiamo B, c e decrementiamo u. c incrementata servirà per eseguire correttamente la somma tra il vettore parallelo s e V: s[0] si sommerà con s[1] e così via creando nel vettore s una somma di tutte le combinazioni adiacenti possibili nel vettore V.
dopo di che ritorniamo la funzione in modo tale che si ripeta questo meccanismo ma con le coppie di quadri adiacenti, e qui servirà la decrementazione di u, per fare in modo che l’algoritmo non prenda in considerazione s[3] che vale quanto V[3].
Dopo aver controllato che anche prendendo 2 quadri adiacenti Fabio non ci perde, facciamo lo stesso procedimento per creare i gruppi da 3 quindi s[0] che conterrà (V[0] + V[1]) si sommerà con V[2] diventando così (V[0] + V[1] + V[2]) mentre s[1] sarà (V[1] + V[2] + V[3]) e così si confronteranno i gruppi da 3 quadri consecutivi.
P.S. l’ho modificato mettendo anche una condizione alla fine per il quale se B != N allora ritorna la funzione, nel caso contrario ritorna B, in modo che sia pure sicuro che se uno può comprare TUTTI i quadri senza che Fabio ci perda allora la funzione si ferma lì a forza.

incollo qui il nuovo codice:

#include <bits/stdc++.h>
using namespace std;

vector<int> s;
bool babbo;
int c=0, u, B=0, i=0;

int quadri(int N, long long M, int V[]) {
    i=0;
    
    if(!babbo){
        u=N;
        babbo=true;

        for(int x=0; x<N; x++) s[x]=V[x];
    }

    for(int x=0; x<u; x++) if(s[i]>M) return B;
       
    B++;
    c++;
    u--;

    while((c+i)<(N-1)){
        s[i]+=V[c+i];
        ++i;
    }

    if(B != N) return quadri(N, M, V);
    return B;
}
4

Ciao, ho trovato un po’ di bug qua e là:

  • s deve essere un vector<long long>
  • s inizialmente è vuoto, dovrebbe avere size N
  • Nel for in cui controlli se c’è un valore maggiore di M iteri sulle x ma hai scritto s[i]
  • Nel while finale non dovrebbe essere <N-1 ma <N, alternativamente <=N-1

Maybe next time debugga un po’ con i casi d’esempio, sicuramente è più veloce che chiedere qui :sweat_smile:

Also in questo modo hai una complessità di O(N^2), per migliorare dovresti usare una binary search o meglio una sliding window .

5

non comprendo come io abbia fatto a non vedere alcuni degli errori tipo la i come indice al posto della x. Ma biasimo me stesso, essendo che sto cercando di studiare troppe cose in troppo poco tempo, e la sera in cui ho fatto il problema ero in burnout. Comunque debuggo sempre con gli esempi ma mi dava errore anche su vsc, e adesso so perchè, comunque grazie mille dell’aiuto, ti segno come soluzione ma penso che farò da capo il problema con la binary search che è l’obbiettivo dell’esercizio.

1 Mi Piace