Olimpiadi di Informatica - Selezione Regionale 2007
problema
Lino il giornalaio (LINO)
- livello difficoltà 2
soluzione in C++ proposta da Riccardo Rigon
/* Selezione regionale 2007 - Lino il giornalaio (LINO) - Difficoltà D = 2 Il giornalaio Lino è un appassionato di matematica e, prima di consegnare il resto ai propri clienti, si diverte a calcolare mentalmente quante diverse 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| | input.txt |output.txt| +-----------+----------+ +-----------+----------+ | 8 | 5 | | 6 | 0 | | 6 | | | 6 | | | 1 | | | 5 | | | 2 | | | 10 | | | 5 | | | 20 | | | 10 | | | 50 | | | 20 | | | 100 | | | 50 | | | 200 | | | 100 | | +-----------+----------+ | 200 | | +-----------+----------+ Note: un programma che restituisce sempre lo stesso valore indipendentemente dai dati in 'input.txt' non totalizza alcun punteggio rilevante ------------------------------------------------------------------------------*/ // Selezione Regionale 2007 - Lino - programma sviluppato da Riccardo Rigon #include
using namespace std; int monete[100]; int n; int conta(int soldi,int posizione){ int numero=0; int temp; for(int i=posizione;i
0) numero+=conta(temp,i); } return numero; } int main(){ ifstream input("input.txt"); int resto; int combinazioni=0; input>>n; input>>resto; for(int i=0;i
>a; if(a>resto){ i--; n--; } else monete[i]=a; } input.close(); combinazioni=conta(resto,0); ofstream output("output.txt"); output<
Testo del problema