Problem 89 のバックアップ(No.1)

• バックアップ一覧
• 差分 を表示
• 現在との差分 を表示
• ソース を表示
• Problem 89 へ行く。
  • 1 (2011-11-12 (土) 05:31:52)

Problem 89 「ローマ数字」 †

ローマ数字の記法は一つの数について沢山ある場合が存在する (FAQを見よ). しかし, ある数については最良の記法が必ず存在する.

例えば, 16の正しい記法を全て並べてみる.

IIIIIIIIIIIIIIII
VIIIIIIIIIII
VVIIIIII
XIIIIII
VVVI
XVI

最後の例は, 最小の文字数で表せるという意味で, 最も効率が良い.

11Kのテキストファイル&ref(): File not found: "roman.txt" at page "Problem 89"; は1000個のローマ記法で書かれた数を含んでいる. これらは, 正しい記法に従っている. 即ち, 大きい数から順に書かれていて, 引き算ペアのルールにも従っている(このルールについてはFAQを見よ) 但し, 最小の文字数で表されているとは限らない.

最小形で書いたときに, 何文字節約できるかを求めよ.

注: ファイル中の全てのローマ数字には, 5つ以上の同じ文字が連続して含まれることはない.

FAQ: ローマ数字のルール †

(訳者:概略のみ与える)

基本法則1 †

全ての文字はサイズの降順に並ぶ

基本法則2 †

引き算ペアについて.

X (10) + IX (9) として19=XIXと表せる. ただし, 8をIIXと二文字以上を引くことは許されない.

1. I, X, Cのみが引き算ペアの最初の文字として許される.
2. IはVまたはXの前に来ることが許される
3. XはLまたはCの前に来ることが許される
4. CはDまたはMの前に来ることが許される