Metro

21.11.2011

Metro

Limit czasowy: 2000 milisekund
Limit pamięciowy: 32000 kilobajtów


W malowniczym szwajcarskim mieście Lozanna działa nowoczesne metro. Jednym z przykładów ciekawego rozwiązania inżynieryjnego jest jednotorowa, a jednak dwukierunkowa linia M1. Pociągi poruszają się w obu kierunkach po pojedynczym torze, mijając się na dwuperonowych stacjach, w których tor rozwidla się na krótką chwilę.

W zadaniu rozważamy linię metra podobną do lozańskiego M1. Rozważana linia składa się z N stacji połączonych pojedynczym torem: pierwsza stacja połączona jest z drugą, druga z pierwszą i trzecią, trzecia z drugą i czwartą, itd. Zakładamy, że odległości pomiędzy stacjami są równe i przejazd pociągu pomiędzy sąsiednimi stacjami zawsze trwa dokładnie jedną minutę.

Niektóre spośród stacji są dwuperonowe - na takiej stacji mogą bezkolizyjnie spotkać się dwa pociągi jadące w przeciwne strony. Pozostałe stacje są jednoperonowe i ew. spotkanie pociągów na takiej stacji byłoby zdarzeniem wyjątkowo niefortunnym (szczególnie dla maszynistów i pasażerów tych pociągów).

Z dwóch końców linii w przeciwnych kierunkach jednocześnie odjeżdżają dwa pociągi. Twoim zadaniem jest wyznaczenie pociągom dodatkowych postojów (dowolnej długości wyrażonej w całkowitej nieujemnej liczbie minut) na dowolnej liczbie stacji tak, aby ich spotkanie wypadło na stacji dwuperonowej (pociągi mogą jednocześnie z dwóch stron wjechać na taką stację, możliwe jest także, że jeden z pociągów będzie oczekiwał na drugi na takiej stacji).

Jaki jest minimalny czas jazdy pociągów przy którym nie dochodzi do kolizji? Przez minimalny czas jazdy rozumiemy minimalny czas po którym oba pociągi, całe, niezderzone i niewykolejone zakończą jazdę na przeciwległych końcach toru. W przypadku, w którym jeden z pociągów kończy jazdę wcześniej, wynikiem jest czas jazdy drugiego pociągu.

Wejście

W pierwszej linii znajduje się liczba naturalna Z ( 1 <= Z <= 10 ) oznaczająca liczbę zestawów testowych. Następnie opisywane są kolejne zestawy.

Opis pojedynczego zestawu testowego składa się z dwóch linii. W pierwszej linii znajduje się pojedyncza dodatnia liczba całkowita N oznaczająca liczbę stacji metra na linii (2 <= N <= 1000000). W drugiej linii znajduje się N dodatnich liczb całkowitych si oddzielonych pojedynczymi spacjami, które odpowiadają kolejnym stacjom. Każda z nich jest równa 1 lub 2 i oznacza liczbę peronów na i-tej stacji metra. Co najmniej jedna stacja będzie miała dwa perony.

Wyjście

Dla każdego zestawu testowego należy w osobnej linii wypisać minimalny czas bezkolizyjnego przejazdu pociągów. Kolejność wypisywanych odpowiedzi musi odpowiadać kolejności zestawów na wejściu.

Przykład

Wejście Wyjście
2
2
2 2
5
1 1 2 1 1
2
4
Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.

Organizatorzy:

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

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com