Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

AL_13_07 - DOMINO

"Domino to gra dla dwóch osób.

W grze wykorzystuje się kamienie(domina), które mają kształt prostokątów, na których obydwu końcach znajduje się pewna liczba oczek od 0 do 6. W zestawie do gry występują klocki z każdą kombinacją oczek i każda kombinacja występuje dokładnie jeden raz" - taka jest definicja gry domino.

Bitek i jego wuj Bajtosław w wolnych chwilach grywają w tą wspaniałą grę, jednak ile można grać ciągle w to samo. Warcaby klasyczne też już dawno się znudziły. Nagle młody gracz wpadł na genialny pomysł i powiedział: "Zmieńmy zasady gry DOMINO!". Wuj chętnie wysłuchał pomysłu Bitka i dodał kilka swoich sugestii, co w rezultacie zaowocowało taką grą:

Układamy losowo wszystkie dostępne kamienie w jeden długi ciąg, w którym klocki nie muszą być poprawnie ułożone (nie musi się zgadzać liczba oczek w dwóch sąsiadujących kamieniach). Gra polega na tym, że gracze wykonują ruchy na przemian obracając wybrany kamień, który jest nieprawidłowo dopasowany w ten sposób, aby liczba oczek dla jednej płytki z lewej i prawej strony się zgadzała. Klocków domina nie można przestawiać miejscami. Dodatkowo, liczba kamieni domina jest znacznie większa, niż w standardowej grze oraz mogą one się powtarzać. Nie zmienia się natomiast liczba dopuszczalnych oczek. Przegrywa osoba, która nie będzie mogła wykonać ruchu.

Twoje zadanie jest następujące: dla ustalonego ciągu klocków określ maksymalny spójny podciąg, który będzie można utworzyć obracając kamienie domina tak, że będzie on tworzył poprawny podciąg gry DOMINO.

Wejście

W pierwszym wierszu jedna liczba n określająca ilość kości domina (1 ≤ ≤ 2⋅106).

W następnym wierszu n kości domina. Każda kość jest w formacie: [oczka1]|[oczka2], gdzie oczka1 i oczka2 oznaczają ilość oczek po jednej i drugiej stronie domina np.:

zapis 4|5 oznacza kość

domino

Wyjście

Jedna liczba określająca długość najdłuższego spójnego podciągu, który spełnia zasady gry DOMINO.

Przykład 1

Wejście:
8
2|2 3|5 1|1 1|6 5|6 6|4 2|4 4|0

Wyjście:
3

Przykład 2

Wejście:
4
6|6 6|2 6|2 6|1

Wyjście:
4

Wyjaśnienie:

W pierwszym przykładzie przekręcamy kamień piąty i uzyskujemy podciąg:

1|1 1|6 6|5

lub kamień siódmy i mamy podciąg:

5|6 6|4 4|2

W drugim przykładzie obracając trzeci kamień uzyskujemy ciąg o długości 4.


Dodane przez:Marcin Kasprowicz
Data dodania:2013-11-16
Limit czasu wykonania programu:1s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM64 GOSU

ukryj komentarze
2013-12-22 18:29:49 Tomasz Gandor
A może niekoniecznie... Mam co innego żle oprócz tego.
2013-12-22 18:24:46 Tomasz Gandor
Czy haczyk jest w tym, że:
in:
2
1|2 3|1
out:
1
(bo nie można obrócić ani 1. ani 2., żeby chwilowo się "zgadzało")?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.