« 『電脳体「キュラゲタム」を討伐せよ』の高度じゃないコード | トップページ | 「ディビジョン・ナイン問題」の高度じゃないコード »

2016年3月11日 (金)

「ロング・ロング・ストリング問題」の高度じゃないコード

「高度じゃないコード」シリーズその9は「ロング・ロング・ストリング問題」です。今月はこれで4つ目となります。

F(n) を、nn(n は自然数)の10進数で表したときの桁数とします。
G(m) を、F(n) = m(m は 2以上の自然数)となる n の値とします。
(ただし、そのような n が存在しないなら、G(m) = -1)
標準入力から、自然数 m(2 ≦ m ≦ 1010)が与えられます。
標準出力に G(m) の値を出力するプログラムを書いてください。

数学の問題をプログラミングで解こう!「ロング・ロング・ストリング」問題解説

1010桁の数字なんてそのままでは扱えませんが、このような桁数やべき乗の問題は常用対数をとればいいですね。
問題に F(n) やら G(m) やら出てきてわかりにくいですが、簡単に書くとこういうことです。
10(m - 1) ≦ nn < 10m
対数をとるとこのようになります。
m - 1 ≦ n * log10(n) < m
m - 1 以上 m 未満ということは、n * log10(n) の小数点以下を切り捨てた値が m - 1 に等しいということです。

まずは、m ≦ 1010 の上限に最も近くて G(m) が -1 にならない m をオフラインで調べてみました。
すると、m = 9999999995 の時に G(m) = 1105747502 で最大値となることがわかりました。
一方、m = 2 の時の G(m) = 3 が最小値です。(もちろん、-1 は除外しています)

さて、求める答えは、最小値と最大値の間にあるので、その中間値でテストし、それより大きいようなら最小値、小さいようなら最大値を中間値に更新していくという方法でコーディングしました。
ただし、組んだアルゴリズムだと、初期値が最小値か最大値と同じ(境界値)の場合、結果を見落としてしまうため、初期値は (最小値 - 1) と (最大値 + 1) にしました。(テストケースに境界値はなかったので通りはしましたが)

そうしてできたのが、以下の C のコードです。

|

« 『電脳体「キュラゲタム」を討伐せよ』の高度じゃないコード | トップページ | 「ディビジョン・ナイン問題」の高度じゃないコード »

コメント

コメントを書く



(ウェブ上には掲載しません)




トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/99795/63330411

この記事へのトラックバック一覧です: 「ロング・ロング・ストリング問題」の高度じゃないコード:

« 『電脳体「キュラゲタム」を討伐せよ』の高度じゃないコード | トップページ | 「ディビジョン・ナイン問題」の高度じゃないコード »