Measuring Traffic

题目描述

紧邻 Farmer John 农场的高速公路最近车流量似乎大幅增加，至少 Farmer John 是这么觉得的。为了确认这一点，他想用一组传感器来测量高速公路上的车流量，每个传感器都能够测量一段道路上的交通流量速率。 不幸的是，某天 Farmer John 走过谷仓时绊了一跤，把装传感器的盒子掉进了一大桶牛奶里，结果这些传感器的工作效果变差了。现在，每个传感器不再输出一个精确的车流量读数，而是输出一个可能值的范围。例如，一个传感器可能输出区间 $[7, 13]$，表示该路段的车流量速率不小于 7 且不大于 13。 高速公路沿着农场延伸 $N$ 英里，且交通只沿一个方向流动：从第 1 英里朝第 $N$ 英里方向。Farmer John 想安装 $N$ 个传感器——每个 1 英里路段安装一个。在一些路段中有入口匝道（on-ramp）允许车辆进入高速公路；在这种情况下，Farmer John 会把传感器安装在入口匝道上，以（近似）测量进入的车流量。在一些路段中有出口匝道（off-ramp）允许车辆离开高速公路；在这种情况下，Farmer John 会把传感器安装在出口匝道上。每个路段最多包含一个匝道。 如果某段高速公路没有入口匝道或出口匝道，Farmer John 就把传感器安装在高速公路主路上。 给定 Farmer John 的 $N$ 个传感器读数，请确定在第 1 英里之前高速公路上初始车流量，以及在第 $N$ 英里之后仍继续在高速公路上的车流量，这两者各自可能的、尽可能精确的范围。这些范围应当与全部 $N$ 个传感器读数一致。

输入格式

第一行输入为 $N$（$1 \leq N \leq 100$）。接下来的 $N$ 行按从第 $1$ 英里到第 $N$ 英里的顺序描述每个 1 英里路段。 每行包含一个字符串，取值为 "on"（表示该路段有入口匝道）、"off"（表示该路段有出口匝道）或 "none"（表示没有匝道），后跟两个范围在 $0 \ldots 1000$ 的整数，表示该路段传感器输出区间的下界与上界。 如果该路段包含匝道，则传感器读数来自匝道；否则来自高速公路主路。 至少有一个路段会被标记为 "none"。

输出格式

输出第一行应包含两个整数，给出第 1 英里之前车流量速率的最精确可能范围。 输出第二行应包含两个整数，给出第 $N$ 英里之后车流量速率的最精确可能范围。 保证总是存在合法解。

4
on 1 1
none 10 14
none 11 15
off 2 3

10 13
8 12

提示

在本例中，第 2 与第 3 段的读数结合起来告诉我们，这两段中的车流量速率位于区间 $[11, 14]$，因为只有这个区间同时与读数 $[10,14]$ 和 $[11,15]$ 一致。在第 1 英里处，入口匝道恰好有 1 个单位的流量进入，因此在第 1 英里之前，车流量速率必须在区间 $[10, 13]$。在第 4 英里处，出口匝道有 2 到 3 个单位的流量离开，因此之后可能的车流量速率范围为 $[8,12]$。 题目来源：Brian Dean

标签: USACO|2019|Bronze

来源

USACO|2019|Bronze