344 - Roman Digititis

Time limit: 3.000 seconds

Roman Digititis

Many persons are familiar with the Roman numerals for relatively small numbers. The symbols ``i", ``v", ``x", ``l", and ``c" represent the decimal values 1, 5, 10, 50, and 100 respectively. To represent other values, these symbols, and multiples where necessary, are concatenated, with the smaller-valued symbols written further to the right. For example, the number 3 is represented as ``iii", and the value 73 is represented as ``lxxiii". The exceptions to this rule occur for numbers having units values of 4 or 9, and for tens values of 40 or 90. For these cases, the Roman numeral representations are ``iv" (4), ``ix" (9), ``xl" (40), and ``xc" (90). So the Roman numeral representations for 24, 39, 44, 49, and 94 are ``xxiv", ``xxxix", ``xliv", ``xlix", and ``xciv", respectively.

The preface of many books has pages numbered with Roman numerals, starting with ``i" for the first page of the preface, and continuing in sequence. Assume books with pages having 100 or fewer pages of preface. How many ``i", ``v", ``x", ``l", and ``c" characters are required to number the pages in the preface? For example, in a five page preface we歓l use the Roman numerals ``i", ``ii", ``iii", ``iv", and ``v", meaning we need 7 ``i" characters and 2 ``v" characters.

Input

The input will consist of a sequence of integers in the range 1 to 100, terminated by a zero. For each such integer, except the final zero, determine the number of different types of characters needed to number the prefix pages with Roman numerals.

Output

For each integer in the input, write one line containing the input integer and the number of characters of each type required. The examples shown below illustrate an acceptable format.

Sample Input

1
2
20
99
0

Sample Output

1: 1 i, 0 v, 0 x, 0 l, 0 c
2: 3 i, 0 v, 0 x, 0 l, 0 c
20: 28 i, 10 v, 14 x, 0 l, 0 c
99: 140 i, 50 v, 150 x, 50 l, 10 c

================================================

#include <stdio.h>
#include <stdlib.h>

/* function prototype */
void digit_change(int,int [5]);

int main()
{
　freopen("Input.txt","r",stdin);
　freopen("Output.txt","w",stdout);
　int num,i,count[5];
　while(scanf("%d",&num)==1)
　　if(num!=0)
　　{
　　　/* reset the number counting array */
　　　for(i=0;i<5;i++)
　　　　count[i]=0;
　　　for(i=1;i<=num;i++)
　　　　digit_change(i,count);
　　　printf("%d: %d i, %d v, %d x",num,count[0],count[1],count[2]);
　　　printf(", %d l, %d c\n",count[3],count[4]);
　　}
　return 0;
}

/* return every elements of Roman digit from 1 to num */
void digit_change(int num,int count[5])
{
　/* handle the exception "100" */
　if(num==100)
　{
　　count[4]++;
　　return;
　}
　/* the representations of units and tens are the same, */
　/* just differenct at count[] index shift */
　int i,n,k,times=1;
　if(num>9)
　　times=2;
　for(i=0,k=0,n=num%10;i<times;i++,k+=2,n=num/10)
　　if(n!=0)
　　　/* separate one digit to three phases */
　　　if(n>0&&n<4)
　　　　count[0+k]+=n;
　　　else if(n>3&&n<9)
　　　{
　　　　count[1+k]++;
　　　　count[0+k]+=abs(n-5);
　　　}
　　　else
　　　{
　　　　count[0+k]++;
　　　　count[2+k]++;
　　　}
}