首页 > 专题系列 > Java解POJ > POJ 2661 Factstone Benchmark [解题报告] Java
2013
11-11

POJ 2661 Factstone Benchmark [解题报告] Java

Factstone Benchmark

问题描述 :

Amtel has announced that it will release a 128-bit computer chip by 2010, a 256-bit computer by 2020, and so on, continuing its strategy of doubling the word-size every ten years. (Amtel released a 64-bit computer in 2000, a 32-bit computer in 1990, a 16-bit computer in 1980, an 8-bit computer in 1970, and a 4-bit computer, its first, in 1960.)

Amtel will use a new benchmark – the Factstone – to advertise the vastly improved capacity of its new chips. The Factstone rating is defined to be the largest integer n such that n! can be represented as an unsigned integer in a computer word.

Given a year 1960 <= y <= 2160, what will be the Factstone rating of Amtel's most recently released chip?

输入:

There are several test cases. For each test case, there is one line of input containing y. A line containing 0 follows the last test case.

输出:

For each test case, output a line giving the Factstone rating.

样例输入:

1960
1981
0

样例输出:

3
8

解题代码:

//* @author: [email protected]
import java.util.*;
public class Main
{
 public static void main(String[] args)
 {
  Scanner in=new Scanner(System.in);
  while(true)
  {
	int a=in.nextInt();
	if(a==0) break;
	a-=1960;
	a/=10;
	a=(int)Math.pow(2, a+2);
	double k=0;
	int n=2;
	while(k< a)
	{
          k+=Math.log(n)/Math.log(2);
	  n++;
	}
	System.out.println(n-2);
   }
 }
}

  1. 第二种想法,我想来好久,为啥需要一个newhead,发现是把最后一个节点一直返回到嘴上面这层函数。厉害,这道题之前没样子想过。

  2. 这道题目的核心一句话是:取还是不取。
    如果当前取,则index+1作为参数。如果当前不取,则任用index作为参数。

  3. a是根先忽略掉,递归子树。剩下前缀bejkcfghid和后缀jkebfghicd,分拆的原则的是每个子树前缀和后缀的节点个数是一样的,根节点出现在前缀的第一个,后缀的最后一个。根节点b出现后缀的第四个位置,则第一部分为四个节点,前缀bejk,后缀jkeb,剩下的c出现在后缀的倒数第2个,就划分为cfghi和 fghic,第3部分就为c、c