TopCoder SRM 478 Div 1 Easy CarrotJumping

TopCoder

問題概要

数直線上にいるウサギが、初期位置initからジャンプを繰り返してゴールまで行く。
このとき必要なジャンプの最小回数を求めよ。
100000回以下のジャンプでゴールへ到達するのが不可能な場合-1を返せ。


ただし、

  • ゴールは座標がx%1000000007==0である点（そのような点どれでもよい）
  • 座標xにいるウサギのは4*x+3または8*x+7にジャンプできる

解法

4*x+3を小ジャンプ、8*x+7を大ジャンプと呼ぶと、小ジャンプ3回は大ジャンプ2回と等しい。（64*x+63)
したがって、行けるとこまで大ジャンプで行って、残りの1回か2回を小ジャンプするのが最適解。

ソースコード

const int MOD=1000000007;

class CarrotJumping {
	public:
	int theJump(int init)
	{
		int t=100001,c=init;
		rep(i,100001)
		{
			if(c==0)t=min(t,i);
			if(((ll)c*4+3)%MOD==0)t=min(t,i+1);
			if(((ll)c*16+15)%MOD==0)t=min(t,i+2);
			
			c=((ll)c*8+7)%MOD;
			
		}
		return t<=100000?t:-1;
	}
};