# Aiuto Lotteria di Quadri 0/100

**URL:** <https://forum.olinfo.it/t/aiuto-lotteria-di-quadri-0-100/7279>\
**Category:** Aiuto\
**Created:** [20 Aprile 2022, 6:21pm UTC](https://forum.olinfo.it/t/aiuto-lotteria-di-quadri-0-100/7279 "2022-04-20T18:21:15Z")\
**Posts on this page:** 2\
**Page:** 1

<div class="post-metadata">

**Author:** ![FrancescoFam](https://forum.olinfo.it/user_avatar/forum.olinfo.it/francescofam/32/1455_2.png) [@FrancescoFam](https://forum.olinfo.it/u/FrancescoFam)\
**Post date:** [20 Aprile 2022, 6:21pm UTC](https://forum.olinfo.it/t/aiuto-lotteria-di-quadri-0-100/7279/1 "2022-04-20T18:21:15Z")

</div>

```auto
int quadri(int N, long long M, int V[]) {
    // Scrivete qui la vostra soluzione
    int B=N/2;
    bool a=false;
    for(int i=0;i<N;i++){
       long long tot=0;
       for(int j=i;j<B+i;j++)tot+=V[j];
       if(tot>M){
          if(a){
             return B--;
          }else{
             i=0;
             B--;
          }
       }else if(i==N-2){
          i=0;
          B++;
          a=true;
       }
    }
    return B;
 }

```

Ho pensato ad un approccio diverso, dato che un precedente codice che avevo scritto non andava oltre il 45. Nonostante gli esempi di test in locale siano giusti, sul sito degli allenamenti il risultato è output non corretto.

---

<div class="post-metadata">

**Author:** ![lorenzoferrari](https://forum.olinfo.it/user_avatar/forum.olinfo.it/lorenzoferrari/32/683_2.png) [@lorenzoferrari](https://forum.olinfo.it/u/lorenzoferrari)\
**Post date:** [21 Aprile 2022, 7:01am UTC](https://forum.olinfo.it/t/aiuto-lotteria-di-quadri-0-100/7279/2 "2022-04-21T07:01:19Z")

</div>

Ciao, provando la tua soluzione in locale mi sbaglia gli esempi 🤔

Per risolvere questo problema ci sono almeno 2 strategie:

- 

[ricerca binaria](https://forum.olinfo.it/t/ricerca-binaria-for-dummies/7224) sulla risposta. Riesci a controllare se una lunghezza B va bene in \mathcal{O}(n)?

- 

sliding window. Per ogni i, considera l’intervallo [i,j] con j massimo e somma \leq M. C’è un modo per trovare questi intervalli in \mathcal{O}(n)? Una volta che hai gli intervalli, cos’è la risposta?