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.

Anch’io ho suddiviso l’algoritmo in due procedure distinte: prima e dopo il punto di interruzione del domino ma dall’esito sembra non essere corretto eppure l’ho testato su un’infinità di casi.
Qualcuno potrebbe suggerirmi una serie di testcase “strani” per poter scovare il bug? Grazie.