TopCoder problem "Amazing" used in TCCC06 Semi 1 (Division I Level Three)



Problem Statement

    We are designing an Amazing Race course. Contestants will travel back and forth between various cities. We want to choose the required sequence of cities so that the total effort of a contestant is as close as possible to 1000.

The total effort of a contestant is the sum of the effort for each city-to-city trip, but the effort for a trip depends on how tired the contestant is. Let effort(c1,c2) be the effort required to travel from city c1 to city c2 when a contestant is fresh. We estimate that if the contestant has already completed k trips then the effort required for a trip from city c1 to city c2 is

                 factork *  effort(c1,c2)
where factor is a fixed value >= 1.

Create a class Amazing that contains a method totalE that is given factor, numTrips, and a String[] effort. Each element of effort contains a single space separated list of integers. The jth integer in the ith element of effort is effort(ci,cj). Your method should find the race course with exactly numTrips trips that comes closest to requiring a total effort of 1000, and return the absolute difference between that total effort and 1000.

A trip may go from a city to itself, and effort(ci,ci) is not necessarily 0.

 

Definition

    
Class:Amazing
Method:totalE
Parameters:double, int, String[]
Returns:double
Method signature:double totalE(double factor, int numTrips, String[] effort)
(be sure your method is public)
    
 

Notes

-Your return value must have an absolute or relative error less than 1e-9.
 

Constraints

-factor will be between 1.0 and 2.0, inclusive.
-numTrips will be between 1 and 10, inclusive.
-effort will contain n elements where n is between 1 and 10, inclusive.
-Each element of effort will contain exactly n non-negative integers separated by single spaces.
-Each element of effort will contain no leading spaces and no trailing spaces.
-Each integer in each element of effort will be between 0 and 1000, inclusive, and contain no leading zeroes.
 

Examples

0)
    
1.0
2
{"1000 300 700","200 0 901","35 100 0"}
Returns: 1.0
One course requires contestants to start in city 1, then travel to city 2, and then back to city 1. The total effort would be 1001. The only other equally good course would be to start in city 2, then travel to city 1 and then back to city 2.
1)
    
2.0
2
{"1000 300 700","200 0 901","35 100 0"}
Returns: 29.0
Now that the tiredness factor is 2.0, the courses from the previous example would require too much effort (1101 and 1902 respectively). The best course would be to start at city 1, go to city 2 at an effort of 901 and then to city 0 with an additional effort of 2.0*35 giving a total of 971.
2)
    
1.3
10
{"1000 300 700","200 0 901","35 100 0"}
Returns: 2.8999999999998636

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=6861

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10132&pm=6861

Writer:

dgoodman

Testers:

PabloGilberto , radeye , Olexiy , Andrew_Lazarev

Problem categories:

Brute Force, Search