Lotteria dei quadri 15/100

Aiuto
1

Salve, sto provato a risolvere il problema abc_quadri (CMSocial - a social coding app) da qualche giorno. Ho provato vari modi ma nessuno andava bene e mi andavano fuori tempo. Ho riscritto il codice e mi da solo 15/100, ma non riesco a capire il perché. Qualcuno può aiutarmi?

int quadri(int N, long long M, int V[]) {
    
    int sum=0;
    int ans=0;
    int count=0;
    while(sum<M&&count<N){
    	sum+=V[count];
    	ans++;
    	count++;
	}
	if(sum<=M){
		return N;
	}
	count=0;
	while(sum>M&&count<N){
		sum-=V[count];
		ans--;
		count++;
	}
	if(count==N-1){
		ans=0;
	}
    return ans;
}
2

Ciao,
Da quanto ho capito, il tuo codice salva la somma di tutti gli elementi dell’array finché questa non supera M o arrivi alla fine dell’array. Poi, se la somma ha superato M, vengono rimossi i costi dei quadri dalla somma a partire dal primo elemento dell’array finché la somma non torna ad essere minore di M.

Il problema con questo approccio è che spesso trascura dei risultati. Prova con questo input:
6 8
1 2 3 3 4 9
L’ultimo quadro da solo ha valore > 8, quindi il risultato dovrebbe essere 0.

Suggerimento per trovare il problema:

Il codice smette di andare avanti nell’array quando la somma di quella parte dell’array supera M. Può essere che ci sia un’altra parte dell’array più avanti che superi M con il valore di un blocco di quadri di numero minore.

Suggerimento per la risoluzione del problema:

Io lo ho risolto con una sliding window, quindi usando due pointer che indicano una parte dell’array e lavorando con la somma di questa. Se ti può servire il codice fammi sapere.

3

Grazie per l’aiuto. Non essendo ancora molto pratico con i vari algoritmi gradirei se potessi mandare il tuo codice in maniera da capire anche l’implementazione. Grazie mille.

4 
#include <bits/stdc++.h>

using namespace std;

#define ll long long int

int quadri(int N, long long M, int V[]) {
    // Scrivete qui la vostra soluzione
    int res = -1;
    int i = 0, j = 0;
    ll sum = V[0];

    // anche solo il primo elemento va fuori limite
    if(sum > M) return 0;

    // se i supera j c'è un quadro che supera M --> ritorna 0
    // Se j è >= N-1 e la somma sta nel range sono arrivato alla fine senza dover togliere
    // più niente dalla somma
    while(j>=i && j<N-1) {
        // mando avanti quello di dx
        while(sum <= M && j < N-1) {
            j++;
            sum += V[j];
        }
        // la somma ora è maggiore di M, prima non lo era --> 
        // il risultato parziale è il numero di elementi che formano la somma prima dell'ultimo controllato
        // la somma degli elementi sarebbe j-i+1, senza l'ultimo tolgo 1
        if(res==-1) {   // non ho ancora trovato un valore di res
            if(sum <= M) res = j-i+1;   // corner case, arrivo ad N-1 ma la somma è valida
            else res = j-i;  
        }
        else {
            if(sum <= M) res = min(res, j-i+1);   // corner case, arrivo ad N-1 ma la somma è valida
            else res = min(res, j-i);
        } 

        // tolgo gli elementi di troppo
        while(sum > M && i<=j) {
            sum -= V[i];
            i++;
        }
    }

    if(j<i || res == -1) return 0;
    return min(res, (j-i+1));    // essendo alla fine non ho potuto aggiungere un elemento in più per superare M --> riaggiungo 1
}
5

Grazie mille.