# Pre\_oii treni subtask 4 e 5

**URL:** <https://forum.olinfo.it/t/pre-oii-treni-subtask-4-e-5/8313>\
**Category:** Aiuto\
**Created:** [12 Giugno 2023, 2:19pm UTC](https://forum.olinfo.it/t/pre-oii-treni-subtask-4-e-5/8313 "2023-06-12T14:19:10Z")\
**Posts on this page:** 7\
**Page:** 1

<div class="post-metadata">

**Author:** ![tbiz](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/t/3ec8ea/32.png) [@tbiz](https://forum.olinfo.it/u/tbiz)\
**Post date:** [12 Giugno 2023, 2:19pm UTC](https://forum.olinfo.it/t/pre-oii-treni-subtask-4-e-5/8313/1 "2023-06-12T14:19:10Z")

</div>

Buon pomeriggio,  
sto cercando di risolvere il problema treni: [CMSocial - a social coding app](https://training.olinfo.it/#/task/preoii_treni/statement) e ho scritto un codice che però risolve solo i subtask 1,2 e 3.  
La soluzione si basa sullo scorrere lungo gli array a e b e considerare di volta in volta una riga, controllando anche le due precedenti. L’algoritmo valuta se è meglio prendere il treno a o il treno b (eliminando in questo caso la scelta fatta alla riga precedente), raggiungendo quindi di volta in volta la soluzione ottima per quella data riga. Il codice risolve correttamente i primi 3 subtask ma poi restituisce “output incorrect” per tutti i test del 4 e del 5.

```auto
int tempo_massimo(int N, int a[], int b[])
{
    long long tot = 0; //durata totale aumentata progressivamente
    long long preadd = 0; //valore aggiunto alla riga precedente
    long long prepreadd = 0; //valore aggiunto due righe prima

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

        if(i == 0){ //alla prima riga considero semplicemente il treno di durata maggiore
            if (a[i] > b[i]){
                tot += a[i];
                preadd = a[i];
            }
            else{
                tot += b[i];
                preadd = b[i];
            }
            //cout << tot << " "<< preadd << " " << prepreadd << endl;
        }

        else if(i == 1){ //alla seconda riga valuto se è maggiore:
            if((b[i] - preadd) > a[i]){ //1) inserire il valore di b ed eliminare quello inserito alla riga prima
                tot += (b[i] - preadd);
                prepreadd = 0;
                preadd = b[i];
            }else{ //2) inserire solo il valore di a
                tot += a[i];
                prepreadd = preadd;
                preadd = a[i];
            }
            //cout << tot << " "<< preadd << " " << prepreadd << endl;
        }

        else{ //dalla terza riga in poi faccio la stessa cosa che con la seconda ma con un controllo ulteriore su "prepreadd"
            long long primoterm = 0;
            if(prepreadd == 0){ //se due righe prima non avevo preso nessun treno (per prendere alla riga prima il treno b), 
                                //dato che ora cambio la riga prima per non prendere nessun treno non ho più bisogno di lasciare vuoto due righe prima
                                //e posso cambiarlo per prendere il treno a
                                
                primoterm = b[i] - preadd + a[i-2];

            }else{
                primoterm = b[i] - preadd;
            }

            if (primoterm >= a[i]){ //controllo se mi conviene prendere b (con la condizione che ne deriva) oppure a
                tot += primoterm;
                prepreadd = 0; //aggiorno già coi valori che userò al prossimo ciclo
                preadd = b[i];
                
                
            }else{
                tot += a[i];
                prepreadd = preadd;
                preadd = a[i];
            }
            //cout << tot << " "<< preadd << " " << prepreadd << endl;
        }
    }
    return tot;
}

```

---

<div class="post-metadata">

**Author:** ![qwfwq](https://forum.olinfo.it/user_avatar/forum.olinfo.it/qwfwq/32/2974_2.png) [@qwfwq](https://forum.olinfo.it/u/qwfwq)\
**Post date:** [13 Giugno 2023, 3:24pm UTC](https://forum.olinfo.it/t/pre-oii-treni-subtask-4-e-5/8313/2 "2023-06-13T15:24:22Z")

</div>

ciao, con questo input:  
5  
4 10  
6 20  
20 25  
10 40  
5 15  
l’algoritmo restituisce 75 invece di 65.  
Questi sono invece i totali parziali che possono risultare utili per individuare le correzioni: 10 20 40 60 65.

---

<div class="post-metadata">

**Author:** ![tbiz](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/t/3ec8ea/32.png) [@tbiz](https://forum.olinfo.it/u/tbiz)\
**Post date:** [14 Giugno 2023, 7:59am UTC](https://forum.olinfo.it/t/pre-oii-treni-subtask-4-e-5/8313/3 "2023-06-14T07:59:37Z")

</div>

Ciao, grazie mille per la risposta.  
In realtà, però, eseguendo il programma sul mio pc restituisce correttamente 65, con anche i parziali da te indicati. Incollo nuovamente il codice in caso si sia perso qualcosa nel post precedente.

```auto
int tempo_massimo(int N, int a[], int b[])
{
    long long tot = 0; //durata totale aumentata progressivamente
    long long preadd = 0; //valore aggiunto alla riga precedente
    long long prepreadd = 0; //valore aggiunto due righe prima

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

        if(i == 0){ //alla prima riga considero semplicemente il treno di durata maggiore
            if (a[i] > b[i]){
                tot += a[i];
                preadd = a[i];
            }
            else{
                tot += b[i];
                preadd = b[i];
            }
            //cout << tot << " "<< preadd << " " << prepreadd << endl;
        }

        else if(i == 1){ //alla seconda riga valuto se è maggiore:
            if((b[i] - preadd) > a[i]){ //1) inserire il valore di b ed eliminare quello inserito alla riga prima
                tot += (b[i] - preadd);
                prepreadd = 0;
                preadd = b[i];
            }else{ //2) inserire solo il valore di a
                tot += a[i];
                prepreadd = preadd;
                preadd = a[i];
            }
            //cout << tot << " "<< preadd << " " << prepreadd << endl;
        }

        else{ //dalla terza riga in poi faccio la stessa cosa che con la seconda ma con un controllo ulteriore su "prepreadd"
            long long primoterm = 0;
            if(prepreadd == 0){ //se due righe prima non avevo preso nessun treno (per prendere alla riga prima il treno b), 
                                //dato che ora cambio la riga prima per non prendere nessun treno non ho più bisogno di lasciare vuoto due righe prima
                                //e posso cambiarlo per prendere il treno a

                primoterm = b[i] - preadd + a[i-2];

            }else{
                primoterm = b[i] - preadd;
            }

            if (primoterm >= a[i]){ //controllo se mi conviene prendere b (con la condizione che ne deriva) oppure a
                tot += primoterm;
                prepreadd = 0; //aggiorno già coi valori che userò al prossimo ciclo
                preadd = b[i];
                
                
            }else{
                tot += a[i];
                prepreadd = preadd;
                preadd = a[i];
            }
            //cout << tot << " "<< preadd << " " << prepreadd << endl;
        }
    }
    return tot;
}

```

---

<div class="post-metadata">

**Author:** ![qwfwq](https://forum.olinfo.it/user_avatar/forum.olinfo.it/qwfwq/32/2974_2.png) [@qwfwq](https://forum.olinfo.it/u/qwfwq)\
**Post date:** [14 Giugno 2023, 9:44am UTC](https://forum.olinfo.it/t/pre-oii-treni-subtask-4-e-5/8313/4 "2023-06-14T09:44:00Z")

</div>

Scusa, ho sicuramente fatto, inavvertitamente, una qualche modifica nel copia-incollare il codice precedente che non funziona correttamente con questo input:  
5  
7 21  
9 37  
32 75  
18 95  
36 2  
E questi sono i parziali: 21 37 96 132 168.

---

<div class="post-metadata">

**Author:** ![tbiz](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/t/3ec8ea/32.png) [@tbiz](https://forum.olinfo.it/u/tbiz)\
**Post date:** [14 Giugno 2023, 2:12pm UTC](https://forum.olinfo.it/t/pre-oii-treni-subtask-4-e-5/8313/5 "2023-06-14T14:12:21Z")

</div>

Grazie mille ancora, ho capito che in realtà non posso assumere che l’ottimo di due scelte fa sia ancora valido, quindi bisognerebbe ricontrollare tutte le scelte 🙄 Provo a pensare un nuovo algoritmo!

---

<div class="post-metadata">

**Author:** ![qwfwq](https://forum.olinfo.it/user_avatar/forum.olinfo.it/qwfwq/32/2974_2.png) [@qwfwq](https://forum.olinfo.it/u/qwfwq)\
**Post date:** [15 Giugno 2023, 4:16pm UTC](https://forum.olinfo.it/t/pre-oii-treni-subtask-4-e-5/8313/6 "2023-06-15T16:16:18Z")

</div>

Invece di fare ogni volta la scelta migliore controllando le 2 precedenti, prova a trovare la somma migliore che puoi fare a partire dalle 2 precedenti.  
In pratica le prime 2 somme sum[0] e sum[1] si trovano facimente e le hai già calcolate, ti serve solo iterare dalla somma successiva sum[i], considerando solo le 2 precedenti (sum[i-1], sum[i-2]) che già assommano i risultati migliori raggiunti fino ad allora.  
Il tuo codice fa in un qualche modo la stessa cosa ma non utilizza in maniera appropriata prepreadd.

---

<div class="post-metadata">

**Author:** ![tbiz](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/t/3ec8ea/32.png) [@tbiz](https://forum.olinfo.it/u/tbiz)\
**Post date:** [15 Giugno 2023, 4:58pm UTC](https://forum.olinfo.it/t/pre-oii-treni-subtask-4-e-5/8313/7 "2023-06-15T16:58:05Z")

</div>

> [@qwfwq](#):
>
> In pratica le prime 2 somme sum[0] e sum[1] si trovano facimente e le hai già calcolate, ti serve solo iterare dalla somma successiva sum[i], considerando solo le 2 precedenti (sum[i-1], sum[i-2]) che già assommano i risultati migliori raggiunti fino ad allora.

Sì, sono riuscito a implementare questa soluzione con un vector che si “riempie” progressivamente, anziché con una singola variabile. Grazie ancora per tutto!
