|Online Judge||Problem Set||Authors||Online Contests||User|
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.
POJ Monthly--2006.04.28, frkstyc@PKU_RPWT
[Submit] [Go Back] [Status] [Discuss]
Home Page Go Back To top
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator