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: Guarding Zion
Description It is the 22 The underground world is actually the sewers of the previous cities in ruin — gigantic tunnels connecting the ground, Zion, and various other intersections. However all sewers have been destroyed when the machines first conquered the mankind. Because of limited time, the sewers have been repaired by people from Zion such that there will always be no more than one path from one intersection to another. No tunnel connects an intersection to itself. The best weapon we have is EMP (electromagnetic pulse) charge, an extremely powerful weapon to use against machines. Blowing an EMP charge will cause any electronic device within its range to stop functioning, therefore destroying the machines within range completely. However it can also cause another EMP charge within the range to malfunction, so the distance between any two EMP charges must be no less than their range. The council has decided to put EMP on certain intersections to minimize the possibility of the machines destroying Zion. Since our resources are limited, we can only afford to put EMP charges on certain intersections of the underground tunnels. Deploying an EMP charge on a certain intersection has a non-negative cost. What is the maximal distance you can cover with EMP charges, and what’s the minimum cost to achieve that maximal distance? Input There are multiple test cases in the input file. Each test case starts with three integers
Output For each test case, output two integers in the format as indicated in the sample output: the maximum distance EMPs can cover and the minimum cost you’ve found on a single line. Sample Input 2 1 3 5 6 1 0 6 0 0 0 Sample Output Case 1: 6 11 Source |

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

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

Any problem, Please Contact Administrator