Codeforces #196 Div1. A. Quiz

CF196はDiv1もあったけど不参加だった回。
http://codeforces.com/contest/338/problem/A

問題

N問のクイズがあり、１問クイズに正解すると１ポイント貰える。
また、K問連続正解すると所有ポイントが倍になる。
N問中M問正解した場合、得られる最小ポイントを答えよ。

解法

後半になるほどでポイント倍化によるポイント増分が大きい。
よって、後半は倍化しないようにすればよい。
すなわち、(K-1)問解いたら１問失敗するというのを繰り返す。

失敗する問題数は(N-M)なので、(K-1)*(N-M+1)問までは(K-1)問解いて１問失敗、を繰り返せる。
残りの正解分は最初に連続正解し、ポイントが少ない間に倍化しておく。
前半X問(>=K)が正解なら、そのポイントは2*K*(2^(X/K)-1) + (X%K)である。

ll N,K,M;
ll mo=1000000009;

ll modpow(ll a, ll n, ll p) {
	ll r=1;
	while(n) {
		if(n%2) r=(r*a)%p;
		a=(a*a)%p;
		n>>=1;
	}
	return r;
}

void solve() {
	int f,i,j,k,l, x,y;
	ll ret=0;
	
	cin>>N>>M>>K;
	M=N-M;
	ll t=K*M;
	if(N<=t) return _P("%d\n",N-M);
	N-=t;
	l = (K-1)*M + (N%K);
	N/=K;
	ret = (modpow(2,N+1,mo) - 2) * K + l;
	ret = ((ret%mo)+mo)%mo;
	cout << ret%mo << endl;
}

まとめ

ここらへんはまだ簡単。