Original Solution

ข้อนี้อาจดูเหมือนจะมีเฉลยที่วุ่นวายมากๆ แต่ถ้าหากเราสามารถแบ่งกรณีได้อย่างเป็นระบบระเบียบก็จะไม่วุ่นวายมาก

สำหรับทุกจำนวนเต็มน้อยกว่าหรือเท่ากับ $d$ เราต้องการหาจำนวน i, v, x, l, c ที่ต้องใช้ สมมุติว่าเรากำลังพิจารณาตัวเลข $n$ อยู่

Pseudocode จะเป็นดังต่อไปนี้

while n >= 0:
    if n >= 100:
        c += 1
        n -= 100
    elif n >= 90:
        c += 1
        x += 1
        n -= 90
    elif n >= 50:
        l += 1
        n -= 50
    elif n >= 40:
        l += 1
        x += 1
        n -= 40
    elif n >= 10:
        x += 1
        n -= 10
    elif n >= 9:
        x += 1
        i += 1
        n -= 9
    elif n >= 5:
        v += 1
        n -= 5
    elif n >= 4:
        v += 1
        i += 1
        n -= 4
    else:
        i += 1
        n -= 1

สังเกตุว่าในแต่ละรอบของ while loop $n$ จะเข้าเพียงหนึ่งกรณีเท่านั้น และอัลกอริทึมจะพิจารณากรณีที่ $n$ มากๆไปหา $n$ น้อยๆเสมอเพื่อรับประกันว่าสัญลักษณ์ที่มีค่ามากกว่าจะอยู่ทางซ้ายเสมอ (โดยมีข้อยกเว้นดังที่ระบุไว้ในตัวโจทย์)

Alternative Solution

จริง ๆ ข้อนี้สามารถมองเหมือนเป็น pattern ได้เหมือนกัน ลองดูแบบนี้ครับ ลำดับของอักษรแทนเลขโรมัน คือ I V X L C ตามลำดับ

พิจารณาเลข 1, 2, 3, ..., 9

1 : I
2 : II
3 : III
4 : IV
5 : V
6 : VI
7 : VII
8 : VIII
9 : IX

พิจารณา 10, 20, 30, ..., 90

10 : X
20 : XX
30 : XXX
40 : XL
50 : L
60 : LX
70 : LXX
80 : LXXX
90 : XC

พิจารณา 100, 200, 300

100 : C 
200 : CC
300 : CCC

จะสังเกตได้ว่าเลขแบ่งเป็นชุดตัวอักษร ชุดละ 3 ตัว เรียกจากมากไปน้อยจะเป็น I V X ของ 1 - 9, X L C ของ 10 - 90, และ 100 - 300 ทั้งหมดเป็นไปตามกฎการเพิ่มแบบเดียวกัน ทั้งนี้เพื่อให้เหมือนกับ 2 ชุดก่อนหน้า เราสามารถสมมุติให้มีตัวอักษรอีก 2 ตัวเพิ่มขึ้นมาข้างหลังได้ C _ _

นอกจากนี้ ตัวเลขโรมันในแต่ละหลักจะต่อกันไปเรื่อยเลย เช่น 318 ก็คือ 300 (CCC) + 10 (X) + 8 (VIII) = CCCXVIII ดังนั้น เราสามารถหาว่าแต่ละหลักเป็นเลขอะไร แล้วค่อย ๆ ไล่นับจำนวนตัวอักษร โดยเราจะสร้าง array มาเก็บจำนวนของแต่ละตัวอักษร เรียงจากน้อยไปมาก และบวกเพิ่มโดยใช้ array อีกตัวที่เก็บว่าเลขในหลักนั้น ๆ มีตัวอักษรตาม pattern ที่กล่าวไปข้างต้นอย่างไร

#include <bits/stdc++.h>

using namespace std;

int factor[][3] = {
	{0, 0, 0}, 
	{1, 0, 0}, 
	{2, 0, 0},
	{3, 0, 0}, 
	{1, 1, 0}, 
	{0, 1, 0},
	{1, 1, 0},
	{2, 1, 0}, /// เช่น XII ถ้าเป็นหลักหน่วย และ LXX ถ้าเป็นหลักสิบ
	{3, 1, 0},
	{1, 0, 1}
};

int cnt[7]; /// [I, V, X, L, C, _, _]

/// เพิ่มค่าใน cnt โดย start_pos จะขึ้นอยู่กับว่าเป็นเลขในหลักใด
///     หลักหน่วย -- 0 เพื่อให้ไปบวกเพิ่ม ณ ตำแหน่ง [I, V, X]
///     หลักสิบ   -- 2 เพื่อให้ไปบวกเพิ่ม ณ ตำแหน่ง [X, L, C]
///     หลักร้อย  -- 4 เพื่อให้ไปบวกเพิ่ม ณ ตำแหน่ง [C, _, _]

void add(int start_pos, int num) {
	for(int i = 0; i < 3; i++) {
		cnt[start_pos + i] += factor[num][i];
	}
}

int main() {
	int d;
	cin >> d;

	for(int i = 1; i <= d; i++) {
		add(0, i % 10); /// หลักหน่วย
		add(2, (i / 10) % 10); /// หลักสิบ
		add(4, i / 100); /// หลักร้อย
	}

	for (int i = 0; i < 5; i++) {
		cout << cnt[i] << " ";
	}
	
	return 0;
}