| III Mistrzostwa Wielkopolski w Programowaniu Zespołowym | 2-3 grudnia 2005 |
|
|
W MWPZtowie dochodzi do wielkich zmian! Ministerstwo Infrastruktury postanowiło wreszcie zaopatrzyć cały kraj w sieć supernowoczesnych autostrad. Autostrady mają połączyć wszystkie miasta w kraju. Oczywiście, jako że transport ma być jak najszybszy i najbardziej bezkolizyjny, założono, że każda autostrada musi zaczynać się i kończyć w jakimś mieście, a poza miastami nie mogą istnieć żadne skrzyżowania - w razie konieczności przecięcia się dwóch autostrad zostanie wybudowany odpowiedni most lub tunel, ale nie będzie możliwości zjazdu z jednej na drugą, ani też dwie autostrady nie „zjadą się” w jedną. Oczywiście, również żadne dwie autostrady nie powinny łączyć dwóch tych samych miast, no i nie ma sensu budować autostrady z jakiegoś miasta do tego samego miasta. Ponieważ MWPZtowo nie jest krajem zbyt bogatym, budowę autostrad zaczęto od wybudowania tras wylotowych z każdego z miast. Niestety po zakończeniu tego etapu okazało się, że pieniądze przeznaczone na ten cel się skończyły i autostrad, jak nie było, tak nie ma, a trasy wylotowe bezużytecznie zalegają sobie na obrzeżach miast.
Teraz jednak zbliżają się wybory. Jak to zwykle bywa przed wyborami, znajdują się pieniądze na wiele rzeczy. Znalazły się także na dokończenie budowy sieci autostrad. Niestety... nikt nie wie, jak wybudować autostrady, aby zostały spełnione warunki, które założono przy planowaniu tych dróg, bo stare plany poginęły. Nie wiadomo nawet, czy w ogóle istnieje możliwość budowy autostrad zgodnie z założeniami, bo nikt nie ma już pewności, czy zostały wybudowane wszystkie trasy wylotowe. Postanowiono więc zebrać od lokalnych władz każdego z miast informacje o tym, ile tras wylotowych się u nich znajduje. Dane te trafiły do stolicy, a Tobie wyznaczono zadanie sprawdzenia, czy znając te liczby tras wylotowych jest sens w ogóle zabierać się do tego projektu, czyli, czy istnieje możliwość dobudowania dróg tak, aby sieć autostrad spełniała ustalone pierwotnie wymagania.
Pierwsza linia wejścia zawiera liczbę całkowitą D (1 ≤ D ≤ 50), oznaczającą liczbę zestawów danych. Każdy zestaw danych składa się z dwóch linii. W pierwszej znajduje się N - liczba miast, które są w MWPZtowie (2 ≤ N ≤ 100000), a w drugiej znajduje się N nieujemnych liczb całkowitych, oddzielonych spacjami, nie większych niż 100000, z których każda oznacza ilość tras wylotowych znajdujących się w odpowiednim mieście.
Dla każdego zestawu danych prawidłowym wyjściem powinno być słowo TAK jeśli da się utworzyć sieć autostrad, lub NIE jeśli takiej sieci utworzyć się nie da.
2 3 2 2 2 3 1 2 2
TAK NIE