UnKoder #03 : Frog Jumping

変にバグって苦戦しまくり。
https://www.hackerrank.com/contests/unkoder-03/challenges/frog-jumping

問題

１次元数直線上で、蛙は１回のジャンプで正負どちらかの方向に5の累乗分の距離移動できる。
N移動するのに必要な最小ジャンプ回数を求めよ。

解法

Nを５進数表記したとき、最上位の桁をXとしてN = X*5^k + Y (Y＜5^k)と表せるとする。
以下の２通りの戦略をDFSで試していけば良い。

• 5^kのジャンプをX回刻み、残りYを再帰的に処理する。
• 5^(k+1)のジャンプを1回行い、(5^(k+1) - N)分戻るのにかかる回数を再帰的に求める。
  • 行ったり来たりするのを防ぐため、(5^(k+1) - N)＜Nの時だけこちらを行う。

ll dodo(ll hoge) {
	hoge=abs(hoge);
	if(hoge==0) return 0;
	
	ll t=1;
	while(t*5<=hoge) t*=5;
	if(t==hoge) return 1;
	ll tr=hoge/t;
	
	ll ret=tr+dodo(hoge-tr*t);
	ll a=abs(hoge-t*5);
	if(a<hoge) ret=min(ret,1+dodo(a));
	return ret;
}

void solve() {
	ll N;
	cin>>N;
	cout<<dodo(N)<<endl;
}

まとめ

なぜバグったかいまだにわからない。
absを適切に入れないと落ちる。型の問題？