Metro (omówienie)

14.12.2011

Kluczem do rozwiązania zadania była dość banalna obserwacja, że rozważane pociągi muszą się gdzieś minąć.

Załóżmy na chwilę, że wiemy, że pociągi mają minąć się na x-tej stacji. Jak w tej sytuacji obliczyć poszukiwany czas przejazdu pociągów?

  • Pociąg wyruszający ze stacji 1 przyjedzie na stację po $ X-1 $ minutach
  • Pociąg wyruszający ze stacji N przyjedzie na stację po $ N-X $ minutach

W takim razie oba pociągi będą na x-tej stacji (gotowe do odjazdu - jeśli tylko stacja była dwuperonowa...) po $ max(X-1,N-X) $ minutach.

Jak widać, wynik dla pojedynczej stacji można wyliczyć w czasie stałym, więc wystarczyło sprawdzić wszystkie możliwe stacje x, pamiętając aby brać pod uwagę tylko stacje dwuperonowe.

Organizatorzy:

Wrocławski Portal Informatyczny Instytut Informatyki Uniwersytet Wrocławski Wrocław

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com