Cerca le somme

Filippo, il nuovo assistente del sindaco di Roma, è molto preoccupato.
Alla prima riunione in cui ha partecipato, si sono discusse le varie voci del bilancio delle olimpiadi.
Lui ha trascritto tutti questi numeri su un foglio, ma poi lo ha lasciato nei pantaloni che sono finiti in lavatrice.
Per fortuna non tutto è perduto: si intravedono le cifre, e lui si ricorda qual era il totale del bilancio previsto per le olimpiadi.

Il vostro compito è quello di aiutare Filippo a capire quanti sono i modi di comporre le cifre, nel modo descritto di seguito, per poter ricostruire correttamente il bilancio delle olimpiadi.
Dato il foglio con le cifre, vogliamo inserire alcuni segni + in modo che il risultato delle operazioni di somma sia quello che si ricorda Filippo.

Ad esempio, data la sequenza di cifre decimali

1 2 3 4 5 6 7

possiamo inserire quattro operatori + in modo tale che il risultato delle somme sia uguale a 100.
In questo particolare caso una possibile soluzione è

1+23+4+5+67

Aiuta Filippo a trovare tutti i possibili modi di ottenere la somma data.

Dati di input

Il file input.txt contiene tre righe di testo.

  • Nella prima riga c’è un singolo numero intero positivo N che ci dice quante sono le cifre decimali nel foglio di Filippo.
  • Nella seconda riga del file vi sono le cifre decimali separate tra loro da spazi.
  • Nella terza riga del file c’è il totale del bilancio, ovvero il valore che deve essere ottenuto con le operazioni di somma.

Dati di output

Il file output.txt contiene una riga per ciascuna soluzione esatta trovata; la riga contiene le posizioni dei segni + separate da spazi.
Se una posizione ha valore i, significa che il corrispondente segno + segue la i-esima cifra.

Assunzioni

  • La stessa cifra può apparire più volte nella sequenza.
  • Vengono date al più N=9 cifre.
  • È garantito che esiste almeno una soluzione.

Esempi di input/output

input.txt output.txt
71
2 3 4 5 6 7
100
1 3 4 5
1 2 4 6
82
1 3 4 5 1 8 9
105
1 2 3 4 5 6
1 2 4 6 7
95
4 3 2 1 2 3 4 5
101
1 2 3 5 7
1 2 4 6 7
1 3 4 5 6 7
1 3 4 6 8
2 3 4 5 6 8
1 3 5 7 8
2 4 5 6 7 8

/*
    www.valcon.it
    GATOR 2015 - Cerca le somme
*/    

#include

int     cifre[10];       // 0, x, x, x, x, x, x, x, x, x
int segni_piu[10];       // 0, 0, 0, 0, 0, 0, 0, 0, 0, 0

int  N;
long TOTALE;
int  i;

FILE* fin;
FILE* fout;
	
void out_sol()
{
	for(i=1; i < N; i++)
		if(segni_piu[i] != 0)
		    fprintf(fout,"%d ", i);
	fprintf(fout, "\n");
}

void soluzione(int passo, long Tp, long T)
{	
	if(passo == N)
	{
	    if(T+Tp == TOTALE)    
	        out_sol();
    }
	else
	{
		segni_piu[passo]=0;	soluzione(passo+1, Tp*10+cifre[passo+1], T   );
		segni_piu[passo]=1;	soluzione(passo+1, cifre[passo+1]      , T+Tp);		
	}	    
}

int main()
{
	fin =fopen( "input.txt","r");
	fout=fopen("output.txt","w");
	
	fscanf(fin, "%d", &N);	
	for(i=1; i <= N; i++)
	    fscanf(fin, "%d", &cifre[i]);
	fscanf(fin, "%ld", &TOTALE);
	
	soluzione(1, cifre[1], 0);  // opera dopo la prima cifra: parziale = 1° cifra, totale = 0
	return 0;
}

---