Runda 12 [Basic] - Pociągi

21.02.2011 - Damian Rusak
Trudność

 

Zadanie tygodnia

runda 12; kategoria Basic

Limit czasowy: 1s; Limit pamięciowy: 32MB


 

Pociągi

Na stacji kolejowej wielkie zamieszanie i chaos - okazało się, że wszystkie pociągi przyjechały na czas. Pojawił się palący problem - jak ulokować wagony na peronach nieprzystosowanych do obsługi rozkładu na czas? Inspektorzy nadzoru krążą wszędzie dookoła i pewnym jest, że dokładnie obserwują, czy wagony są ustawione w estetyczny sposób. Każdy wagon ma pewien ściany w pewnym kolorze. Aby ciąg wagonów można było nazwać estetycznym musi się on składać z parzystej liczby wagonów i do tego pierwszy wagon musi być w tym samym kolorze co ostatni, drugi w tym samym kolorze co przedostatni itd.

Innymi słowy jeśli wagonów ma być $ 2n $ a kolory kolejnych wagonów to $ w_{0} $, $ w_{1} $,...,$ w_{2n-2} $, $ w_{2n-1} $ to musi być $ w_{0} = w_{2n-1} $, $ w_{1} = w_{2n-2} $,...,$ w_{n-1} = w_{n} $.

Podczas przedłużającego się oczekiwania na dworcu zainteresowało Cię ile różnych ciągów kolorów wagonów pracownicy kolei mogą uzyskać, tak aby wagony ustawione były w estetyczny sposób.

Wejście:

Pierwsza linia wejścia zawiera jedną liczbę całkowitą $ n $ - połowę liczby wagonów ($ 1 \leq n \leq 20 $). W kolejnej linii znajduje się $ 2n $ liczb całkowitych $ w_{0}, w_{1}, ... , w_{2n-1} $. ($ 0\leq w_{i} \leq 10 $) - kolory kolejnych wagonów.

Wyjście:

Wyjście powinno zawierać jedną liczbę całkowitą - liczbę różnych ciągów kolorów wagonów ustawionych w estetyczny sposób. Masz gwarancję, że wynik będzie nie większy niż $ 2^{60} $.

Przykład:

Wejście:

2
0 0 0 0 

Wyjście:

1

jedyny estetyczny ciąg to 0000

 

Wejście:

2
0 2 0 2

Wyjście:

2

Dwa możliwe do ustawienia ciągi są ustawione w estetyczny sposób: 0220 i 2002

 

 

Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.
PozycjaImię i nazwiskoWynikCzasPociągi
1Marcin Karpinski1000:26:4810
2Arek Wróbel1000:58:2410
3Kamil Dębowski1003:28:3810
4Jakub Gąsiewski1004:05:4710
5Przemysław Derengowski1012:06:0210
6Krzysztof Drab1012:25:5010
7Przemek Komosa1012:44:1210
8Andrzej Rumiński1014:53:1110
9Wojciech Szałapski1016:43:0310
10Mateusz Wasylkiewicz1031:11:1310
11Damian Straszak1078:16:2810
12Jakub Kołodziej10154:00:2110
13Łukasz Hryniuk10157:29:2110
14Piotr Bejda10158:44:2110
15Witold Długosz10217:27:2110
16Tomasz Jan Drab7178:42:037
17Przemysław Wawrzyniak5162:58:295
18Krzysztof Cirocki1155:40:511
4
Twoja ocena: Brak Ocena: 4 (1 ocena)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com