LISTSERV mailing list manager LISTSERV 16.0

Help for LINUX-L Archives


LINUX-L Archives

LINUX-L Archives


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

LISTSERV Archives

LISTSERV Archives

LINUX-L Home

LINUX-L Home

LINUX-L  2007

LINUX-L 2007

Subject:

Re: Jim is the MAN!

From:

Eric Lavigne <[log in to unmask]>

Reply-To:

Platform Independent Linux List! <[log in to unmask]>

Date:

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

Content-Type:

text/plain

Parts/Attachments:

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

Top of Message | Previous Page | Permalink

Advanced Options


Options

Log In

Log In

Get Password

Get Password


Search Archives

Search Archives


Subscribe or Unsubscribe

Subscribe or Unsubscribe


Archives

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

ATOM RSS1 RSS2



LISTS.UFL.EDU

CataList Email List Search Powered by the LISTSERV Email List Manager