Una grande tavola pitagorica

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.

Dati di input

Il file input.txt è composto da un’unica riga contenente i due numeri interi n e m (1 ≤ n, m ≤ 1000) separati da uno spazio.

Dati di output

Il file output.txt è composto da dieci righe.
La c-esima riga contiene la frequenza della cifra c-1 (1 ≤ c ≤ 10): la prima riga deve contenere il numero di 0 presenti nella tabella delle moltiplicazioni, la seconda il numeri di 1, e così via.

Esempi di input/output

input.txt	output.txt
10 10	28 24 27 15 23 15 17 8 15 6

Autore/i: A.S. Stankevich, ACM ICPC Team St. Petersburg State University of Information technology, Mechanics and Optics.

/*
    www.valcon.it
	OII - Esercizi facili - Una grande tavola pitagorica
*/

#include 
#include 
using namespace std;

int cifre[10];

int main()
{
	ifstream fin ( "input.txt");
	ofstream fout("output.txt");

	int N, M;
	int numero, q, r;
	
	fin >> N >> M;		
	for(int i=1; i <= N; i++)
	for(int j=1; j <= M; j++)
 	{
		numero=i*j;
		while(numero > 0)
		{
		 	q=numero/10;
		 	r=numero%10;

		 	cifre[r]++;
		 	numero=q;
		}
	}	

	for(int i=0; i < 10; i++) 		
 		fout << cifre[i] << endl;	
	return 0;
}