Tramvaji
레이팅 미적용의견: 0
One magical night Patrik and Josip were talking about the number 42 and the
meaning of life. They were interrupted by the famous lady voice in the tram: The
next stop \(is\) Jordanovac. Patrik and Josip were distracted by this common sentence
and started discussing:
Patrik: It is a very short ride between Joranovac and Maksimir, isn’t it?
Josip: It is, but the ride between Mašićeva and Kvatrić is way shorter.
Patrik: Really? I disagree.
Josip: I wonder, which is the shortest ride between all stations?
Paula, a big public traffic transport, was carefully listening to their conversation. The problem of finding
the shortest ride interested her so much that she stayed in the tram longer than she intended just to listen
to their conversation.
At each station (except for the first one, when they entered the tram) one of the following two things
happened:
• Patrik said: t minutes have passed since \(we\) entered the tram
• Josip said: From station y \(to\) this station t minutes have passed
But before Paula could hear their conclusion about which ride was the shortest, they left the tram!
Luckily, Paula remembers all their statements. Now she needs your help! Help her find the duration of
the shortest ride and between which two stations the tram drove on that ride.
Subtask 1 (12 points): \(t_{i} \le 1\,000\)
Subtask 2 (13 points): Every sentence was said by Patrik.
Subtask 3 (25 points): No additional constraints.
The first line contains the integer \(n\) (\(2 \le n \le 1\,000\)), the number of tram stations.
The \(i-th\) of the following \(n - 1\) lines contains the information about station \(i + 1\) in one of the following
formats:
• Patrik \(t@@RISE_MATH_BLOCK_0@@i\) (\(1 \le t\)\(i \le 10^{9}\))
• Josip \(y_{i}\) \(t_{i}\) – Duration of the ride between station \(y\) and station \(i + 1\) is \(t_{i}\) (\(y_{i} < i + 1\), \(1 \le t_{i} \le 10^{9}\))
Every station will be in a distinct position.
In one line output three numbers: t, x1, x2, the duration of the shortest ride and the indices of the starting
and ending stations of that ride.
If multiple solutions exist, print the one with the smallest indices of the stations.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
1 | 12점 | \(t_{i} \le 1\,000\) |
2 | 13점 | Every sentence was said by Patrik. |
3 | 25점 | No additional constraints. |
4
Patrik 3
Patrik 5
Josip 1 72 2 32
Josip 1 55 1 25
Patrik 4
Josip 2 4
Josip 2 6
Josip 4 22 3 4Clarification of the first example:
The tram drove for 3 minutes from the first to the second station, and 5 from the first to the third. We
can conclude that from the second to the third station it took 2 minutes, which is the shortest ride.
Clarification of the third example:
The ride between the fourth and fifth station is also 2 minutes but, because they have greater indices,
only the 2 3 4 solution is accepted.
평가 및 의견
Tramvaji
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Tramvaji