#PU917. USACO 2019 February Contest, Bronze — Problem 3. Measuring Traffic
USACO 2019 February Contest, Bronze — Problem 3. Measuring Traffic
USACO 2019 February Contest, Bronze — Problem 3. Measuring Traffic
题目描述
The highway adjacent to Farmer John's farm has recently seen a dramatic increase in traffic, or at least so it seems to Farmer John. To be sure, he wants to measure the traffic flow on the highway with a set of sensors, each capable of measuring the rate of flow of traffic on a segment of road. Unfortunately, while walking through the barn one day, Farmer John trips and drops his box of sensors into a large vat of milk, after which they no longer work as well. Instead of producing a single exact reading of traffic flow rate, each sensor now outputs a range of possible values. For example, a sensor might
输入格式
The first line of input contains (). Each of the remaining lines describes a 1-mile segment of the road, in order from mile to mile . Each line contains a string that is either "on" (if there is an on-ramp on this segment), "off" (if there is an off-ramp), or "none" (if there is no ramp), followed by two integers in the range , indicating the lower and upper endpoints of the sensor range from this segment. If the segment contains a ramp, the sensor reading is from the ramp. Otherwise, it is from the main highway. At least one of the highway segments will be designated as "none".
输出格式
The first line of output should contain two integers giving the most specific range possible for the rate of traffic flow prior to mile 1. The second line of
数据范围
(见题面原文)
样例
样例 1
4
on 1 1
none 10 14
none 11 15
off 2 3
10 13
8 12
In this example, the combination of readings from segments 2 and 3 tell us that
the flow rate through these segments is somewhere in the range $[11, 14]$, since
only this range is consistent with both the readings $[10,14]$ and $[11,15]$. In
mile 1, exactly 1 unit of flow enters on an on-ramp, so prior to mile 1, the
flow rate must be in the range $[10, 13]$. In mile 4, between 2 and 3 units
exits on an off-ramp, so the range of possible flow rates after this is
$[8,12]$.
Problem credits: Brian Dean