Editorial for COCI '22 Contest 2 #1 Tramvaji

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Let us calculate the time it is required to go from station $1$ ~1~ to station $x$ ~x~. Let us store those values in the array $a$ ~a~. Obviously, from station $1$ ~1~ to station $1$ ~1~ we need $0$ ~0~ minutes. For any other station $x > 1$ ~x > 1~:

If the information about the station is Patrik $t_i$ ~t_i~, then $a_x = t_x$ ~a_x = t_x~
If the information about the station is Josip $y$ ~y~ $t_i$ ~t_i~, then $a_x = a_y+t_x$ ~a_x = a_y+t_x~ (the time it took from $1$ ~1~ to $y$ ~y~ plus the time it took from $y$ ~y~ to $x$ ~x~)

This will help us in finding the shortest ride. The shortest ride will always be on adjacent stations, so the indices will be $x$ ~x~ and $x+1$ ~x+1~. For some station $x$ ~x~, the time it is required to go from $x$ ~x~ to $x+1$ ~x+1~ is $a_{x+1}-a_x$ ~a_{x+1}-a_x~ (if we subtract the time it took from $1$ ~1~ to $x$ ~x~, from the time it took from $1$ ~1~ to $x+1$ ~x+1~, we will get the time it took from $x$ ~x~ to $x+1$ ~x+1~), now we just need to go through the sequence and find the $x$ ~x~ for which that time is the smallest.

Comments

There are no comments at the moment.