USACO 2.2.1 Preface Numbering_散装海盗船
A certain book's prefaces are numbered in upper case Roman numerals. Traditional Roman numeral values use a single letter to represent a certain subset of decimal numbers. Here is the standard set:
I 1 L 50 M 1000
V 5 C 100
X 10 D 500
As many as three of the same marks that represent 10n may be placed consecutively to form other numbers:
III is 3
CCC is 300
Marks that have the value 5x10n are never used consecutively.
Generally (with the exception of the next rule), marks are connected together and written in descending order to form even more numbers:
CCLXVIII = 100+100+50+10+5+1+1+1 = 268
Sometimes, a mark that represents 10^n is placed before a mark of one of the two next higher values (I before V or X; X before L or C; etc.). In this case, the value of the smaller mark is SUBTRACTED from the mark it precedes:
IV = 4
IX = 9
XL = 40
This compound mark forms a unit and may not be combined to make another compound mark (e.g., IXL is wrong for 39; XXXIX is correct).
Compound marks like XD, IC, and XM are not legal, since the smaller mark is too much smaller than the larger one. For XD (wrong for 490), one would use CDXC; for IC (wrong for 99), one would use XCIX; for XM (wrong for 990), one would use CMXC. 90 is expressed XC and not LXL, since L followed by X connotes that successive marks are X or smaller (probably, anyway).
Given N (1 <= N < 3,500), the number of pages in the preface of a book, calculate and print the number of I's, V's, etc. (in order from lowest to highest) required to typeset all the page numbers (in Roman numerals) from 1 through N. Do not print letters that do not appear in the page numbers specified.
If N = 5, then the page numbers are: I, II, III, IV, V. The total number of I's is 7 and the total number of V's is 2.
PROGRAM NAME: preface
INPUT FORMAT
A single line containing the integer N.
SAMPLE INPUT (file preface.in)
5
OUTPUT FORMAT
The output lines specify, in ascending order of Roman numeral letters, the letter, a single space, and the number of times that letter appears on preface page numbers. Stop printing letter totals after printing the highest value letter used to form preface numbers in the specified set.
SAMPLE OUTPUT (file preface.out)
I 7
V 2
Preface Numbering
序言页码
译 by Jeru
一类书的序言是以罗马数字标页码的。传统罗马数字用单个字母表示特定的数值，一下是标准数字表:
I 1 L 50 M 1000
V 5 C 100
X 10 D 500
最多3个可以表示为10n的数字(I,X,C,M)可以连续放在一起，表示它们的和:
III=3
CCC=300
可表示为5x10n的字符(V,L,D)从不连续出现。
除了下一个规则，一般来说，字符以递减的顺序接连出现:
CCLXVIII = 100+100+50+10+5+1+1+1 = 268
有时，一个可表示为10^n的数出现在一个比它大的数前(I在V或X前面，X在L或C前面，等等)。在这种情况下，数值等于后面的那个数减去前面的那个数:
IV = 4
IX = 9
XL = 40
像XD, IC, 和XM这样的表达是非法的，因为前面的数比后面的数小太多。对于XD(490的错误表达)，可以写成 CDXC; 对于IC(99的错误表达)，可以写成XCIX; 对于XM(990的错误表达)，可以写成CMXC。
给定N(1 <= N < 3,500)， 序言的页码数，请统计在第1页到第N也中，有几个I出现，几个V出现，等等 (从小到大的顺序)。不要输出并没有出现过的字符。
比如N = 5, 那么页码数为: I, II, III, IV, V. 总共有7个I出现，2个V出现。
PROGRAM NAME: preface
INPUT FORMAT
一个整数N。
SAMPLE INPUT(preface.in)
5
OUTPUT FORMAT
每行一个字符和一个数字k，表示这个字符出现了k次。字符必须按数字表中的递增顺序输出。
SAMPLE OUTPUT(preface.out)
I 7
V 2
此题关键在于对罗马数字规律的掌握；
【计数方法】
(1)相同的数字连写，所表示的数等于这些数字相加得到的数，如： Ⅲ = 3；
(2)小的数字在大的数字的右边，所表示的数等于这些数字相加得到的数， 如：Ⅷ = 8；Ⅻ = 12；
(3)小的数字，(限于Ⅰ、X 和 C)在大的数字的左边，所表示的数等于大数减小数得到的数，如：Ⅳ = 4；Ⅸ = 9；
(4)在一个数的上面画一条横线，表示这个数增值 1 000 倍，如：Ⅻ = 12 000 。
【组数规则】
有几条须注意掌握；
(1)基本数字Ⅰ、X 、C 中的任何一个，自身连用构成数目，或者放在大数的右边连用构成数目，都不能超过三个；放在大数的左边只能用一个。
(2)不能把基本数字 V 、L 、D 中的任何一个作为小数放在大数的左边采用相减的方法构成数目；放在大数的右边采用相加的方式构成数目，只能使用一个。
(3)V 和 X 左边的小数字只能用Ⅰ。
(4)L 和 C 左边的小数字只能用×。
(5)D 和 M 左 边的小数字只能用 C 。
【举例】
・个位数举例
I, 1 II, 2 III, 3 IV, 4 V, 5 VI, 6 VII, 7 VIII,8 IX, 9
・十位数举例
X, 10 XI, 11 XII, 12 XIII, 13 XIV, 14 XV, 15 XVI, 16 XVII, 17 XVIII, 18 XIX, 19 XX, 20 XXI, 21 XXII, 22 XXIX, 29 XXX, 30 XXXIV, 34 XXXV, 35 XXXIX, 39 XL, 40 L, 50 LI, 51 LV, 55 LX, 60 LXV, 65 LXXX, 80 XC, 90 XCIII, 93 XCV, 95 XCVIII, 98 XCIX, 99
・百位数举例
C, 100 CC, 200 CCC, 300 CD, 400 D, 500 DC,600 DCC, 700 DCCC, 800 CM, 900 CMXCIX,999
・千位数举例
M, 1000 MC, 1100 MCD, 1400 MD, 1500 MDC, 1600 MDCLXVI, 1666 MDCCCLXXXVIII, 1888 MDCCCXCIX, 1899 MCM, 1900 MCMLXXVI, 1976 MCMLXXXIV, 1984 MCMXC, 1990 MM, 2000 MMMCMXCIX, 3999
・千位数以上举例
-----
CLXXX DCL, 183650
====== -----
CXXXIV CMXLV DLXXXIV, 134945584
方法：
1.整千，整百，整十处理。（有顺序）
2.6，7，8，9减5后与1，2，3，4相同。60，70， 600，700…同理。
3.注意不输出未出现的，按I,V,X,L,C,D,M 顺序输出，并非字母表。
4.细心！！！敢想，别怕麻烦。
Read full article from USACO 2.2.1 Preface Numbering_散装海盗船
A certain book's prefaces are numbered in upper case Roman numerals. Traditional Roman numeral values use a single letter to represent a certain subset of decimal numbers. Here is the standard set:
I 1 L 50 M 1000
V 5 C 100
X 10 D 500
As many as three of the same marks that represent 10n may be placed consecutively to form other numbers:
III is 3
CCC is 300
Marks that have the value 5x10n are never used consecutively.
Generally (with the exception of the next rule), marks are connected together and written in descending order to form even more numbers:
CCLXVIII = 100+100+50+10+5+1+1+1 = 268
Sometimes, a mark that represents 10^n is placed before a mark of one of the two next higher values (I before V or X; X before L or C; etc.). In this case, the value of the smaller mark is SUBTRACTED from the mark it precedes:
IV = 4
IX = 9
XL = 40
This compound mark forms a unit and may not be combined to make another compound mark (e.g., IXL is wrong for 39; XXXIX is correct).
Compound marks like XD, IC, and XM are not legal, since the smaller mark is too much smaller than the larger one. For XD (wrong for 490), one would use CDXC; for IC (wrong for 99), one would use XCIX; for XM (wrong for 990), one would use CMXC. 90 is expressed XC and not LXL, since L followed by X connotes that successive marks are X or smaller (probably, anyway).
Given N (1 <= N < 3,500), the number of pages in the preface of a book, calculate and print the number of I's, V's, etc. (in order from lowest to highest) required to typeset all the page numbers (in Roman numerals) from 1 through N. Do not print letters that do not appear in the page numbers specified.
If N = 5, then the page numbers are: I, II, III, IV, V. The total number of I's is 7 and the total number of V's is 2.
PROGRAM NAME: preface
INPUT FORMAT
A single line containing the integer N.
SAMPLE INPUT (file preface.in)
5
OUTPUT FORMAT
The output lines specify, in ascending order of Roman numeral letters, the letter, a single space, and the number of times that letter appears on preface page numbers. Stop printing letter totals after printing the highest value letter used to form preface numbers in the specified set.
SAMPLE OUTPUT (file preface.out)
I 7
V 2
Preface Numbering
序言页码
译 by Jeru
一类书的序言是以罗马数字标页码的。传统罗马数字用单个字母表示特定的数值，一下是标准数字表:
I 1 L 50 M 1000
V 5 C 100
X 10 D 500
最多3个可以表示为10n的数字(I,X,C,M)可以连续放在一起，表示它们的和:
III=3
CCC=300
可表示为5x10n的字符(V,L,D)从不连续出现。
除了下一个规则，一般来说，字符以递减的顺序接连出现:
CCLXVIII = 100+100+50+10+5+1+1+1 = 268
有时，一个可表示为10^n的数出现在一个比它大的数前(I在V或X前面，X在L或C前面，等等)。在这种情况下，数值等于后面的那个数减去前面的那个数:
IV = 4
IX = 9
XL = 40
像XD, IC, 和XM这样的表达是非法的，因为前面的数比后面的数小太多。对于XD(490的错误表达)，可以写成 CDXC; 对于IC(99的错误表达)，可以写成XCIX; 对于XM(990的错误表达)，可以写成CMXC。
给定N(1 <= N < 3,500)， 序言的页码数，请统计在第1页到第N也中，有几个I出现，几个V出现，等等 (从小到大的顺序)。不要输出并没有出现过的字符。
比如N = 5, 那么页码数为: I, II, III, IV, V. 总共有7个I出现，2个V出现。
PROGRAM NAME: preface
INPUT FORMAT
一个整数N。
SAMPLE INPUT(preface.in)
5
OUTPUT FORMAT
每行一个字符和一个数字k，表示这个字符出现了k次。字符必须按数字表中的递增顺序输出。
SAMPLE OUTPUT(preface.out)
I 7
V 2
此题关键在于对罗马数字规律的掌握；
【计数方法】
(1)相同的数字连写，所表示的数等于这些数字相加得到的数，如： Ⅲ = 3；
(2)小的数字在大的数字的右边，所表示的数等于这些数字相加得到的数， 如：Ⅷ = 8；Ⅻ = 12；
(3)小的数字，(限于Ⅰ、X 和 C)在大的数字的左边，所表示的数等于大数减小数得到的数，如：Ⅳ = 4；Ⅸ = 9；
(4)在一个数的上面画一条横线，表示这个数增值 1 000 倍，如：Ⅻ = 12 000 。
【组数规则】
有几条须注意掌握；
(1)基本数字Ⅰ、X 、C 中的任何一个，自身连用构成数目，或者放在大数的右边连用构成数目，都不能超过三个；放在大数的左边只能用一个。
(2)不能把基本数字 V 、L 、D 中的任何一个作为小数放在大数的左边采用相减的方法构成数目；放在大数的右边采用相加的方式构成数目，只能使用一个。
(3)V 和 X 左边的小数字只能用Ⅰ。
(4)L 和 C 左边的小数字只能用×。
(5)D 和 M 左 边的小数字只能用 C 。
【举例】
・个位数举例
I, 1 II, 2 III, 3 IV, 4 V, 5 VI, 6 VII, 7 VIII,8 IX, 9
・十位数举例
X, 10 XI, 11 XII, 12 XIII, 13 XIV, 14 XV, 15 XVI, 16 XVII, 17 XVIII, 18 XIX, 19 XX, 20 XXI, 21 XXII, 22 XXIX, 29 XXX, 30 XXXIV, 34 XXXV, 35 XXXIX, 39 XL, 40 L, 50 LI, 51 LV, 55 LX, 60 LXV, 65 LXXX, 80 XC, 90 XCIII, 93 XCV, 95 XCVIII, 98 XCIX, 99
・百位数举例
C, 100 CC, 200 CCC, 300 CD, 400 D, 500 DC,600 DCC, 700 DCCC, 800 CM, 900 CMXCIX,999
・千位数举例
M, 1000 MC, 1100 MCD, 1400 MD, 1500 MDC, 1600 MDCLXVI, 1666 MDCCCLXXXVIII, 1888 MDCCCXCIX, 1899 MCM, 1900 MCMLXXVI, 1976 MCMLXXXIV, 1984 MCMXC, 1990 MM, 2000 MMMCMXCIX, 3999
・千位数以上举例
-----
CLXXX DCL, 183650
====== -----
CXXXIV CMXLV DLXXXIV, 134945584
方法：
1.整千，整百，整十处理。（有顺序）
2.6，7，8，9减5后与1，2，3，4相同。60，70， 600，700…同理。
3.注意不输出未出现的，按I,V,X,L,C,D,M 顺序输出，并非字母表。
4.细心！！！敢想，别怕麻烦。
Read full article from USACO 2.2.1 Preface Numbering_散装海盗船
