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.
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 to station
. Let us store those values in the array
. Obviously, from station
to station
we need
minutes. For any other station
:
- If the information about the station is Patrik
, then
- If the information about the station is Josip
, then
(the time it took from
to
plus the time it took from
to
)
This will help us in finding the shortest ride. The shortest ride will always be on adjacent stations, so the indices will be and
. For some station
, the time it is required to go from
to
is
(if we subtract the time it took from
to
, from the time it took from
to
, we will get the time it took from
to
), now we just need to go through the sequence and find the
for which that time is the smallest.
Comments