Question 5

Text from the official booklet. Refer to the PDF for original mathematical notation, formatting, and linked input files. Printed samples and inputs are reproduced as published.

A researcher is studying traffic flow along a straight 𝑁-mile highway, where traffic moves in a
single direction from mile 1 to mile 𝑁. To measure the flow of vehicles, they install 𝑁
sensors—one per mile. However, due to a malfunction, each sensor only provides a range of
possible values instead of an exact reading. For example, a sensor might report a traffic flow
between 7 and 13 vehicles per unit time.
Some segments of the highway have on-ramps where additional vehicles enter, while others
have off-ramps where vehicles exit. If a segment has an on-ramp, the sensor measures the
number of vehicles entering. If a segment has an off-ramp, the sensor measures the number of
vehicles exiting. If there are no ramps, the sensor directly measures the traffic flow along the
highway. Each segment contains at most one ramp.
Given the readings from the 𝑁 sensors, determine the most precise possible ranges for the
initial traffic flow entering the highway before mile 1 and for the remaining traffic continuing past
mile 𝑁. These ranges should be consistent with all sensor readings.
INPUT FORMAT:
The first line of input contains N (1≤N≤100). Each of the remaining N lines describes a 1-mile
segment of the road, in order from mile 1 to mile N. 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 0…1000, 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".
OUTPUT FORMAT:
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 output should contain two integers giving
the most specific range possible for the rate of traffic flow after mile N. A valid solution is always
guaranteed to exist.
SAMPLE INPUT:
4
on 1 1
none 10 14
none 11 15
off 2 3
SAMPLE OUTPUT:
10 13
8 12
Input
Case 1:
81
on 1 2
on 0 2
none 484 535
none 474 534
off 2 2
off 2 2
off 1 2
off 0 0
off 0 0
none 464 541
on 0 2
none 473 540
on 0 1
none 463 539
none 473 548
off 1 1
on 1 3
off 2 4
off 0 0
on 1 1
off 0 2
off 0 2
on 2 2
on 0 1
on 0 0
none 476 548
off 1 3
off 0 1
on 1 3
off 0 2
on 1 2
off 1 2
on 0 0
on 1 2
none 464 544
off 0 2
none 467 557
on 0 0
off 1 3
on 0 2
none 464 542
off 0 0
off 1 1
on 0 0
on 1 3
on 0 1
none 460 554
off 0 1
none 465 560
on 2 4
on 2 3
none 462 564
none 452 563
off 1 1
on 2 4
on 1 1
off 1 2
off 2 4
on 2 4
none 452 556
none 466 565
off 0 0
off 0 0
none 465 565
on 2 4
on 0 2
on 1 3
on 1 2
off 2 4
on 2 4
off 0 0
none 466 582
off 1 3
off 1 3
none 464 570
on 2 2
on 2 2
off 0 1
on 2 4
off 2 2
none 450 587
Case 2:
100
off 2 4
on 2 3
off 1 1
off 1 1
off 2 3
on 2 2
none 468 524
off 2 3
on 1 1
off 0 2
none 467 537
on 2 4
none 461 537
on 1 3
off 1 1
off 1 2
off 1 1
off 0 0
off 2 4
none 458 536
none 453 528
off 1 2
on 1 1
on 1 2
off 1 2
none 443 527
off 0 0
none 451 529
off 0 1
off 0 2
none 443 527
on 0 0
off 0 2
off 0 2
off 0 2
off 2 4
none 438 524
off 2 3
off 0 2
off 2 2
off 0 1
on 2 3
off 1 3
none 434 529
none 420 533
off 2 4
off 1 3
on 1 1
on 2 4
none 418 533
off 1 1
on 1 3
off 0 2
on 2 4
off 0 1
off 2 4
on 0 1
none 426 544
on 0 0
on 2 4
on 0 2
off 2 4
none 419 539
off 2 4
off 2 4
none 409 539
none 417 532
none 411 538
on 0 0
on 2 2
on 0 1
on 1 3
off 2 2
on 2 3
off 0 2
none 415 545
on 0 2
none 409 537
on 0 1
none 416 549
none 402 543
off 0 1
on 1 3
on 1 1
on 2 2
on 1 1
none 406 560
off 2 2
off 0 0
on 0 2
off 0 2
on 1 3
off 2 4
on 0 1
off 2 3
none 409 549
off 0 0
off 2 3
off 1 2
none 396 548