Pazza gioia 82/100

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

Ho trattato il problema parecchio tempo fa e non ricordo bene comunque:

Ho trovato tutte le posizioni nelle quali si arresta la caduta e se la distanza fra la prima e l’ultima supera … la soluzione è impossibile. Inoltre ho gestito le zone di copertura:

  1. E’ possibile che ci siano tessere che è possibile rimuovere senza che questo blocchi la catena di cadute se una di queste è della lunghezza che serve è fatta.

  2. inoltre ho gestito diversamente due situazioni:

  • la tessera che prendo viene prima della fascia da coprire

  • la tessera che prendo viene dopo della fascia da coprire.