## LINUX-L@LISTS.UFL.EDU

#### View:

 Message: [ First | Previous | Next | Last ] By Topic: [ First | Previous | Next | Last ] By Author: [ First | Previous | Next | Last ] Font: Monospaced Font

Subject:

Re: Jim is the MAN!

From:

Date:

Wed, 21 Mar 2007 23:19:01 -0400

Content-Type:

text/plain

Parts/Attachments:

 text/plain (61 lines)
 > > Congratulations to Jim Wilson for his Python solution to this year's > > Codeslinger championship. Several of us hammered away with brute force > > solutions, but Jim sliced through this problem with a quick and simple > > approach based on "greedy" grouping. We continued trying for half an > > hour after Jim submitted his solution, but still none of us could > > solve the problem. > > For those who don't make it to the meetings, is the problem posted > anywhere?...so we can take a whack at it before seeing the solution(s). > Convoy A convoy of vehicles has lined up on a single lane and one-way street in front of a single lane and one-way bridge over a river. Note that since the street is single lane, no vehicle can overtake any other. The bridge can sustain a given maximum load. To control the traffic on the bridge, operators are stationed on either end of the bridge. The convoy of vehicles is to be divided into groups, such that all the vehicles in any group can cross the bridge together. When a group reaches the other side, the operator on that side of the bridge uses a telephone to inform the operator on this side that the next group can start its journey over the bridge. The weight of each vehicle is known. The sum of the weights of the vehicles in any group cannot exceed the maximum load sustainable by the bridge. Associated with each vehicle is the maximum speed with which it can travel over the bridge. The time taken by a group of vehicles is calculated as the time taken by the slowest vehicle in the group to cross the bridge. The problem is to find the minimum amount of time in which the entire convoy can cross the bridge. Input to the Program The first line of input contains three positive integers (separated by blanks): the first one represents the maximum load that the bridge can sustain (in tonnes); the second one represents the length of the bridge (in kms); and the third one is the number of vehicles (n) in the convoy. Each of the next n lines of input contains a pair of positive integers, w s (separated by blanks), where w is the weight of the vehicle (in tonnes) and s is the maximum speed (in kmph) with which this vehicle can travel over the bridge. The weights and speeds of the vehicles are specified in the same order as the order in which the vehicles are queued up. You can assume that n < 1000. Output of the Program The output of the program should be a single real number specifying the minimum time in minutes in which the convoy can cross the bridge. ========= = Input file = ========= 100 5 10 40 25 50 20 50 20 70 10 12 50 9 70 49 30 38 25 27 50 19 70

2021
2020
2019
2018
2017
2016
2015
2014
2013
2012
2011
2010
2009
2008
2007
2006
2005
2004
2003
2002
2001
2000
1999
1998
1997