1243 One Person

問題概要

物の値段を当てる次のようなゲームがある。
プレイヤーは値段を言い、

  • 当たっていたら勝利
  • 外れていたらGが1減る。本当の値段がより低かったか、より高かったかが教えられる。
  • 本当の値段がより低かった場合更にLが1減る

GまたはLが0になるとゲームオーバーである。
G,Lが与えられたとき、値段が1〜Nのどの整数でも言い当てられるような最大のNを求めよ。

G,L≦30を満たす。

解法

dp[g][l]にGが残りg,Lが残りlのときに当てられる"値段の幅"であるとする。


このとき、値段としてxを宣言したとする。
当たる場合、実際の値段はもっと小さかった場合、大きかった場合がある。
小さかった場合、G=g-1,L=l-1で1〜x-1の区間にある値段を当てる必要がある。
大きかった場合、x+1〜x+dp[g-1][l]の値段を当てられる。


以上より、dp[g][l]=dp[g-1][l-1]+1+dp[g-1][l]の漸化式が立つ。

ソースコード

int g,l;
ll dp[31][31];

int main()
{
	for(int i=1;i<31;i++)rep(j,31)
	{
		dp[i][j]=(j>0?dp[i-1][j-1]:0)+dp[i-1][j]+1;
	}
	
	int cs=0;
	while(scanf("%d%d",&g,&l),g)
	{
		printf("Case %d: %lld\n",++cs,dp[g][l]);
	}
	
	return 0;
}