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:

  1. se uno studente riceve x migliaia di euro, nessuno degli studenti che lo precedono in graduatoria può ricevere meno di x migliaia di euro;
  2. 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: x1 x2 ... xk significa che, in quella ripartizione, al primo studente in graduatoria spetteranno x1 migliaia di euro, al secondo spetteranno x2 migliaia di euro, ..., al k-esimo spetteranno xk 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

Esempio di input/output

File input.txt

6
	

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