首页 > 专题系列 > Java解POJ > POJ 1243 One Person [解题报告] Java
2013
11-09

POJ 1243 One Person [解题报告] Java

One Person

问题描述 :

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)?

输入:

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.

输出:

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.

样例输入:

3 0
3 1
10 5
7 7
0 0

样例输出:

Case 1: 3
Case 2: 6
Case 3: 847
Case 4: 127

解题代码:

/* @author:zeropinzuo */
import java.util.*;

public class Main{
 static Scanner cin;
 static int Case = 0;
 static int[][] result;
 public static void main(String args[]){
  cin = new Scanner(System.in);
	
  result = new int[100][100];
  int i,j;
  for(i = 0;i < 100;i++)
   for(j = 0;j < 100;j++)
     if(i == 1)
	result[i][j] = 1;
     else if(j == 0)
	result[i][j] = i;
     else
	result[i][j] = 0;
		
		
     while(true){
	if(!work(cin.nextInt(),cin.nextInt()))
	  break;
     }
		
    return;
  }
	
  static boolean work(int m,int n){
   if((m == 0)&&(n == 0))
     return false;
		
   Case++;
   System.out.println("Case "+Case+": "+compute(m,n));
   return true;
  }
	
 static int compute(int m,int n){
    if(result[m][n] != 0)
	return result[m][n];
		
    result[m][n] = compute(m-1,n-1)+compute(m-1,n)+1;
    return result[m][n];
		
  }
}

  1. 很高兴你会喜欢这个网站。目前还没有一个开发团队,网站是我一个人在维护,都是用的开源系统,也没有太多需要开发的部分,主要是内容整理。非常感谢你的关注。