Il giornalaio Lino è un appassionato di matematica e, prima di consegnare il resto ai propri clienti, si diverte a calcolare mentalmente quante differenti possibilità esistono per consegnare tale resto.
Ad esempio, considerando l’Euro come valuta, per consegnare 6 centesimi di resto esistono le seguenti 5 possibilità:
- 6 monete da un centesimo,
- 4 monete da un centesimo e 1 da due centesimi,
- 2 monete da un centesimo e 2 da due centesimi,
- 1 moneta da un centesimo e 1 da cinque centesimi,
- 3 monete da due centesimi.
Lino si sta però accorgendo che a causa della lentezza nella consegna del resto sta perdendo molti clienti.
Pertanto, aiuta Lino a calcolare il numero di possibili combinazioni.Dati di input
Il file input.txt contiene nella prima riga un intero positivo N che rappresenta il numero di monete diverse disponibili.
La seconda riga contiene un intero positivo R che rappresenta il resto da consegnare al cliente.
Ciascuna delle successive N righe contiene un intero positivo che indica il valore di ogni singolo tipo di moneta.Dati di output
Il file output.txt è composto da una riga contenente un solo intero, che rappresenta il numero di tutte le possibili combinazioni di monete per la consegna del resto R (notare che possono essere usate più copie dello stesso tipo di moneta, per esempio 6 monete da cinque centesimi).
Assunzioni
- 1 < N < 100
- 1 < R < 1000
- I valori dei vari tipi di N monete sono tutti diversi.
Esempi di input/output
input.txt output.txt 8
6
1 2 5 10 20 50 100 2005 6
6
5 10 20 50 100 2000
// Contributo di: Mirko Da Corte #includeint N; int R; int valore[100]; int risposta=0; void analisi(int resto, int taglio) { if(resto == 0) risposta++; else for(int i=taglio; i >= 0; i--) if(resto >= valore[i]) analisi(resto-valore[i], i); } int main() { FILE *fileIN = fopen("input.txt", "r"); fscanf(fileIN, "%d", &N); fscanf(fileIN, "%d", &R); for(int i=0; i < N; i++) fscanf(fileIN, "%d", &(valore[i])); fclose(fileIN); analisi(R, N-1); FILE *fileOUT = fopen("output.txt", "w"); fprintf(fileOUT, "%d", risposta); fclose(fileOUT); return 0; }