Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|

Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |

Language: Constructing Roads
Description In the days of yore, Han was a prosperous kingdom. But at the turn of the century, hard times fell upon the kingdom. A plague swept through the land, and barbarians galloped in from the north, burning farms, destroying roads, and pillaging villages. All that remained were a few isolated strongholds scattered throughout the land. It has now been nearly a decade since the last wave of barbarians stormed through, and the land breathes a sigh of relief. People are becoming revitalized with the hope that they can once again transform the kingdom back into its former glory. Since all the roads were destroyed, the strongholds were left in isolation, so the first order of business was to build a network of roads connecting all the strongholds. Each stronghold thought it would be a reasonable plan to start by building a road to the closest stronghold near it. If there were two strongholds of equal distance, the stronghold whose name comes before the other in the dictionary would be chosen. Each stronghold builds at its own rate, measured in feet/hour. Because they wished to finish as soon as possible, construction happened 24 hours a day, continuously advancing the construction site (the end of the road) towards the destination. Of course, construction on a road would stop if the road ran into another road or a city. At the beginning of the New Year, there was a big celebration, and all the strongholds began construction at the same time. Little did the people of Han know that the barbarians had again infiltrated their kingdom and were carefully observing the progress of the roads. The barbarians were curious about the progress of the roads. In particular, they wanted answers to two type of questions. - After exactly
*t*hours since construction began on the New Year, what is the absolute minimum length of additional roads that still need to be built in order to connect all cities? These additional roads are allowed to join two cities, two construction sites, or a city and a construction site. - What is the fewest number of hours that must elapse since the New Year before the minimum length of additional roads that still need to be built is at most
*l*?
Write a program to answer these questions given Han’s construction plan. Input There will be several test cases, each representing a possible scenario for Han. The first line of each test case will contain a positive integer number The input data is terminated by a line that contains one zero, and should not be processed. Output For each test case, output the answers to each question, formatted as in the sample output. If for question 2, at no point in time will there be only Sample Input 4 portland 0 0 3 seattle 0 10 2 newyork 20 6 1 boston 20 0 1 1 0 1 2.0 1 3.0 2 29 2 1.0 0 2 bree -10 -10 1 buckland 10 10 2 1 5 0 0 Sample Output Kingdom 1 36.000 feet left at time 0.000 22.000 feet left at time 2.000 20.000 feet left at time 3.000 1.000 hours before 29.000 feet left NEVER Kingdom 2 13.284 feet left at time 5.000 End Source |

[Submit] [Go Back] [Status] [Discuss]

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di

Any problem, Please Contact Administrator