Olimpiadi Italiane di Informatica – Correttore online – Facili
Gianni ama la matematica.
Qualche tempo fa, ha deciso che la vecchia tavola pitagorica di dimensione 10×10 era troppo restrittiva.
Ha quindi deciso di costruire una tabella di moltiplicazioni di dimensione generica n×m.
La tabella ha n righe, numerate da 1 a n, e m colonne, numerate da 1 a m.
La casella che si trova all’intersezione fra la riga i (1 ≤ i ≤ n) e la colonna j (1 ≤ j ≤ m), contiene il prodotto tra il numero i e il numero j.
Prima di costruirla, Gianni vuole conoscere le frequenze delle cifre decimali (0, 1, …, 9): si chiede quante volte ciascuna cifra decimale comparirà nella tabella.
Per esempio, se una casella contiene il numero 121, la cifra 1 comparirà due volte e la cifra 2 una volta.
Tale conteggio va esteso a tutte le caselle della tabella, effettuando delle somme cumulative per ogni cifra decimale e ottenendo così le frequenze.
Per esempio, con n=3 e m=4, abbiamo che la tabella contiene, in ordine di riga: 1, 2, 3, 4, 2, 4 , 6, 8, 3, 6, 9, 12.
Quindi, le cifre 1, 3, 4 e 6 compaiono due volte ciascuna, la cifra 2 tre volte, le cifre 8 e 9 una volta ciascuna e tutte le altre cifre compaiono zero volte.
Gianni quindi scrive tali frequenze in ordine crescente di cifra: 0, 2, 3, 2, 2, 0, 2, 0, 1, 1.
Scrivere un programma che, ricevuti i due interi n e m, scrive le frequenze delle cifre decimali (in ordine crescente di cifra) che compaiono nella tabella di dimensione nxm.
Esempio di input/output
+-----------+------------+
| input.txt | output.txt |
+-----------+------------+
| 10 10 | 28 |
| | 24 |
| | 27 |
| | 15 |
| | 17 |
| | 8 |
| | 15 |
| | 6 |
+-----------+------------+
Osserva
- numero: elemento alla posizione i, j della tabella
- quoziente: cifre più significative di x
- resto: cifra meno significativa di x
- CONTI[i], contatore della cifra i
N = 10
M = 10
CONTI = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
for i in range(1, N+1):
for j in range(1, M+1):
numero = i*j
while(numero > 0):
quoziente = numero//10
resto = numero%10
CONTI[resto] += 1
numero = quoziente
for cifra in range(10):
print("%d: %2d" %(cifra, CONTI[cifra]))
0: 28
1: 24
2: 27
3: 15
4: 23
5: 15
6: 17
7: 8
8: 15
9: 6
Versione OII
f = open("input.txt", "r")
linea = f.read()
f.close()
dati = linea.split()
N = int(dati[0])
M = int(dati[1])
CONTI = 10*[0]
for i in range(1, N+1):
for j in range(1, M+1):
numero = i*j
while(numero > 0):
quoziente = numero//10
resto = numero%10
CONTI[resto] += 1
numero = quoziente
strCONTI = 10*[""]
for cifra in range(10):
strCONTI[cifra] = str(CONTI[cifra])+"\n"
f = open("output.txt", "w")
f.writelines(strCONTI)
f.close()