[Extra Problem | 1996 ACM finals problem set | My ACM problem archive | my home page]

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.

Input

The first line of the input contains an integer **n** which
specifies the number of ICPC descriptions to be processed, 1 <=
**n** <= 100. 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, 0 <= **c** <= 99, **s** is the number of
stripping doors at center **c**, 0 <= **s** <= 10, and **d**
is the number of relay doors at center **c**, 0 <= **d** <=
10. 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, 0 <= **r** <= 99, **v**
is the total volume of shipments to that center for the day expressed
as a percentage of trailer volume, 0 <= **v** <= 900 and **l**
is the latest acceptable time for shipments to arrive at center
**r**, expressed as minutes since the start of the day, 0 <=
**l** <= 1440. (**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, 1 <= **m** <=
100. 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, 0 <= a <= 1440, at center number
**c**, and **s** is the number of shipments in the trailer, 0 <=
**s** <= 10. Then all **s** shipments are described by **s**
lines of 5 integers, **i** **o** **r** **v** **t**,
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 **m** on a line by itself indicating the number of
trailer arrival records that follow, 1 <= **m** <= 100. 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, 0 <= a <= 1440, at center number **c**, and
**s** is the number of shipments in the trailer, 0 <= **s** <=
10. Then all **s** shipments are described by **s** lines of 5
integers, **i** **o** **r** **v** **t**, representing
the shipment identification code i, 0 <= **i** <= 99, 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.

Output

The average wait for a stripping door at ICPCThe average wait time is affected only by trailers which wait at least one minute for a stripping door.cis ###.# minutes.

There is no wait for a stripping door at ICPCc.

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

Sample Input:

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

Output for the Sample Input:

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

This page maintained by Ed Karrels.

Last updated September 20, 1999