#!ruby
 
=begin
【問】ある数字 n までの数列ローマ数字（I、II、III、…）にしたとき、
　　　最大の長さを持つ文字列を探す関数を書け。
 
例：
n = 5 のとき、{I、II、III、IV、V}、したがって最大は3。
f(5) = 3 
---------------------------------------------------------------------
wikipedia 'ローマ数字' を参照した
通常の表現範囲 1..3999までを考慮
時計の文字盤に使われる IIII は考慮しない
減算則を使わない方法もあるが考慮しない
異表記は考慮しない
Unicode や JISの外字では III 等は一文字になるが考慮しない
同値の解が複数ある場合 ?   いずれか一つ? 最小解を一つ? 最大解を一つ? 同値の解全て?
 
	123 -> [1-123] -> 12[0-3], 1[0-1][0-9], 0[0-9][0-9]     -> 123, 118,  88 -> 88
	345 -> [1-345] -> 34[0-5], 3[0-3][0-9], [0-2][0-9][0-9] -> 343, 338, 288 -> 338, 288
 
	1887, 2887, 3887 解が 7個
=end
 
 
	NumLen = [0,1,2,3,2,1,2,3,4,2]
	$numMax = []
	10.times{|n|
		mx = NumLen[0..n].max
		wrk = []
		0.upto(n){|x|
			wrk << x	if NumLen[x] == mx
		}
		$numMax << wrk
	}
 
def romeLen( str )
	str.chars.map{|x| NumLen[x.to_i] }.inject(:+)
end
 
def f( num )
	unless num >= 1 && num <= 3999
		warn "Illegal numger #{num}."
		exit
	end
 
	candidate = []
	sNum = num.to_s(10)
	sNum.chars.map{|x| x.to_i}.reverse.each_with_index{|n,idx|
		n -= 1	if idx != 0 && n > 0
		$numMax[n].each{|x|
			sNum[-1-idx] = x.to_s
			str = sNum.sub( /^0+/, '' )
			candidate << [ romeLen( str ), str ]
		}
		sNum[-1-idx] = '8'	# [0-9]1桁の最大長
	}
	candidate.uniq!
 
	maxSize = candidate.max_by{|x| x[0]}[0]
	candidate.delete_if{|x| x[0] != maxSize }
	candidate.map{|x| x[1].to_i }.sort
end
 
#####################################################################
 
def tst( num )
	print " #{'%5d' % num} : ", f(num).join(', '), "\n"
end
 
	tst(1)
	tst(2)
	tst(3)
	tst(4)
	tst(5) #=> 3
	tst(6)
	tst(7)
	tst(8)
	tst(9)
	tst(10)
	tst(11)
	tst(12)
	tst(13)
	tst(17)
	tst(27)
	tst(87)
	tst(887)
	tst(1887)
 

IyFydWJ5Cgo9YmVnaW4K44CQ5ZWP44CR44GC44KL5pWw5a2XIG4g44G+44Gn44Gu5pWw5YiX44Ot44O844Oe5pWw5a2X77yISeOAgUlJ44CBSUlJ44CB4oCm77yJ44Gr44GX44Gf44Go44GN44CBCuOAgOOAgOOAgOacgOWkp+OBrumVt+OBleOCkuaMgeOBpOaWh+Wtl+WIl+OCkuaOouOBmemWouaVsOOCkuabuOOBkeOAggoK5L6L77yaCm4gPSA1IOOBruOBqOOBjeOAgXtJ44CBSUnjgIFJSUnjgIFJVuOAgVZ944CB44GX44Gf44GM44Gj44Gm5pyA5aSn44GvM+OAggpmKDUpID0gMyAKLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tCndpa2lwZWRpYSAn44Ot44O844Oe5pWw5a2XJyDjgpLlj4LnhafjgZfjgZ8K6YCa5bi444Gu6KGo54++56+E5ZuyIDEuLjM5OTnjgb7jgafjgpLogIPmha4K5pmC6KiI44Gu5paH5a2X55uk44Gr5L2/44KP44KM44KLIElJSUkg44Gv6ICD5oWu44GX44Gq44GECua4m+eul+WJh+OCkuS9v+OCj+OBquOBhOaWueazleOCguOBguOCi+OBjOiAg+aFruOBl+OBquOBhArnlbDooajoqJjjga/ogIPmha7jgZfjgarjgYQKVW5pY29kZSDjgoQgSklT44Gu5aSW5a2X44Gn44GvIElJSSDnrYnjga/kuIDmloflrZfjgavjgarjgovjgYzogIPmha7jgZfjgarjgYQK5ZCM5YCk44Gu6Kej44GM6KSH5pWw44GC44KL5aC05ZCIID8gICDjgYTjgZrjgozjgYvkuIDjgaQ/IOacgOWwj+ino+OCkuS4gOOBpD8g5pyA5aSn6Kej44KS5LiA44GkPyDlkIzlgKTjga7op6PlhajjgaY/CgoJMTIzIC0+IFsxLTEyM10gLT4gMTJbMC0zXSwgMVswLTFdWzAtOV0sIDBbMC05XVswLTldICAgICAtPiAxMjMsIDExOCwgIDg4IC0+IDg4CgkzNDUgLT4gWzEtMzQ1XSAtPiAzNFswLTVdLCAzWzAtM11bMC05XSwgWzAtMl1bMC05XVswLTldIC0+IDM0MywgMzM4LCAyODggLT4gMzM4LCAyODgKCgkxODg3LCAyODg3LCAzODg3IOino+OBjCA35YCLCj1lbmQKCgoJTnVtTGVuID0gWzAsMSwyLDMsMiwxLDIsMyw0LDJdCgkkbnVtTWF4ID0gW10KCTEwLnRpbWVze3xufAoJCW14ID0gTnVtTGVuWzAuLm5dLm1heAoJCXdyayA9IFtdCgkJMC51cHRvKG4pe3x4fAoJCQl3cmsgPDwgeAlpZiBOdW1MZW5beF0gPT0gbXgKCQl9CgkJJG51bU1heCA8PCB3cmsKCX0KCmRlZiByb21lTGVuKCBzdHIgKQoJc3RyLmNoYXJzLm1hcHt8eHwgTnVtTGVuW3gudG9faV0gfS5pbmplY3QoOispCmVuZAoKZGVmIGYoIG51bSApCgl1bmxlc3MgbnVtID49IDEgJiYgbnVtIDw9IDM5OTkKCQl3YXJuICJJbGxlZ2FsIG51bWdlciAje251bX0uIgoJCWV4aXQKCWVuZAoKCWNhbmRpZGF0ZSA9IFtdCglzTnVtID0gbnVtLnRvX3MoMTApCglzTnVtLmNoYXJzLm1hcHt8eHwgeC50b19pfS5yZXZlcnNlLmVhY2hfd2l0aF9pbmRleHt8bixpZHh8CgkJbiAtPSAxCWlmIGlkeCAhPSAwICYmIG4gPiAwCgkJJG51bU1heFtuXS5lYWNoe3x4fAoJCQlzTnVtWy0xLWlkeF0gPSB4LnRvX3MKCQkJc3RyID0gc051bS5zdWIoIC9eMCsvLCAnJyApCgkJCWNhbmRpZGF0ZSA8PCBbIHJvbWVMZW4oIHN0ciApLCBzdHIgXQoJCX0KCQlzTnVtWy0xLWlkeF0gPSAnOCcJIyBbMC05XTHmoYHjga7mnIDlpKfplbcKCX0KCWNhbmRpZGF0ZS51bmlxIQoKCW1heFNpemUgPSBjYW5kaWRhdGUubWF4X2J5e3x4fCB4WzBdfVswXQoJY2FuZGlkYXRlLmRlbGV0ZV9pZnt8eHwgeFswXSAhPSBtYXhTaXplIH0KCWNhbmRpZGF0ZS5tYXB7fHh8IHhbMV0udG9faSB9LnNvcnQKZW5kCgojIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMKCmRlZiB0c3QoIG51bSApCglwcmludCAiICN7JyU1ZCcgJSBudW19IDogIiwgZihudW0pLmpvaW4oJywgJyksICJcbiIKZW5kCgoJdHN0KDEpCgl0c3QoMikKCXRzdCgzKQoJdHN0KDQpCgl0c3QoNSkgIz0+IDMKCXRzdCg2KQoJdHN0KDcpCgl0c3QoOCkKCXRzdCg5KQoJdHN0KDEwKQoJdHN0KDExKQoJdHN0KDEyKQoJdHN0KDEzKQoJdHN0KDE3KQoJdHN0KDI3KQoJdHN0KDg3KQoJdHN0KDg4NykKCXRzdCgxODg3KQo=