Runda 14 [Hard] - Łańcuchy

07.03.2011 - Damian Rusak
TrudnośćTrudność

 

Zadanie tygodnia

runda 14; kategoria Hard

Limit czasowy: 3s; Limit pamięciowy: 64MB


 

Łańcuchy

Artur znalazł atrakcyjną posadę w spawalni łańcuchów. Jego praca jest satysfakcjonująca i pasjonująca - przydzielono go do sekcji spawania obręczy.

Każdy z łańcuchów w spawalni ma określoną długość. Obręczą nazwiemy ciąg łańcuchów $ l_{0} $, $ l_{1} $, ..., $ l_{m-1} $ o długościach $ d_{0} $, $ d_{1} $, ..., $ d_{m-1} $ $ (2 \leq m) $ jeśli można je zespawać kolejno ze sobą oraz zespawać ostatni z łańcuchów z pierwszym. Jest to możliwe, o ile (ze względów bezpieczeństwa i dla uzyskania stabilnej obręczy) dla każdej kolejnej pary łańcuchów, które zostały ze soba zespawane ich długości różnią się co do wartości bezwględnej o co najwyżej długość pierwszego z nich. Inaczej mówiąc dla $ i=0,1,...,m-2 $ mamy $ |d_{i} - d_{i+1}| \leq d_{i} $ oraz $ |d_{m-1} - d_{0}| \leq d_{m-1} $.

Artur otrzymał do zespawania cały zestaw łańcuchów. Zastanawia się, na ile sposobów może utworzyć z nich obręcze, tak aby każdy łańcuch należał do dokładnie jednej z nich. Dwa sposoby wyboru są różne wtedy i tylko wtedy, gdy można wskazać pewien łańcuch $ l $ taki ,że obręcze do których należy w pierwszym i w drugim sposobie wyboru nie są tymi samymi ciągami łańcuchów (z dokładnością do przesunięcia cyklicznego - $ l_{0} l_{1} l_{2} $ to ta sama obręcz co $ l_{2} l_{0} l_{1} $). Artur poprosił Cię o pomoc. Aby ułatwić Ci zadanie dodał, że interesuje go tylko reszta z dzielenia tej liczby przez $ 2 $.

Wejście:

Pierwsza linia wejścia zawiera jedną liczbę całkowitą $ t $ - liczbę zestawów danych $ (1 \leq t \leq 10) $. Po niej następują opisy kolejnych zestawów danych. Każdy z nich składa się z dwóch linii - pierwsza zawiera liczbę całkowitą $ n $ - liczbę łańcuchów $ (1 \leq n \leq 100) $. W kolejnej linii znajduje się $ n $ liczb całkowitych $ d_{0} $, $ d_{1} $, ... , $ d_{n-1} $ - są to długości łańcuchów. $ (1 \leq d_{i} \leq 10^{8}) $.

Wyjście:

Dla każdego zestawu danych należy w jednej linii wypisać resztę z dzielenia przez $ 2 $ liczby wszystkich doborów łańcuchów do stworzenia zbioru obręczy.

Przykład:

Wejście:

2
2
10 18
5
100 200 3 3 3

Wyjście:

1
0

Wyjaśnienie: W pierwszym przypadku możemy stworzyć jedynie obręcz z łańcuchów o długościach $ 10 $ i $ 18 $ (spełniają warunek, że $ |10 - 18| = 8 \leq 10 $  i  $ |18 - 10| = 8 \leq 18 $). W drugim przypadku łańcuchy o długościach $ 100 $ oraz $ 200 $ muszą zostać połaczone ze sobą, za to łańcuchy o długości $ 3 $ można na dwa sposoby połączyć w obręcz (pierwszy-drugi-trzeci lub pierwszy-trzeci-drugi).

Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.
PozycjaImię i nazwiskoWynikCzasŁańcuchy
1Damian Straszak1003:48:1310
2Piotr Bejda1073:54:5610
3Wojtek Nadara10178:52:2010
4Witold Długosz10561:12:1210
5Bartosz Tarnawski10582:22:2310
5
Twoja ocena: Brak Ocena: 5 (1 ocena)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com