레이팅 미적용농부 존의 농장 옆 고속도로의 교통량이 최근 급격히 늘어났다. 적어도 농부 존에게는 그렇게 보인다. 확실히 하기 위해, 존은 센서들을 이용해 고속도로의 교통 흐름을 측정하려 한다. 각 센서는 도로의 한 구간에서 교통 흐름의 속도를 측정할 수 있다.
안타깝게도, 어느 날 헛간을 걷다가 농부 존이 넘어지면서 센서 상자를 커다란 우유 통에 빠뜨렸고, 그 뒤로 센서들은 예전만큼 잘 작동하지 않는다. 각 센서는 이제 교통 흐름 속도의 정확한 값 하나 대신 가능한 값의 범위를 출력한다. 예를 들어, 어떤 센서는 \([7, 13]\)이라는 범위를 출력할 수 있는데, 이는 해당 도로 구간의 교통 흐름 속도가 7 이상 13 이하임을 의미한다.
고속도로는 농장 옆으로 \(N\)마일에 걸쳐 있고, 고속도로의 교통은 1마일 지점에서 \(N\)마일 지점 방향으로 한 방향으로만 흐른다. 농부 존은 고속도로의 각 1마일 구간마다 하나씩, 총 \(N\)개의 센서를 설치하려 한다. 일부 구간에는 차량이 고속도로로 진입할 수 있는 진입로가 있다. 이 경우 농부 존은 진입로에 센서를 설치하여 유입되는 교통량을 (대략적으로) 측정한다. 일부 구간에는 차량이 고속도로에서 빠져나갈 수 있는 진출로가 있다. 이 경우 농부 존은 진출로에 센서를 설치한다. 각 구간에는 진입로나 진출로가 최대 하나 있다. 어떤 구간에 진입로도 진출로도 없다면, 농부 존은 고속도로 본선에 센서를 설치한다.
농부 존의 \(N\)개 센서 판독값이 주어졌을 때, 1마일 지점 이전의 초기 교통 흐름 속도와 \(N\)마일 지점을 지나 계속 진행하는 교통 흐름 속도를 나타내는 가능한 한 구체적인 범위를 각각 구하시오. 이 범위들은 \(N\)개 센서 판독값 전부와 모순이 없어야 한다.
문제 제공: Brian Dean
문제 제공: Brian Dean
첫째 줄에 \(N\) (\(1 \leq N \leq 100\))이 주어진다. 남은 \(N\)개의 줄 각각은 1마일 지점부터 \(N\)마일 지점까지 순서대로 도로의 1마일 구간을 나타낸다. 각 줄에는 문자열이 하나 주어지는데, "on"(이 구간에 진입로가 있는 경우), "off"(진출로가 있는 경우), "none"(진입로나 진출로가 없는 경우) 중 하나이며, 그 뒤에 이 구간의 센서 범위의 하한과 상한을 나타내는 \(0 \ldots 1000\) 범위의 두 정수가 주어진다. 구간에 진입로나 진출로가 있으면 센서 판독값은 그 진입로나 진출로에서 온 것이다. 그렇지 않으면 고속도로 본선에서 온 것이다. 고속도로 구간 중 적어도 하나는 "none"으로 지정된다.
출력의 첫째 줄에는 1마일 지점 이전의 교통 흐름 속도에 대해 가능한 한 구체적인 범위를 나타내는 두 정수를 출력한다. 둘째 줄에는 \(N\)마일 지점 이후의 교통 흐름 속도에 대해 가능한 한 구체적인 범위를 나타내는 두 정수를 출력한다. 유효한 답이 항상 존재함이 보장된다.
traffic.in · 출력을 쓸 파일 traffic.out4
on 1 1
none 10 14
none 11 15
off 2 310 13
8 12In 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]\).
riseoj 작성
출처 올림피아드 > USACO > 2018-2019 > February > Bronze