首页 > 专题系列 > Java解POJ > POJ 2819 TN’s Kingdom I – Establishment [解题报告] Java
2013
11-12

POJ 2819 TN’s Kingdom I – Establishment [解题报告] Java

TN’s Kingdom I – Establishment

问题描述 :

Once upon a time, there was a king called TN. Probably because of his quick rise and quick fall, he was little mentioned in written history. Still, I want to share with you some deeds of his.

Before TN had himself crowned, the kingdom was under the reign of Dzx. Dzx was a hard-working king. But luck had little been by his side. During his reign, natural disasters fell frequently. After a drought that lasted for ten years, many citizens had lost their confidence in him. TN noticed the change and found it a good time to usurp power. Without too much effort, he managed to assemble a small troop of militants and launched his first insurrection, capturing several towns.
Hearing about the insurrection, the citizens soon divided. Some remained on their loyalty, but many more changed their stand. Not long after that, the divide evolved into a year-long war. At the end of the war, TN succeeded in seizing the scepter while Dzx was forced to exile.
The war was short but violent. It devastated almost the whole kingdom. As the new king, the first challenge TN faced was reconstruction. And the most urgent task was to rebuild the roads between towns in the kingdom. The job had to be done quick, therefore TN decided to rebuild as few roads as possible so that between every pair of towns there would exist a path consisting solely of new roads. In revenge on Dzx’s persistent resistance during war-time, he wanted to isolate Dzx’s hometown by letting only one new road connect it to another town. He wondered the proportion of such rebuilding plans to all plans rebuilding the fewest number of roads.

 

输入:

The input consists of one or more lines each containing a positive integer between 2 and 1015 and followed by a line containing a single zero which indicates the end of input and should not be processed. Each line represents a separate test case. The integer it contains gives the number of towns in the kingdom.

输出:

For each test case your solution should output one line containing the proportion that TN wondered represented in decimal form and truncated to fourteen decimal places.

样例输入:

10
0

样例输出:

0.43046721000000

解题代码:

//* @author: 
import java.util.*;
import java.math.BigDecimal;
import java.lang.String;

class Main
{
    public static void main(String args[])
    {
        Scanner cin = new Scanner(System.in);
        BigDecimal bd;
        String out;
        int l, i;
        long n;
        while (cin.hasNext())
        {
          n = cin.nextLong();
          if (n == 0)
         	break;
          if (n <= 2)
          {
           System.out.println("1.00000000000000");
           continue;
           }
           bd = Make(n);
           bd = power(bd, n - 2);
	    out = bd.toString().substring(0, 16);
           System.out.println(out);
        }
    }

static BigDecimal power(BigDecimal bd, long n)
{
    	BigDecimal ans;
    	if (n == 0)
    	{
    		return BigDecimal.ONE;
    	}
    	ans = power(bd, n / 2);
    	ans = ans.multiply(ans);
    	if (n % 2 == 1)
    	{
    		ans = ans.multiply(bd);
    	}
    	if (ans.toString().length() > 50)
    	{
    		ans = new BigDecimal(ans.toString().substring(0, 50));
    	}
    	return ans;
    }

    static BigDecimal Make(long N)
    {
    	String s = "";
    	long v = N - 1;
    	int i;
    	for (i = 0; i < 50; i++)
    	{
    		v = (v % N) * 10;
    		s += v / N;
    	}
    	s = "0." + s;
    	return new BigDecimal(s);
    }
}

  1. 题目需要求解的是最小值,而且没有考虑可能存在环,比如
    0 0 0 0 0
    1 1 1 1 0
    1 0 0 0 0
    1 0 1 0 1
    1 0 0 0 0
    会陷入死循环

  2. 第一题是不是可以这样想,生了n孩子的家庭等价于n个家庭各生了一个1个孩子,这样最后男女的比例还是1:1