Lino il giornalaio

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 200
5
6
6
5 10 20 50 100 200
0

// Contributo di: Mirko Da Corte
#include 

int  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;
}