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

• バックアップ一覧
• 差分 を表示
• 現在との差分 を表示
• ソース を表示
• Problem 315 へ行く。
  • 1 (2010-12-20 (月) 00:06:44)

Problem 315 「デジタルルート時計」 †

Sam と Max は, ２個のデジタル時計を「デジタルルート（数字根）時計」に作り変えるよう依頼されている.
デジタルルート時計は, 数字根をステップごとに計算するデジタル時計である.

時計に数字が与えられると, 時計は数字を表示し計算を開始する. 結果にたどりつくまでの途中の値がすべて表示される.
例えば, 時計に 137 という数が与えられると, "137"→"11"→"2" と表示してから真っ黒になり, 次の数を待つ.

各デジタル数字はセグメント状のライトから構成される：横セグメントが３本（上, 中, 下）と縦セグメントが４本（左上, 右上, 左下, 右下）である.
数 "1" は右上と右下の縦セグメントでできており, 数 "4" は中の横セグメントと, 左上, 右上, 右下の縦セグメントからできている. 数 "8" はすべてのセグメントが点灯する.

時計はセグメントを点灯/消灯させるときに限りエネルギーを消費する.
"2" を点灯させるには 5 回の遷移を要する. "7" は 4 回だけ遷移を要する.

Sam と Max は２個の異なる時計を作る.

Sam の時計は 137 のような数を与えられると, "137" を表示し, パネルを消灯してから次の数（"11"）を点灯し, 再び消灯してそして最終的に最後の数（"2"）を点灯, しばらくして消灯する.
たとえば, 137 では, Sam の時計は次のように動く.

• "137"：(2 + 5 + 4) × 2 = 22 回の遷移（"137" の点灯/消灯）
• "11" ：(2 + 2) × 2 = 8 回の遷移（"11" の点灯/消灯）
• "2"　　：(5) × 2 = 10 回の遷移（"2" の点灯/消灯）

合計で 40 回の遷移である.

Max の時計は異なる動きをする. パネル全体を消灯するのではなく, 次の数に必要のないセグメントのみを消灯するという賢いやり方である.
数 137 に対して, Max の時計は次のように動く.

• "137"：2 + 5 + 4 = 11 回の遷移（"137" の点灯）
  　　　　　7 回の遷移（数 "11" に必要ないセグメントの消灯）
• "11" ：0 回の遷移（数 "11" はすでに正しく点灯済み）
  　　　　　3 回の遷移（始めの "1" と２つ目の "1" の下部分を消灯；
  　　　　　上部分は数 "2" と共通である）
• "2"　　：4 回の遷移（"2" にするため残りのセグメントを点灯）
  　　　　　5 回の遷移（"2" を消灯）

合計で 30 回の遷移である.

もちろん, Max の時計のほうが Sam より電力の消費が少ない.
２つの時計に A = 10&sup{7}; から B = 2×10&sup{7}; の間の素数が与えられる.
Sam の時計で必要な遷移の総数と Max の時計で必要な遷移の総数の差を求めよ.