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.
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.
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.
The input describes a possibly disjoint subset of the network's ICPCs and
traffic patterns that must be analyzed.
The first line of the input contains an integer n which specifies the number
of ICPC descriptions to be processed, 
. This is
followed by n
descriptions, each describing one ICPC. Each description begins with a line
containing three integers, c s d, where c is the center
number, 
,
s is the number of stripping doors at
center c, 
, and d is
the number of relay doors at center c, 
.
There then follow d
lines, one for each relay door. Each of these lines contains three integers,
r v l, where r is the relay center's
number, 
, v is the total
volume of shipments to that center for the day expressed as a percentage of
trailer volume, 
and l is the latest acceptable time for
shipments to arrive at center r, expressed as minutes since the start of the
day, 
. (v > 100 indicates that more than a single trailer must
be used.)
The second part of the input describes some of the day's traffic. This part
begins with one integer m on a line by itself indicating the number of
trailer arrival records that follow, 
. Each record begins with
a line containing three integers, a c s, where a is the trailer's arrival
time expressed as minutes since the start of the day, 
, at
center number c, and s is the number of shipments in the
trailer, .
Then all s shipments are described by s lines of 5
integers, i o r v t,
representing the shipment identification code i, 
,
the origin and next relay center
numbers o and r respectively, the volume of the shipment v as
a percentage
of trailer volume and the time t taken to travel from center c to
destination r measured in minutes. t is zero if c
equals r. Arrival records
are in order of ascending values of a. No two records have the same pair
(a,c). All center numbers used as values for c and r will have an
appropriate corresponding definition in the first part of the input, though
the center numbers used for o need not.
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:
The average wait for a stripping door at ICPC c is ###.# minutes.
There is no wait for a stripping door at ICPC c.
The average wait time is affected only by trailers which wait at least one
minute for a stripping door.
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:
The late shipments are:
Id Origin Destination Volume
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
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