問題
2人で行うゲームを考える。i回戦目で勝つと2*i-1ポイントがもらえる。両者の最終的なスコア(x, y)が与えられる。xとなるスコアを得るのに必要な最小勝利回数を求めよ。与えられたスコアを満たせない場合は-1を返す。
解法
ゲームの合計のスコアはx+yとなる。n回戦まで行った時の合計のスコアは以下となる。
よって、nは以下となる。
xが以下の値となるまで、xから2n-1を引いていく。
2は作れない数字なので、除外する必要がある。
xが奇数ならあと1回で、偶数なら2回でxのスコアを実現できる。
計算量