# Aiuto con Treni (20/100)

**URL:** <https://forum.olinfo.it/t/aiuto-con-treni-20-100/8906>\
**Category:** Aiuto\
**Created:** [18 Giugno 2024, 10:16pm UTC](https://forum.olinfo.it/t/aiuto-con-treni-20-100/8906 "2024-06-18T22:16:19Z")\
**Posts on this page:** 3\
**Page:** 1

<div class="post-metadata">

**Author:** ![Malmo](https://forum.olinfo.it/user_avatar/forum.olinfo.it/malmo/32/2653_2.png) [@Malmo](https://forum.olinfo.it/u/Malmo)\
**Post date:** [18 Giugno 2024, 10:16pm UTC](https://forum.olinfo.it/t/aiuto-con-treni-20-100/8906/1 "2024-06-18T22:16:19Z")

</div>

Ciao a tutti, stavo provando a risolvere treno ([CMSocial - a social coding app](https://training.olinfo.it/#/task/preoii_treni/statement)) e ero arrivato a questo codice che, da un output incorretto in tutti i test delle subtask 4 e 5, non riesco a trovare l’errore nella mia logica, qualcuno ha in mente un esempio nel quale il mio codice non funzionerebbe?  
Grazie

```C++
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

//INIZIO CODICE DA INVIARE
#include <algorithm>
using namespace std;

bool scegliB(int i, int a[], int b[]){ //TODO: implementare memoization (il codice è sotto il tempo minimo comunque ma ottimizzare non fa mai male)
  if(i==0){ //dato che il primo giorno si possono prendere entrambi i treni senza conseguenze, si può considerare qualunque linea abbia una durata maggiore quel giorno per controllare quale sarebbe la mossa migliore se non si aspettasse
    if(b[0]>a[0]){
      return true; //se b[0]>a[0] allora all'indice 0 bisognerebbe scegliere b escludendo un eventuale attesa
    }else{
      return false; //se b[0]<a[0] allora all'indice 0 bisognerebbe scegliere a escludendo un eventuale attesa
    }
  }
  if (a[i]>=b[i]){ //in qualunque caso dove a[i]>b[i] conviene scegliere a rispetto a b dato che a non comporta mai conseguenza per gli altri giorni
    return false;
  }else{
    int temp;
    if(scegliB(i-1, a, b)){ //temp=scelta ottimale nel giorno precedente (esclusa un'eventuale attesa)
      temp=b[i-1];
    }else{
      temp=a[i-1];
    }
    if(b[i]>a[i]+temp){
      return true; //se b[i]>a[i]+(scelta migliore tra a e b)[i-1] allora la scelta ottimale qui è b
    }
  }
  return false; // se si arriva qui vuol dire che tutte le altre condizioni erano false e quindi b[i]<a[i]+(scelta migliore tra a e b)[i-1], dunque, la scelta ottimale è a[i]
}

int tempo_massimo(int N, int a[], int b[])
{
  long long int tempotot=0;
  for(int i=N-1; i>=0; i--){
    if(scegliB(i, a, b)){ //se la funzione scegliB ritorna true, b è la scelta ottimale in questo caso, altrimenti a è la scelta ottimale (l'attesa è già implementata)
      tempotot+=b[i];
      i--; //se si usa b[i] si scende di un'ulteriore posizione perché bisogna saltare il giorno precedente in caso si usi b
    }else{
      tempotot+=a[i];
    }
  }
  return tempotot;
}
//FINE CODICE DA INVIARE
int main()
{
    int n;
    FILE *in = stdin, *out = stdout;
    assert(fscanf(in, "%d", &n) == 1);

    int *a = (int*)calloc(n, sizeof(int));
    int *b = (int*)calloc(n, sizeof(int));

    for(int i=0; i<n; i++){
      assert(fscanf(in, "%d", a + i) == 1);
      assert(fscanf(in, "%d", b + i) == 1);
    }
    int answ = tempo_massimo(n, a, b);
    fprintf(out, "%d\n", answ);

    free(a);
    free(b);

    fclose(in);
    fclose(out);

    return EXIT_SUCCESS;
}

```

Il codice che ho scritto io è compreso tra i commenti “INIZIO CODICE DA INVIARE” e “FINE CODICE DA INVIARE” a linee 6 e 47.

EDIT: Ho modificato int tempotot e l’ho cambiato a long long int nel caso fosse un problema di numeri troppo elevati, da lo stesso risultato.  
Probabilmente serve un approccio diverso ma sono curioso del perché questo non funzioni.

---

<div class="post-metadata">

**Author:** ![fve5](https://forum.olinfo.it/user_avatar/forum.olinfo.it/fve5/32/3229_2.png) [@fve5](https://forum.olinfo.it/u/fve5)\
**Post date:** [19 Giugno 2024, 6:03am UTC](https://forum.olinfo.it/t/aiuto-con-treni-20-100/8906/2 "2024-06-19T06:03:53Z")

</div>

Prova il caso:

```auto
4
1 1
1 2
1 3
1 4

```

---

<div class="post-metadata">

**Author:** ![Malmo](https://forum.olinfo.it/user_avatar/forum.olinfo.it/malmo/32/2653_2.png) [@Malmo](https://forum.olinfo.it/u/Malmo)\
**Post date:** [19 Giugno 2024, 7:33pm UTC](https://forum.olinfo.it/t/aiuto-con-treni-20-100/8906/3 "2024-06-19T19:33:51Z")

</div>

Grazie mille dell’esempio, non ci avevo pensato