Aiuto con Treni (pre-oii 2018) (5/100)

Buongiorno,
mi sto scervellando da un po’ su come sia possibile che non funzioni il mio codice per treni… Risultano errati uno dei casi del subtask 2 e tutti i casi successivi. Qualcuno ha idea di come sia possibile?

#include <vector>
#include <algorithm>

using namespace std;

vector<int> Action;
vector<int> OptTimeOf;

int opt(int pos, bool GiveTime, int a[], int b[], bool Override)
{
    if (!Override && GiveTime && OptTimeOf[pos] != -1) return OptTimeOf[pos];
    else if (!Override && Action[pos] != -1) return Action[pos];
    
    if (pos == 0)
    {
        if (a[0] > b[0]) Action[0] = 0;
        else Action[0] = 1;
        OptTimeOf[0] = max(a[0],b[0]);
        
        if (GiveTime) return OptTimeOf[0];
        else return Action[0];
    }
    else
    {
        if (b[pos] > a[pos] + opt(pos-1,true,a,b,false))
        {
            Action[pos] = 1;
            if (pos > 1 && Action[pos-2] == 2) opt(pos-2,false,a,b,true);
            Action[pos-1] = 2;
        }
        else
        {
            Action[pos] = 0;
            Action[pos-1] = opt(pos-1,false,a,b,false);
        }
        
        if (Action[pos] == 0) OptTimeOf[pos] = a[pos];
        else if (Action[pos] == 1) OptTimeOf[pos] = b[pos];
        else OptTimeOf[pos] = 0;
        
        if (Action[pos-1] == 0) OptTimeOf[pos] = a[pos];
        else if (Action[pos-1] == 1) OptTimeOf[pos] = b[pos];
        else OptTimeOf[pos-1] = 0;
        
        if (GiveTime) return OptTimeOf[pos];
        else return Action[pos];
    }
}

int tempo_massimo(int N, int a[], int b[])
{
    Action = vector<int> (N, -1); // 0 = a, 1 = b
    OptTimeOf = vector<int> (N, -1);
    
    int Time = 0;
    
    opt(N-1,false,a,b,false);
    
    for (int i = 0; i < N; i++)
    {
        if (Action[i] == 0) Time += a[i];
        else if (Action[i] == 1) Time += b[i];
    }
    
    return Time;
}

Versione integrata con grader:

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#include <vector>
#include <algorithm>

using namespace std;

vector<int> Action;
vector<int> OptTimeOf;

int opt(int pos, bool GiveTime, int a[], int b[], bool Override)
{
    if (!Override && GiveTime && OptTimeOf[pos] != -1) return OptTimeOf[pos];
    else if (!Override && Action[pos] != -1) return Action[pos];
    
    if (pos == 0)
    {
        if (a[0] > b[0]) Action[0] = 0;
        else Action[0] = 1;
        OptTimeOf[0] = max(a[0],b[0]);
        
        if (GiveTime) return OptTimeOf[0];
        else return Action[0];
    }
    else
    {
        if (b[pos] > a[pos] + opt(pos-1,true,a,b,false))
        {
            Action[pos] = 1;
            if (pos > 1 && Action[pos-2] == 2) opt(pos-2,false,a,b,true);
            Action[pos-1] = 2;
        }
        else
        {
            Action[pos] = 0;
            Action[pos-1] = opt(pos-1,false,a,b,false);
        }
        
        if (Action[pos] == 0) OptTimeOf[pos] = a[pos];
        else if (Action[pos] == 1) OptTimeOf[pos] = b[pos];
        else OptTimeOf[pos] = 0;
        
        if (Action[pos-1] == 0) OptTimeOf[pos] = a[pos];
        else if (Action[pos-1] == 1) OptTimeOf[pos] = b[pos];
        else OptTimeOf[pos-1] = 0;
        
        if (GiveTime) return OptTimeOf[pos];
        else return Action[pos];
    }
}

int tempo_massimo(int N, int a[], int b[])
{
    Action = vector<int> (N, -1); // 0 = a, 1 = b
    OptTimeOf = vector<int> (N, -1);
    
    int Time = 0;
    
    opt(N-1,false,a,b,false);
    
    for (int i = 0; i < N; i++)
    {
        if (Action[i] == 0) Time += a[i];
        else if (Action[i] == 1) Time += b[i];
    }
    
    return Time;
}

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;
}

Mi sembra che tu ti stia complicando la vita, è possibile risolvere questo problema in poche righe.
E’ possibile sapere se gli errori sono risultati errati o timed out?

Indizio: E’ possibile risolvere il problema utilizzando un solo ciclo for da 0 a n, senza creare nuove variabili e neanche usare if ed else. Tutti i dati che ti servono ti vengono gia dati all’inizio.

P.S. Ti prego metti almeno un paio di commenti in giro per il codice prossima volta, è abbastanza difficile capire cosa fa cosa senza sapere il ragionamento dietro.

1 Mi Piace

Gli errori sono solo output errati; comunque, provero’ a ripensare al problema con il tuo indizio. Grazie mille.
Riconosco ora che e’ un bel po’ di codice da interpretare senza commenti, quindi mi scuso… cerchero’ di pensarci prima la prossima volta!

Sono riuscito a risolverlo con un solo ciclo for, grazie mille della dritta!!!
Se qualcuno stesse leggendo questo post, non fatelo come ho fatto io originariamente!

1 Mi Piace