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.