Borse di studio

di

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 sotto forma 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: 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

  • 1 ≤ N ≤ 50
  • La scuola ha più di 100 studenti;
input.txt output.txt
6 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		 
/*
    www.valcon.it    
    OOI 2002 - Fase nazionale - BORSE DI STUDIO
*/  

#include
#include
using namespace std;

#define NMAX 50

ifstream fin;
ofstream fout;
         
int  N,                         // plusvalenza in migliaia di euro
     ripartizione[NMAX];        // una soluzione

void assegna(int daAssegnare, int massimo, int attuale)
{
	if(daAssegnare == 0)
    {
        for(int i=0; i < attuale; i++)
            fout << ripartizione[i] << ' ';
	    fout << endl;
	}
    else
    {
        for(int quota=1; quota <= min(daAssegnare,massimo); quota++)
        {
			ripartizione[attuale]=quota;
			assegna(daAssegnare-quota, quota, attuale+1);
		}
    }
}

int main()
{
	fin.open("input.txt");
	fout.open("output.txt");
	
	fin >> N;  
	assegna(N,N,0); 
	return 0;
}