Problem description

Back
Show PDF
Poprawne klockowanie
(A)
Limit pamięci: 512 MB
Limit czasu: 1.00 s

Jasio dostał na urodziny nowy zestaw klocków. Na każdym z nich napisany jest pewien ciąg nawiasów otwierających ( lub zamykających ). Jasio zastanawia się, czy jest w stanie ułożyć wszystkie klocki w pewnej kolejności obok siebie w taki sposób, żeby powstały ciąg nawiasów był poprawny?

Poprawny ciąg nawiasowań to taki, który można uzyskać nawiasując jakieś działanie matematyczne. Przykładowo, ciąg (())() jest poprawnym nawiasowaniem, natomiast ((), ) lub )( nie są poprawnymi nawiasowaniami.

Formalnie, napis S składający się z nawiasów ( oraz ) jest poprawnym nawiasowaniem, gdy

  • S jest pusty,
  • S jest postaci (A), gdzie A jest poprawnym nawiasowaniem,
  • S jest postaci AB, gdzie A oraz B są poprawnymi nawiasowaniami.

Wejście

W pierwszym wierszu wejścia znajduje się jednak liczba naturalna N oznaczająca liczbę klocków z zestawu Jasia. W następnych N wierszach znajduje się opis napisów na każdym z klocku, i-ty wiersz zawiera ciąg nawiasów Si.

Wyjście

W pierwszym i jedynym wierszu wyjścia należy wypisać jedno słowo, TAK, jeżeli klocki da się poukładać tak, żeby utworzyły poprawne nawiasowanie, lub NIE w przeciwnym wypadku.

Ograniczenia

1 ≤ N ≤ 1 000 000, suma długości Si nie przekracza 1 000 000.

Podzadania

Podzadanie Warunki Punkty
1 Długość każdego napisu Si to dokładnie 1. 13
2 Suma długości napisów Si nie przekracza 100, N = 10 23
3 Każdy z napisów Si jest poprawnym nawiasowaniem. 9
4 Każdy z napisów Si ma tyle samo znaków ( co ). 27
5 Brak dodatkowych ograniczeń. 28

Przykład

Wejście Wyjście Wyjaśnienie 
2
)
(()

TAK

Jeżeli Jasio ustawi klocki w kolejności drugi i pierwszy, to powstanie napis (()), który jest poprawnym nawiasowaniem.
Wejście Wyjście Wyjaśnienie 
2
)()
)((

NIE

Jedyne możliwe do uzyskania napisy to )())(( oraz )(()().