Buon giorno,
è da circa una settimana che cerco di risolvere questo esercizio, sto avendo molta difficolta a superare il testcase 13, 45, 46, 47, 48. Qualcuno ha qualche consiglio da darmi su come risolverli o su come arrivare alla soluzione? L’idea che ho usato per arrivare a 82 punti consiste nel capire quale è la posizione dell’ultima tesserina caduta, capire quale è l’altezza minima che mi permette a partire da quella tesserina di fare cadare tutte le altre a destra. Fatto ciò parto dalla prima tesserina e scorro tutte le altre e mi metto a controllare che la tesserina che sto guardando sia maggiore di H (l’altezza della tesserina minima per fa cadere quella a destra). Se è maggiore scambio le tesserine e faccio il controllo altrimenti continuo a scorrere. Quando ho finito di scorrere la prima volta le tesserine incremento H, punto alla tesserina precedente a quella caduta e rifaccio la stessa cosa fino a quando non ho trovato la soluzione o non ho fatto questa cosa anche per la prima tesserina.
Questo è il codice:
#include<bits/stdc++.h>
using namespace std;
typedef enum {
OK,
RISOLTO,
IMPOSSIBILE
} stato_t;
typedef struct {
int domino1;
int domino2;
} coppia_t;
//questa procedura invece simula sempre la caduta delle tesserina ma mi riempie il vettore flag e mi dice quali cadono e quali no
int simulateFalls(int tessere[], int N, int index)
{
int move=tessere[index]-1, pos=index;
for(int i=index+1;i<N;++i){
if(move>0){
--move;
pos=i;
if(tessere[i]-1>move)
move=tessere[i]-1;
}
else
break;
}
return pos;
}
stato_t correggi(int N, int altezze[], coppia_t* scambio)
{
int lastFall;
if((lastFall=simulateFalls(altezze, N, 0))==N-1){
//cout<<"OK \n";
return OK;
}
else{ //3, 2, 1, 2, 1, 2, 4 //3, 3, 1, 1, 2, 1, 2 //3, 1, 1, 2, 1, 5 //4, 4, 1, 1, 1, 1 //3, 3, 1, 1, 1, 3, 2, 1
int high=1, pos=lastFall+1;
for(int i=lastFall+1;i<N;++i){
if((i=simulateFalls(altezze, N, i))==N-1)
break;
pos=i+1;
}
high+=pos-lastFall;
//cout<<"high: "<<high<<"\n";
//cout<<"ciclo annidato \n";
for(int i=lastFall;i>-1;--i, ++high){ //controllo tutti i numeri prima dell'ultima pedina caduta
for(int j=0;j<N;++j){
//cout<<"i: "<<i<<" j: "<<j<<"\n";
if(altezze[j]>=high&&altezze[j]>altezze[i]){
swap(altezze[i], altezze[j]);
if(simulateFalls(altezze, N, 0)==N-1){
scambio->domino1=i;
scambio->domino2=j;
//cout<<i<<" "<<j<<"\n";
return RISOLTO;
}
swap(altezze[i], altezze[j]);
}
}
}
}
//cout<<"IMPOSSIBILE \n";
return IMPOSSIBILE;
}