Selezioni nazionali IOI 2002

Borse di studio (`BORSE`, `D`=2)

Il problema

Alla fine dell'anno scolastico, il preside dell'Istituto Tecnico Alan Turing scopre di avere una plusvalenza di bilancio di N migliaia di euro. Il Consiglio d'Istituto decide di destinare tale plusvalenza distribuendola sottoforma di borse di studio da assegnare agli studenti meno abbienti.

Per farlo, viene per prima cosa stilata una graduatoria degli alunni della scuola in ordine di reddito (il primo nella graduatoria è lo studente con reddito più basso). A questo punto gli N mila euro vengono redistribuiti rispettando i seguenti vincoli:

se uno studente riceve x migliaia di euro, nessuno degli studenti che lo precedono in graduatoria può ricevere meno di x migliaia di euro;
ciascuno studente riceve un numero intero di migliaia di euro (eventualmente zero).

Dovete scrivere un programma che, data l'entità N della plusvalenza, stabilisca in quanti e quali modi diversi possono essere ripartite le borse di studio in modo da rispettare i vincoli indicati.

Dati in input

Il file di input, di nome input.txt, contiene una sola riga, la quale contiene il singolo numero intero N.

Dati in output

Il file di output, di nome output.txt, è costituito da tante righe quanti sono i modi diversi di ripartire il denaro in borse di studio. Ciascuna riga è costituita da una sequenza di numeri interi positivi, separati da uno spazio. Se su una riga compaiono (in questo ordine) gli interi: x₁ x₂ ... x_k significa che, in quella ripartizione, al primo studente in graduatoria spetteranno x₁ migliaia di euro, al secondo spetteranno x₂ migliaia di euro, ..., al k-esimo spetteranno x_k migliaia di euro; gli studenti dopo il k-esimo non riceveranno alcuna borsa di studio.

Importante. L'ordine in cui compaiono le righe nel file di output non è importante. È invece importante che le possibili ripartizioni compaiano tutte e senza ripetizioni.

Assunzioni

il tempo limite di esecuzione è fissato in 4 secondi;
1 <= N <= 50;
la scuola ha più di 100 studenti;
il file di input non contiene altri caratteri oltre a quelli indicati nel testo;
il file di output non deve contenere altri caratteri oltre a quelli indicati nel testo; inoltre, il programma non deve produrre alcun altro input/output oltre a quelli indicati: deve limitarsi a leggere il file di input e a scrivere i risultati sul file di output;

i file di input/output vanno specificati senza alcuna indicazione di path, e quindi verranno aperti in C con un'istruzione tipo

			fr = fopen( "input.txt", "r" );
			fw = fopen( "output.txt", "w" );

e in Pascal con un'istruzione tipo

			assign( fr, 'input.txt' ); reset( fr );
			assign( fw, 'output.txt' ); rewrite( fw );

Esempio di input/output

File input.txt

File output.txt

1 1 1 1 1 1
2 1 1 1 1
3 1 1 1
2 2 1 1
4 1 1
3 2 1 
5 1 
2 2 2
4 2
3 3
6