Una grande tavola pitagorica

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()