📄 gtrucking.html
字号:
<HTML>
<HEAD>
<META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=gb2312">
<META NAME="GENERATOR" CONTENT="Mozilla/4.03 [zhcn] (Win95; I) [Netscape]">
<TITLE>1996 ACM Finals, Problem G - Trucking</TITLE>
<!SGML "ISO 8879:1986">
</HEAD>
<BODY BGCOLOR="#FFFFFF">
<HR NOSHADE>
<CENTER>
<H1>
1996 ACM Scholastic Programming Contest Finals</H1></CENTER>
<CENTER>
<H4>
sponsored by Microsoft</H4></CENTER>
<CENTER>
<H1>
Problem G</H1></CENTER>
<CENTER>
<H2>
Trucking</H2></CENTER>
<CENTER>
<H3>
Input file: truck.in</H3></CENTER>
Allied Container Movers (ACM) is a trucking company that provides overnight
freight delivery. ACM has a distribution network with several intermediate
container processing centers (ICPCs). At an ICPC, an incoming trailer is
unloaded at a stripping door. Freight destined for that center is simply
acknowledged as received. Onward shipments are distributed to relay doors
based on their next destinations, where they are loaded onto waiting trailers.
<P>Each ICPC has several stripping doors for unloading incoming trailers.
When the number of trailers to be stripped exceeds the number of stripping
doors, incoming trailers are queued until a door is available. A single
trailer may have freight for several different ICPCs. Trailers with freight
destined only for the local ICPC receive a lower priority for access to
a stripping door than trailers with relay freight. In a similar fashion,
trailers with relay freight having a closer final destination have lower
priority than trailers with relay freight having a distant final destination.
The time to unload a container and, if necessary, reload all its shipments
onto one or more relay trailers is always 2 hours regardless of the size
and number of shipments. A relay trailer is immediately routed to its next
destination when it is full or when all shipments for the day expected
for that destination have been loaded onto the trailer. Shipments are measured
as a percent of a trailer volume and may be subdivided to the nearest percent
in order to fill the trailer. There is no delay between a trailer departing
and another trailer becoming available at the relay or stripping doors.
There is never a shortage of trailers for onward distribution.
<P>In order to help ACM assess the efficiency of their network, you must
write a program to determine the average time a trailer waits for access
to a stripping door and identify those shipments which will not arrive
in their entirety at their intermediate or final destinations on time.
<H3>
<HR>Input</H3>
The input describes a possibly disjoint subset of the network's ICPCs and
traffic patterns that must be analyzed.
<P>The first line of the input contains an integer <B>n</B> which specifies
the number of ICPC descriptions to be processed, 1 <= <B>n</B> <=
100. This is followed by <B>n</B> descriptions, each describing one ICPC.
Each description begins with a line containing three integers, <B>c</B>
<B>s</B> <B>d</B>, where <B>c</B> is the center number, 0 <= <B>c</B>
<= 99, <B>s</B> is the number of stripping doors at center <B>c</B>,
0 <= <B>s</B> <= 10, and <B>d</B> is the number of relay doors at
center <B>c</B>, 0 <= <B>d</B> <= 10. There then follow <B>d</B>
lines, one for each relay door. Each of these lines contains three integers,
<B>r</B> <B>v</B> <B>l</B>, where <B>r</B> is the relay center's number,
0 <= <B>r</B> <= 99, <B>v</B> is the total volume of shipments to
that center for the day expressed as a percentage of trailer volume, 0
<= <B>v</B> <= 900 and <B>l</B> is the latest acceptable time for
shipments to arrive at center <B>r</B>, expressed as minutes since the
start of the day, 0 <= <B>l</B> <= 1440. (<B>v</B> < 100 indicates
that more than a single trailer must be used.)
<P>The second part of the input describes some of the day's traffic. This
part begins with one integer <B>m</B> on a line by itself indicating the
number of trailer arrival records that follow, 1 <= <B>m</B> <= 100.
Each record begins with a line containing three integers, a <B>c</B> <B>s</B>,
where a is the trailer's arrival time expressed as minutes since the start
of the day, 0 <= a <= 1440, at center number <B>c</B>, and <B>s</B>
is the number of shipments in the trailer, 0 <= <B>s</B> <= 10. Then
all <B>s</B> shipments are described by <B>s</B> lines of 5 integers, <B>i</B>
<B>o</B> <B>r</B> <B>v</B> <B>t</B>, representing the shipment identification
code i, 0 <= i. The second part of the input describes some of the day's
traffic. This part begins with one integer <B>m</B> on a line by itself
indicating the number of trailer arrival records that follow, 1 <= <B>m</B>
<= 100. Each record begins with a line containing three integers, a
<B>c</B> <B>s</B>, where a is the trailer's arrival time expressed as minutes
since the start of the day, 0 <= a <= 1440, at center number <B>c</B>,
and <B>s</B> is the number of shipments in the trailer, 0 <= <B>s</B>
<= 10. Then all <B>s</B> shipments are described by <B>s</B> lines of
5 integers, <B>i</B> <B>o</B> <B>r</B> <B>v</B> <B>t</B>, representing
the shipment identification code i, 0 <= <B>i</B> <= 99, the origin
and next relay center numbers <B>o</B> and <B>r</B> respectively, the volume
of the shipment <B>v</B> as a percentage of trailer volume and the time
<B>t</B> taken to travel from center <B>c</B> to destination <B>r</B> measured
in minutes. <B>t</B> is zero if <B>c</B> equals <B>r</B>. Arrival records
are in order of ascending values of a. No two records have the same pair
(a,<B>c</B>). All center numbers used as values for <B>c</B> and <B>r</B>
will have an appropriate corresponding definition in the first part of
the input, though the center numbers used for <B>o</B> need not.
<H3>
<HR>Output</H3>
For each of the n ICPCs, your program must write out a line describing
the average wait time for stripping doors in the appropriate one of these
two forms:
<BLOCKQUOTE>The average wait for a stripping door at ICPC <B>c</B> is ###.#
minutes.
<BR>There is no wait for a stripping door at ICPC <B>c</B>.</BLOCKQUOTE>
The average wait time is affected only by trailers which wait at least
one minute for a stripping door.
<P>Your program should then list all the shipments any part of which will
not arrive at their intermediate or final destinations by any of the latest
arrival times given along the route. This report should appear in columns
headed as shown:
<PRE> The late shipments are:
Id Origin Destination Volume</PRE>
<H3>
<HR>Sample Input:</H3>
<PRE>2
0 1 1
8 40 600
8 3 4
6 115 1200
2 95 1260
10 100 1440
4 55 1380
7
500 0 1
17 11 8 40 80
700 8 3
24 11 8 45 0
18 11 6 40 120
23 11 10 15 600
720 8 1
16 3 8 100 0
750 8 2
4 15 2 50 180
7 15 6 50 120
760 8 4
14 3 4 20 300
27 3 2 20 180
33 3 10 35 600
16 3 6 25 120
780 8 2
12 9 2 25 180
15 9 4 35 300
800 8 1
19 18 10 50 600</PRE>
<H3>
<HR>Output for the Sample Input:</H3>
<PRE>There is no wait for a stripping door at ICPC 0.
The average wait for a stripping door at ICPC 8 is 63.3 minutes.
The late shipments are:
Id Origin Destination Volume
17 11 8 40
23 11 10 15
33 3 10 35
19 18 10 50</PRE>
<HR NOSHADE>
</BODY>
</HTML>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -