# Problema abc quadri

**URL:** <https://forum.olinfo.it/t/problema-abc-quadri/8876>\
**Category:** Aiuto\
**Created:** [7 Giugno 2024, 8:46pm UTC](https://forum.olinfo.it/t/problema-abc-quadri/8876 "2024-06-07T20:46:14Z")\
**Posts on this page:** 3\
**Page:** 1

<div class="post-metadata">

**Author:** ![TizioGrigio0](https://forum.olinfo.it/user_avatar/forum.olinfo.it/tiziogrigio0/32/1819_2.png) [@TizioGrigio0](https://forum.olinfo.it/u/TizioGrigio0)\
**Post date:** [7 Giugno 2024, 8:46pm UTC](https://forum.olinfo.it/t/problema-abc-quadri/8876/1 "2024-06-07T20:46:14Z")

</div>

Il mio programma è in grado di **risolvere tutti i problemi** che gli vengono posti (tranne il primo esempio per qualche ragione) e più della metà dei problemi del sub task 5, dove sfora con il tempo ( **timed out** ).

Vorrei sapere se nel mio programma è possibile modificare qualcosa per **ottimizzare** i tempi abbastanza da permettere al mio programma di risolverlo o se ho proprio sbagliato algoritmo.

```auto
#include <algorithm>

using namespace std;

int quadri(int N, long long M, int V[]) {
    
    int B = N;

    for(int i=0; i<N-1; i++) { //Controlla se esiste un quadro oltre il massimo, e ritorna subito 0 evitando di calcolare tutto
        if(!(V[i] < M)) return 0; 
    }
    
    for(int i=0; i<N-1; i++) { //Per ogni quadro
        long long int sum=0;
        int newB=0;
        for(int j=i; j<N and sum<M; j++) { //Vedi i successivi finchè non esci
            sum+=V[j];
            if(sum<M) newB++;
        } //J

        B = min(B, newB);
        if(newB == N-i) {if(B != N) B++; break; } //Se arriva alla fine senza problemi, ha trovato il nuovo risultato

    } //I
    return B;
}

```

Ho cercato di mettere più commenti possibile in modo da semplificare la revisione.  
Ringrazio in anticipo per l’aiuto.

---

<div class="post-metadata">

**Author:** ![TizioGrigio0](https://forum.olinfo.it/user_avatar/forum.olinfo.it/tiziogrigio0/32/1819_2.png) [@TizioGrigio0](https://forum.olinfo.it/u/TizioGrigio0)\
**Post date:** [8 Giugno 2024, 8:03pm UTC](https://forum.olinfo.it/t/problema-abc-quadri/8876/2 "2024-06-08T20:03:21Z")

</div>

UPDATE:  
Sono riuscito a risolvere il problema, era l’algoritmo sbagliato, però comunque non riesce a risolvere il primo caso di test. (I calcoli che fa sono gli stessi e danno gli stessi risultati, solo con molti meno passaggi, ma mi piacerebbe sapere perché non riesce a risolvere il primo esempio).  
Il primo esempio è:

> 4 8  
> 1 2 3 4

il mio algoritmo da come risultato 3 anche se il risultato è 2, se qualcuno è in grado di dirmi dove sbaglia il mio algoritmo ne sarei davvero grato.

---

<div class="post-metadata">

**Author:** ![0xA1E](https://forum.olinfo.it/user_avatar/forum.olinfo.it/0xa1e/32/2161_2.png) [@0xA1E](https://forum.olinfo.it/u/0xA1E)\
**Post date:** [6 Marzo 2025, 10:48am UTC](https://forum.olinfo.it/t/problema-abc-quadri/8876/3 "2025-03-06T10:48:56Z")

</div>

È questo che è rotto:

```auto
 if(newB == N-i) {if(B != N) B++; break; } //Se arriva alla fine senza problemi, ha trovato il nuovo risultato

```

Quando tu arrivi a `i=2` avrai `3+4 = 7 < 8` quindi `newB = 2`. Avrai che `newB = N - i` e poi tu incrementi B → B = 3 ed esci