POJ-1243 One Person （經典級dp

one person

time limit: 1000ms

memory limit: 10000k

total submissions: 2122

accepted: 1426

description

in the game show "the price is right", a number of players (typically 4) compete to get on stage by guessing the price of an item. the winner is the person whose guess is the closest one not exceeding the actual price. because of the popularity of the one-person

game show "who wants to be a millionaire",the american contest management (acm) would like to introduce a one-person version of the "the price is right". in this version, each contestant is allowed g (1 <= g <= 30) guesses and l (0 <= l <= 30)lifelines. the

contestant makes a number of guesses for the actual price. after each guess, the contestant is told whether it is correct, too low, or too high. if the guess is correct, the contestant wins. otherwise,he uses up a guess. additionally, if his guess is too high,

a lifeline is also lost. the contestant loses when all his guesses are used up or if his guess is too high and he has no lifelines left. all prices are positive integers. 

it turns out that for a particular pair of values for g and l, it is possible to obtain a guessing strategy such that if the price is between 1 and n (inclusive) for some n, then the player can guarantee a win.the acm does not want every contestant to win,

so it must ensure that the actual price exceeds n.at the same time, it does not want the game to be too diffcult or there will not be enough winners to attract audience. thus, it wishes to adjust the values of g and l depending on the actual price. to help

them decide the correct values of g and l, the acm has asked you to solve the following problem.given g and l, what is the largest value of n such that there is a strategy to win as long as the price is between 1 and n (inclusive)? 

input

the input consists of a number of cases. each case is specified by one line containing two integers g and l, separated by one space. the end of input is specified by a line in which g = l = 0. 

output

for each case, print a line of the form: 

case c: n 

where c is the case number (starting from 1) and n is the number computed. 

sample input

sample output

不得不說，看了題解之後才感受到這題的巧妙。

題目大意：

有一種猜數字的遊戲，你有g次機會以及l點生命值，遊戲首先給定一個範圍1～n，你要來猜在此範圍内的一個數字x。你的每次猜測都會告訴你是猜高了還是低了，每次猜測都要損失一次猜測機會（即g--），但如果你猜的值比x高了，那麼同時還要損失一點生命值（l--）。

現在主辦人面臨一個問題：若給定的範圍太大，就有很有可能導緻參賽者用盡機會和生命值也猜不到這個x；而範圍太小的話又降低了趣味性。是以，需要你來幫忙，根據給定的g和l來确定一個盡量大的範圍，同時確定該範圍内的所有數字都是一定可以被猜到的。

解題思路：

設f(g,l)為有g次機會，l點生命值時最多可猜到多少個數字（注意此處的描述

猜數字我們都知道是要用二分法來猜.首先，要考察g與l間的大小關系：

1）、若l=0，即一次都不可以猜高了，那麼保險能猜到的方案就隻有1、2、3、4。。。的一個一個往上猜，那麼最多能猜到的數字個數也就是g

2）、若l>g，即可以猜高的次數比較多。可事實上，每次猜測都要耗費一點g，那麼多出來的生命值也就沒什麼意義了，是以這種情況與l=g相同，即f(g,g)

3）、若l<=g，那麼，就要繼續分類考慮。首先進行一次猜測（假設猜的是k），那麼可能得到以下三種情況之一：

（1）：猜低了。也就是說明正确答案大于k（此處可腦補一條以k為原點的數軸輔助了解），那麼接下來的猜測就要相對于k往前（以數軸正方向為前），此時剩餘g-1點機會，l點生命，也就是說可以再向前猜出f(g-1,l)個數字。

（2）：猜高了。也就是說正确答案小于k，那麼接下來就要相對于k向後猜，同理，可以再向後猜出f(g-1,l-1）個數字。

（3）：恰好猜到～

總結下，即當l<=g時，f(g,l)=f(g-1,l)+f(g-1,l-1)+1

例如：

有2次機會（先不考慮生命值），就可以猜出1～3中所有數，有3此機會，就可猜出1～7

不過不要把思路局限為隻能從1開始。比如有2次機會，也可以猜出5～7範圍内給定的某個數，即是說有兩次機會時，可以猜出連續的3個數字。那麼3次機會時，就可以看作首先猜4，剩下2次機會，可以向前或向後猜3個數字，即範圍為1～7；同理，若有三次機會，第一次猜的是0，那麼就可以猜到-3～3。

代碼：