解答ヒントのメモ。

問題 107 The Cat in the Hat
難易度 投稿数 18906 (正解率 15.9 %)

技法の問題というよりも、純粋に数学の問題かもしれない。

入力データは正の整数二つ、data1 と data2。 問題を読めば判るが、
   data1 = (N+1)k
   data2 = Nk

となる。出力結果も2つの整数、 output1 と output2
   output1 = (data2-1)/(N-1)
   output2 = data1 + N * (data1 - data2)

つまり、Nの値さえ判れば、簡単にプログラムは解ける。

整数の長さ(上限)について、問題では全く(わざだと思うが)触れていなかったが、解答してみて判り、32ビットの整数だけを考えればOK。64ビットとか、さらに数百ビットとかになるとえらい大変だが。

ということで、与えられた、32ビット以内の整数 (N+1)k と Nk に対し、N を求めなさい、というのが問題の本質。

ただし、 2k と 1 の入力ペアについても、その処理を忘れないように。

Comments are closed.

Post Navigation