Informatica Online Judge

  Prefance Numbering (서문에 페이지 달기) [0275 / 0113]

Time Limit(Test case) : 1000 (ms)
Number of users who solved : 32   Total Tried : 37


The Champion of this Problem (C++) : tlsdydaud1 - 0ms / 383byte
My Best Submission (C++) : N/A

[]

Background

일반적으로 책들의 서문의 페이지는 로마수로 표시하는 경우가 많다.

전통적인 로마수는 하나의 문자로 숫자값을 표현한다. 다음은 그 수와 문자를 나타낸다.

I 1 L 50 M 1000
V 5 C 100
X 10 D 500

이 숫자는 다음과 같은 규칙들이 있다.

[규칙1]
로마숫자 중 10^n형태로 표현되는 마크는 최대 3개를 연속해서 사용하여 새로운 숫자를 만들 수 있다.

- III : 3
- CCC : 300

[규칙2]
로마수는 5*10^n의 형태는 숫자를 연결하여 만들지 않는다.

[규칙3]
일반적으로 숫자들은 서로 연결하여(내림차순으로) 쓴다. ([규칙4]는 제외)

- CCLXVIII : 100+100+50+10+5+1+1+1 = 268

[규칙4]
I과 V, V과 X와 같이 한 단계 더 높은 숫자들 간에는 더 작은 기호가 한 단계 큰 기호 앞에 붙어서 다음과 같은 숫자를 표현한다.

- IV : 4
- IX : 9
- XL : 40

[규칙5]
[규칙4]에서 만들어진 복합 기호는 [규칙3]의 원리에 하나의 기호처럼 적용된다. 그리고 [규칙4]는 중복으로 적용되지는 않는다.

- IXL : 39 (X)
- XXXIX : 39 (O)

[예외규칙]
복합기호로 XL보다 큰 XD, IC, XM은 허용되지 않는다. 예를 들어 490은 XD로 표현하지 않고 CDXC로 표현하며, 99는 IC로 표현하지 않고 XCIX로 표현하며, 990은 XM이 아니라 CMXC로 표현한다.

3500이하의 자연수 N이 주어질 때, 서장은 1페이지부터 N페이지까지로 구성된다는 의미이다. 이 서장의 모든 페이지를 로마수로 표현한다면 이 때 사용되는 각 기호 I, V, X, ... 는 몇 번씩 사용되는 지를 구하는 프로그램을 작성하시오.

Input

하나의 정수 N이 입력된다.

Output

I, V, .. 등 중 1회 이상 사용되는 기호들에 대해서 오름 차순으로 한 줄에 하나씩 출력한다.
각 줄은 기호와 횟수를 공백으로 구분하여 출력한다.

IO Example

입력
5

출력
I 7
V 2

* 설명 : 1~5페이지를 로마수로 나타내면 I, II, III, IV, V이므로 I가 6번 V가 2번 사용된다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]