Olimpiadi Italiane di Informatica – Fase territoriale 2001
È venerdì, e il cassiere Camillo ha davanti a sé una lunga fila di clienti della sua banca venuti a ritirare contante per il weekend.
Per fare presto, Camillo decide di usare per ogni cliente il numero minimo possibile di banconote.
Sapreste scrivere un programma per evitargli il mal di testa, considerato che ha a disposizione banconote da 100.000, 10.000, 5.000, 2.000 e 1.000 in quantità illimitata e che l’entità di ogni prelievo è un multiplo di 1.000 lire?
Dati in input
L’input del programma è costituito da un numero.
Dati in output
Il programma deve scrivere il numero di banconote necessario per ognuno dei tagli disponibili.
Più precisamente, deve scrivere cinque numeri che corrispondono (in ordine, dalla prima all’ultima) alle banconote da
- 100 000
- 10 000
- 5 000
- 2 000
- 1 000.
Assunzioni
- L’entità del prelievo è in ogni caso inferiore a 1 miliardo di lire.
Esempi
| Input | Output | |
|---|---|---|
| 1° | 10 000 | 0 1 0 0 0 |
| 2° | 152 000 | 1 5 0 1 0 |
| 3° | 2 001 000 | 20 0 0 0 1 |
Soluzione 1
Per ogni taglio disponibile si calcola il numero di banconote necessarie (quoziente) e la cifra rimasta da cambiare (resto)
N = 152000
TAGLI = [100000, 10000, 5000, 2000, 1000]
NTAGLI = len(TAGLI)
PEZZI = [0,0,0,0,0]
for taglio in range(NTAGLI):
PEZZI[taglio] = N // TAGLI[taglio]
N = N % TAGLI[taglio]
for taglio in range(NTAGLI):
print(TAGLI[taglio], PEZZI[taglio])
Soluzione 2
Codice più corto
N = 152000
TAGLI = [100000, 10000, 5000, 2000, 1000]
for taglio in TAGLI:
print(taglio, N//taglio)
N = N%taglio
Soluzione 3
La lista dei tagli disponibili può essere aggiornata a quelli dell’euro… ed estesa alle monete
...
TAGLI = [500, 200, 100, 50, 20, 10, 5, 2, 1, .50, .20, .10, .05, .02, .01]
...
Versione OII
f = open("input.txt", "r")
linea = f.read()
f.close()
N = int(linea)
TAGLI = [100000, 10000, 5000, 2000, 1000]
PEZZI = ["", "", "", "", ""]
for taglio in TAGLI:
BANCONOTE[i] = str(N//taglio)+'\n'
N = N%taglio
f = open("output.txt", "w")
f.writelines(BANCONOTE)
f.close()