Chiarimenti nel capire i Test Case errati traccia: Soleone sul lungomare


#1

Salve a tutti, mi sto esercitando per la seguente traccia lungomare.pdf ,con il codice che posterò tra qualche riga riesco a superare quasi tutti i test case tranne i seguenti:
Subtask 5 023; Subtask 6 037; Subtask 7 056; Subtask 8 084 095 099.
La cosa bella è che dovrebbero essere i testcase più facili, visto che non ci sono vincoli importanti.
Eccovi il codice:

long long int percorri(int N, long long int L, long long int D[], long long int P[]) {
    long long int passerellaCorrente = 0;
    long long int percorso = D[0];

    bool primasosta=false;
    int spiaggiaSosta = 0;
    long long int massimo=0;
    for(int u=0;u<N;u++){
        long long int calcolo = 0;
        passerellaCorrente=P[u];
        if(primasosta==false) {calcolo=D[u];}
        else{
            calcolo=D[u]-D[spiaggiaSosta]+P[spiaggiaSosta];
        }
        if(passerellaCorrente<calcolo && passerellaCorrente<(L-D[u])){
            spiaggiaSosta=u;
            primasosta=true;
            percorso=calcolo+P[u];
            if(percorso>massimo)massimo=percorso;
        }
    }
    if(massimo==0 || massimo >L){massimo=L;}
	return massimo;
}

#2

Un input in cui il tuo programma sbaglia è:

2 10
5 6
3 1

#3

Grazie per la rapida risposta,
ho provato con una ricerca iniziale per individuare la prima sosta valida, adesso risolvo il tuo test case ma la situazione risulta invariata in piattaforma.

long long int percorri(int N, long long int L, long long int D[], long long int P[]) {
    long long int passerellaCorrente = 0;
    long long int percorso = D[0];

    bool primasosta=false;
    int spiaggiaSosta = 0;
    long long int massimo=0;


    long long int minimo=L;
    int posMinimo=-1;

    for(int j=0;j<N;j++){
        if((P[j]-D[j])<minimo){
            minimo=(P[j]-D[j]);
            posMinimo=j;

        }
    }

    for(int u=posMinimo;u<N;u++){
        long long int calcolo = 0;
        passerellaCorrente=P[u];
        if(primasosta==false) {calcolo=D[u];}
        else{
            calcolo=D[u]-D[spiaggiaSosta]+P[spiaggiaSosta];
        }

if(passerellaCorrente<calcolo && passerellaCorrente<(L-D[u])){
            spiaggiaSosta=u;
            primasosta=true;
            percorso=calcolo+P[u];
            if(percorso>massimo)massimo=percorso;
        }
  }
    if(massimo==0 || massimo >L){massimo=L;}
	return massimo;
}

#4

Scusami ho postato il codice errato:

long long int percorri(int N, long long int L, long long int D[], long long int P[]) {
    long long int passerellaCorrente = 0;
    long long int percorso = D[0];

    bool primasosta=false;
    int spiaggiaSosta = 0;
    long long int massimo=0;


    long long int minimo=L;
    int posMinimo=-1;

    for(int j=0;j<N;j++){
        if((2*P[j]+D[j])<minimo){
            minimo=(2*P[j]+D[j]);
            posMinimo=j;
        }
    }

    for(int u=posMinimo;u<N;u++){
        long long int calcolo = 0;
        passerellaCorrente=P[u];
        if(primasosta==false) {calcolo=D[u];}
        else{
            calcolo=D[u]-D[spiaggiaSosta]+P[spiaggiaSosta];
        }

        if(passerellaCorrente<calcolo && passerellaCorrente<(L-D[u])){
            spiaggiaSosta=u;
            primasosta=true;
            percorso=calcolo+P[u];
            if(percorso>massimo)massimo=percorso;
        }
  	}
    if(massimo==0 || massimo >L){massimo=L;}
	return massimo;
}

#5

L’errore non è nell’implementazione ma nell’algoritmo in sé, quella modifica è abbastanza inutile se pensi ad esempio al caso:

3 10
1 5 6
1 3 1

#6

Ok grazie, ho capito il problema.