Ciao a tutti, stavo provando a risolvere treno (CMSocial - a social coding app) 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
#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.