Zadania do wyboru

Po wyborze jednego zadania należy opracować algorytm, oszacować jego złożoność oraz zaimplementować poprawny program. Należy dokładnie przetestować program!!!

Wybrane zadanie można realizować maksymalnie w dwu osobowych grupach projektowych.

W jednej grupie dziekańskiej nie może powtarzać się dwukrotnie to samo zadanie.

Lista zadan

Zadanie 1

Bajtazar postanowił zająć się produkcją naszyjnikow. Udało mu się okazyjnie kupić bardzo długi sznur rożnokolorowych korali. Dysponuje on maszyną, ktora dla zadanego k (k > 0) potrafi pociąć sznur na odcinki składające się z k korali (czyli pierwszy odcinek składa się z korali o numerach 1, . . . , k, drugi k + 1, . . . , 2k, itd.). Jeśli sznur korali ma długość, ktora nie jest wielokrotnością k, to ostatni odcinek, ktory ma długość mniejszą niż k, jako niepełnowartościowy, nie jest wykorzystywany. Kolory korali oznaczamy dalej dodatnimi liczbami całkowitymi.

Bajtazar lubi rożnorodność i zastanawia się, jak dobrać liczbę k, tak by otrzymać jak najwięcej rożnych

sznurow korali. Sznur korali, ktory ma zostać pocięty, ma wyraźnie określony koniec, od ktorego zaczynamy odcinać krotsze sznury. Jednak każdy odcięty sznur może zostać obrocony — inaczej mowiąc, sznury (1, 2, 3) i (3, 2, 1) są dla Bajtazara takie same. Napisz program, ktory pomoże mu wyznaczyć optymalną wartość parametru k.

Przykładowo, dla sznura korali postaci:

(1, 1, 1, 2, 2, 2, 3, 3, 3, 1, 2, 3, 3, 1, 2, 2, 1, 3, 3, 2, 1),

• stosując k = 1, możemy otrzymać 3 rożne sznury korali: (1), (2), (3),

• stosując k = 2, możemy otrzymać 6 rożnych sznurow korali: (1, 1), (1, 2), (2, 2), (3, 3), (3, 1), (2, 3),

• stosując k = 3, możemy otrzymać 5 rożnych sznurow korali: (1, 1, 1), (2, 2, 2), (3, 3, 3), (1, 2, 3), (3, 1, 2),

• stosując k = 4, możemy otrzymać 5 rożnych sznurow korali: (1, 1, 1, 2), (2, 2, 3, 3), (3, 1, 2, 3), (3, 1, 2, 2), (1, 3, 3, 2),

• dla większych wartości k możemy uzyskać co najwyżej 3 rożne sznury korali.

Wejście

W pierwszym wierszu standardowego wejścia znajduje się liczba całkowita n (1 ¬ n ¬ 200 000), oznaczająca długość sznura korali. W drugim wierszu znajduje się n dodatnich liczb całkowitych ai (1 ¬ ai ¬ n), pooddzielanych pojedynczymi odstępami i oznaczających kolory kolejnych korali w sznurze Bajtazara.

Wyjście

W pierwszym wierszu standardowego wyjścia należy wypisać dwie liczby całkowite oddzielone pojedynczym odstępem: liczbę rożnych sznurow korali, ktore można uzyskać przy optymalnym wyborze parametru k, oraz liczbę l rożnych wyborow parametru k prowadzących do uzyskania takiej liczby sznurow. Drugi wiersz powinien zawierać l liczb pooddzielanych pojedynczymi odstępami: wartości parametru k, dla ktorych uzyskujemy optymalne rozwiązanie — mogą one zostać wypisane w dowolnej kolejności.

Przykład

Dla danych wejściowych:

21

1 1 1 2 2 2 3 3 3 1 2 3 3 1 2 2 1 3 3 2 1

poprawnym wynikiem jest:

6 1

2

Zadanie 2

Poszukiwacze skarbów zdobyli mapę zamku, w którego podziemiach znajduje się olbrzymi skarb. Mapa jest naniesiona na siatkę kwadratową, której węzły mają współrzędne całkowite. Lewy dolny róg (węzeł) siatki ma współrzędne (0,0), a przeciwległy, prawy górny róg - współrzędne (10000, 10000). Na mapie zamek ma kształt wielokąta, którego boki leżą na liniach siatki. Kolejne dwa boki wielokąta są zawsze prostopadłe. Brzeg tego wielokąta jest łamaną zamkniętą zwykłą, tzn. każdy jej wierzchołek należy do dokładnie dwóch odcinków łamanej, a każdy inny punkt - do jednego. Odcinki linii tworzących siatkę zawarte w wielokącie, w tym także każdy bok wielokąta, przedstawiają odcinki podziemnych korytarzy zamku. W jednym z węzłów (tzn. na przecięciu linii siatki), należącym do wielokąta zaznaczony jest punkt wejścia do podziemi, a w innym węźle również należącym do wielokąta - punkt, w którym ukryty jest skarb.

Chcemy obliczyć długość najkrótszej drogi podziemnymi korytarzami zamku od punktu wejścia do podziemi do punktu, w którym ukryty jest skarb. Przyjmujemy, że jednostką długości jest długość boku pojedynczej kratki na siatce.

Zadanie

Napisz program, który:

• wczytuje z pliku tekstowego ZAM.IN następujące dane o zamku:

• liczbę wierzchołków n wielokąta przedstawiającego zamek, 4 <= n <= 5000,

• współrzędne wierzchołków w kolejności ich występowania przy obchodzeniu wielokąta,

• współrzędne punktu wejścia do podziemi i punktu, w którym ukryty jest skarb;

• znajduje długość najkrótszej drogi podziemnymi korytarzami zamku (po liniach siatki), od punktu wejścia do podziemi do punktu, w którym znajduje się skarb;

• zapisuje wynik w pliku tekstowym ZAM.OUT.

Wejście

W pierwszym wierszu pliku tekstowego ZAM.IN jest zapisana jedna liczba całkowita n z zakresu [4..5000] - jest to liczba wierzchołków wielokąta przedstawiającego zamek.

W każdym z kolejnych n wierszy są zapisane dwie liczby całkowite z zakresu [0..10000] oddzielone pojedynczym odstępem - są to współrzędne kolejnego wierzchołka wielokąta.

Następnie, w przedostatnim wierszu pliku są zapisane w takim samym formacie współrzędne punktu wejścia do podziemi, a w ostatnim wierszu współrzędne punktu położenia skarbu.

Wyjście

W pierwszym i jedynym wierszu pliku tekstowego ZAM.OUT należy zapisać jedną liczbę całkowitą - długość najkrótszej drogi od punktu wejścia do podziemi do punktu w którym ukryty jest skarb.

Przykład

Opisem zamku przedstawionego na rysunku jest następujący plik tekstowy ZAM.IN

10

9 6

9 2

12 2

12 9

2 9

2 1

8 1

8 3

4 3

4 6

11 5

3 1

Poprawnym rozwiązaniem jest w tym przypadku następujący plik ZAM.OUT:

14

Twój program powinien szukać pliku ZAM.IN w katalogu bieżącym i tworzyć plik ZAM.OUT również w bieżącym katalogu. Plik zawierający napisany przez Ciebie program w postaci źródłowej powinien mieć nazwę ZAM.???, gdzie zamiast ??? należy wpisać co najwyżej trzyliterowy skrót nazwy użytego języka programowania. Ten sam program w postaci wykonalnej powinien być zapisany w pliku ZAM.EXE.

Zadanie 3

W czasach Ludwika XIII i jego potężnego ministra, kardynała Richelieu, w gospodzie pod Pełnym Antałkiem raczyło się jadłem i winem n muszkieterów. Wina było pod dostatkiem, a że muszkieterowie byli skorzy do zwady, doszło do wielkiej awantury, w której każdy muszkieter obraził wszystkich pozostałych.

Musiało dojść do pojedynków, ale kto miał się z kim pojedynkować i w jakiej kolejności? Uzgodnili (po raz pierwszy od awantury zrobili coś zgodnie), że staną na okręgu w ustalonej kolejności i będą ciągnąć losy. Wylosowany muszkieter toczył pojedynek ze swoim sąsiadem z prawej. Przegrany "odpadał z gry", a dokładniej - służący wynosili jego zwłoki. Sąsiadem wygrywającego stawał się następny muszkieter, stojący za przegranym.

Po latach, gdy historycy czytali wspomnienia zwycięzcy, spostrzegli, że ostateczny wynik zależał w istotny sposób od kolejności wylosowanych pojedynków. Zauważyli bowiem, że dotychczasowe treningi fechtunku pokazywały, kto z kim mógł wygrać pojedynek. Okazało się, że - mówiąc językiem matematycznym - relacja "A wygrywa z B" nie była przechodnia! Mogło się zdarzyć, że muszkieter A walczył lepiej od muszkietera B, B lepiej od C, a C lepiej od A. Oczywiście wśród takiej trójki wybór pierwszego pojedynku decydował o ostatecznym wyniku! Jeśli pierwsi będą walczyć A i B, to ostatecznie wygra C, ale jeśli pierwszymi będą B i C, to ostatecznie wygra A. Historycy, zafascynowani tym odkryciem, postanowili sprawdzić, którzy muszkieterowie mogli przeżyć - od tego zależał przecież los Francji, a wraz z jej losem, los całej cywilizowanej Europy!

Zadanie

Na okręgu stoi n osób, ponumerowanych kolejno liczbami od 1 do n. Osoby te toczą n-1 pojedynków. W pierwszej rundzie jedna z tych osób powiedzmy o numerze i - toczy pojedynek z sąsiadem z prawej, tzn. osobą o numerze i+1 (lub, jeśli i=n, to z osobą o numerze 1). Przegrany odpada z gry, sąsiadem zwycięzcy staje się następna w kolejności osoba. Dana jest też tabela możliwych wyników pojedynków w postaci macierzy A. Jeśli A_i,j=1, to osoba o numerze i zawsze wygrywa z osobą o numerze j. Jeżeli A_i,j=0, to osoba o numerze i przegrywa z osobą o numerze j. Mówimy, że osoba k może wygrać zawody, jeżeli istnieje taki ciąg n-1 losowań, w wyniku którego będzie ona zwycięzcą ostatniego pojedynku.
Napisz program, który:

• wczyta z pliku tekstowego MUS.IN macierz A

• wyznaczy numery osób, które mogą wygrać zawody,

• zapisze je do pliku tekstowego MUS.OUT.

Wejście

W pierwszym wierszu pliku testowego MUS.IN dana jest liczba całkowita n spełniająca nierówność 3 <= n <= 100. W każdym z następnych n wierszy znajduje się jedno słowo złożone z n znaków 0 lub 1. Znak stojący na j-tym miejscu w i-tym z tych wierszy oznacza wartość A_i,j (tzn. jeśli tym znakiem jest jedynka, to A_i,j=1, a jeśli zero, to A_i,j=0). Oczywiście A_i,j=1-A_j,i, dla i<>j. Przyjmujemy, że A_i,i=1, dla każdego i.

Wyjście

W pierwszym wierszu pliku wyjściowego MUS.OUT należy zapisać liczbę m tych osób, które mogą wygrać zawody. W następnych m wierszach należy zapisać numery tych osób w kolejności rosnącej, po jednym numerze w wierszu.

Przykład

Dla pliku wejściowego MUS.IN

7

1111101

0101100

0111111

0001101

0000101

1101111

0100001

kolejność pojedynków: 1-2, 1-3, 5-6, 7-1, 4-6, 6-1 daje ostateczną wygraną osobie o numerze 6. Można też sprawdzić, że jeszcze tylko osoby o numerach 1 i 3 mogą wygrać zawody. Zatem plik wyjściowy MUS.OUT powinien wyglądać następująco:

3

1

3

6

Twój program powinien szukać pliku MUS.IN w katalogu bieżącym i tworzyć plik MUS.OUT również w bieżącym katalogu. Plik zawierający napisany przez Ciebie program w postaci źródłowej powinien mieć nazwę MUS.???, gdzie zamiast ??? należy wpisać co najwyżej trzyliterowy skrót nazwy użytego języka programowania. Ten sam program w postaci wykonywalnej powinien być zapisany w pliku MUS.EXE

Zadanie 4

Gra w zielone jest grą dla dwóch graczy - nazwijmy ich Ania i Bolek - polegającą na przesuwania pionka po planszy.

Część pól planszy jest pokolorowana na zielono, a pozostałe są białe. Wszystkie pola są ponumerowane liczbami naturalnymi z zakresu 1...(a+b). Pola o numerach z zakresu 1...a należą do Ani, natomiast pola o numerach (a+1)...(a+b) należą do Bolka.

Dla każdego pola dany jest zbiór następników, zawierający te pola planszy, do których można z niego przejść w jednym ruchu. Zbiory te zostały tak dobrane, że z pola należącego do Ani można przejść w jednym ruchu tylko na pole należące do Bolka i odwrotnie. Wszystkie pola mają niepuste zbiory następników, a więc zawsze można wykonać ruch.

Na początku gry ustawiamy pionek na dowolnym polu początkowym P, a następnie gracze na przemian przestawiają pionek ze swojego pola na dowolny następnik tego pola - należący do przeciwnika. Grę rozpoczyna właściciel pola początkowego P. Gra kończy się w momencie, gdy pionek stanie po raz drugi na tym samym polu. Nazwijmy to pole Q. Jeśli w sekwencji ruchów od pierwszego zajęcia pola Q do powtórnego zajęcia pola Q pionek stanął przynajmniej raz na polu zielonym, to wygrywa Ania, w przeciwnym przypadku wygrywa Bolek. Powiemy, że Ania ma strategię wygrywającą dla danego pola początkowego P, jeśli istnieje metoda gwarantująca jej wygraną w rozgrywce zaczynającej się od tego pola, niezależnie od tego, jakie ruchy będzie wykonywał Bolek.

Zadanie

Napisz program, który:

• wczyta z pliku tekstowego GRA.IN opis planszy do gry w zielone,

• znajdzie zbiór pól planszy, dla których Ania ma strategię wygrywającą,

• zapisze wynik w pliku tekstowym GRA.OUT.

Wejście

W pierwszym wierszu pliku tekstowego GRA.IN zapisane są dwie dodatnie liczby całkowite a, b oddzielone pojedynczym odstępem, oznaczające odpowiednio: liczbę pól należących do Ani i liczbę pól należących do Bolka. Liczby a, b spełniają warunek: 1 <= a+b <= 3000. W kolejnych a+b wierszach opisano pola planszy - najpierw pola należące do Ani, a następnie pola należące do Bolka. Wiersz o numerze i+1, dla 1 <= i <= a+b, zawiera na początku liczby całkowite z, k oddzielone pojedynczym odstępem, oznaczające odpowiednio kolor pola o numerze i (0 oznacza kolor biały, 1 - kolor zielony), oraz liczbę następników tego pola. Następnie w tym wierszu zapisane jest k liczb całkowitych (1 <= k < a+b), pooddzielanych pojedynczymi odstępami, będącymi numerami następników danego pola. Liczba pól zielonych na planszy nie przekracza 100. Suma liczb następników wszystkich pól na planszy nie przekracza 30000.

Wyjście

Pierwszy wiersz pliku tekstowego GRA.OUT powinien zawierać dokładnie jedną liczbę całkowitą l, oznaczającą liczbę pól, dla których Ania ma strategię wygrywającą. Następne l wierszy powinno zawierać numery tych pól zapisane w kolejności rosnącej - każda liczba powinna zostać zapisana w osobnym wierszu.

Przykład

Dla pliku wejściowego GRA.IN:

5 3

0 2 6 7

0 3 6 7 8

0 1 8

1 1 7

1 1 8

1 2 1 2

0 2 1 2

0 2 3 4

poprawną odpowiedzią jest plik wyjściowy GRA.OUT:

5

1

2

4

6

7

Zadanie 5

Mamy daną dwuwymiarową bitmapę A[1..N,1..N], której pola są równe 0 lub 1. Należy znaleźć podprostokąt tej bitmapy o największym polu, taki że wszystkie jego pola będą równe 0.

Dane: 1 ≤ N ≤ 100; 1 ≤ i, j ≤ N; A[i,j] ∈ {0,1}
Wejście: N A[1,1] A[1,2] ... A[1,N] A[2,1] ... A[2,N] ..... A[N,1] ... A[N,N] {3 1 0 1 0 0 0 1 0 0}
Wyjście: maksymalne_pole

Zadanie 6

Zgodnie z regułami gry w szachy, hetman (królowa) może atakowac figury ustawione na polach w kolumnie, wierszu oraz dwóch przekatnych przechodzacych przez pole, w którym jest ustawiony. O tych polach mówimy, że sa atakowane przez hetmana.

Na rysunku

hetman stoi w polu (2,6) i atakuje (7+7+6+3) = 23 pola.

Zostały one zamalowane kolorem szarym.

a) Poniżej znajduje sie tabela o wymiarach 5x5. Korzystajac z powyższej obserwacji, uzupełnij pola tabeli wpisujac do każdego z nich liczbe pól, które atakowałby hetman znajdujacy sie w tym polu.

Hetman stojacy w polu (1,1) atakuje 12 pól planszy.

1 2 3 4 5

1

2

3

4

5 12

b) Okresl liczbe atakowanych pól na szachownicy 32x32, gdy dane sa współrzedne

ustawienia hetmana.

Dla (2,2) wynik = ...................................................................................................

Dla (5,4) wynik = ...................................................................................................

Dla (20,18) wynik = ...............................................................................................

Dla (25,30) wynik = ...............................................................................................

Podaj specyfikacje i utwórz algorytm, który dla dowolnej dodatniej liczby całkowitej n _ 50 i położenia

hetmana (x, y) na szachownicy o wymiarach n×n , gdzie 1_x,y_n, pozwoli obliczyc liczbe pól atakowanych

przez tego hetmana.

Zadanie 7

Na nieskończonej szachownicy znajduje się superskoczek, który może wykonywać różnego rodzaju ruchy. Każdy rodzaj ruchu jest określony za pomocą dwóch liczb całkowitych - pierwsza mówi o ile kolumn (w prawo w przypadku liczby dodatniej lub w lewo w przypadku liczby ujemnej), a druga o ile wierszy (do przodu w przypadku liczby dodatniej lub do tyłu w przypadku liczby ujemnej) przesuwa się skoczek wykonując taki ruch.

Zadanie

Napisz program, który:

• wczyta z pliku tekstowego sup.in zestawy danych opisujące różne superskoczki,

• dla każdego superskoczka stwierdzi, czy za pomocą swoich ruchów może dotrzeć do każdego pola na planszy,

• zapisze wynik do pliku tekstowego sup.out .

Wejście

W pierwszym wierszu pliku tekstowego sup.in znajduje się jedna liczba całkowita k określająca liczbę zestawów danych, 1<=k<=100. Po niej następuje k zestawów danych. W pierwszym wierszu każdego z nich pojawia się liczba całkowita n będąca liczbą rodzajów ruchów, które może wykonywać superskoczek, 1<=n<=100. Każdy z kolejnych n wierszy zestawu danych zawiera dwie liczby całkowite p i q oddzielone pojedynczym odstępem, opisujące ruch, -100<=p, q<=100.

Wyjście

Plik tekstowy sup.out powinien składać się z k wierszy. Wiersz i-ty powinien zawierać jedno słowo TAK, jeśli superskoczek opisany w i-tym zestawie danych może dotrzeć do każdego pola na planszy, a słowo NIE w przeciwnym przypadku.

Przykład

Dla pliku wejściowego sup.in:

2

3

1 0

0 1

-2 -1

5

3 4

-3 -6

2 -2

5 6

-1 4

poprawną odpowiedzią jest plik wyjściowy sup.out :

TAK

NIE

Zadanie 8

U stóp Bajtogóry znajduje się wejście do jaskini. Jaskinia to system komnat połączonych korytarzami. Wejście do jaskini prowadzi bezpośrednio do komnaty nazywanej wejściową. Korytarze nie przecinają się (spotykają się jedynie w komnatach). Dwie komnaty mogą być albo połączone jednym korytarzem, albo mogą nie być połączone wcale (być może można jednak wtedy przejść z jednej do drugiej przechodząc po drodze przez inne komnaty). Korytarz łączy zawsze dwie różne komnaty.

Postanowiono zorganizować zawody o puchar króla Bajtocji. Celem każdego z zawodników jest przebycie dowolnie wybranej trasy w jaskini i wyjście na zewnątrz w jak najkrótszym czasie. Trasa musi przechodzić przez co najmniej jedną komnatę inną niż wejściowa. Obowiązują tylko dwie zasady: podczas wędrówki po jaskini, każdą komnatę można odwiedzić co najwyżej raz (z wyjątkiem komnaty wejściowej), podobnie tylko raz można przejść każdym z korytarzy.

Do zawodów przygotowuje się słynny grotołaz Bajtała. Bajtała długo trenował w jaskini i dokładnie poznał sieć korytarzy. Dla każdego z korytarzy wyznaczył czasy potrzebne do jego przejścia w każdą stronę. Czas potrzebny do poruszania się po komnatach można zaniedbać. Bajtała chciałby teraz wyznaczyć taką trasę spełniającą wymogi zawodów, którą można przebyć w jak najkrótszym czasie (czas potrzebny do przebycia trasy jest sumą czasów potrzebnych do przejścia korytarzy składających się na trasę).

Zadanie

Pomóż Bajtale! Napisz program, który:

• wczyta ze standardowego wejścia opis jaskini oraz czasy potrzebne do przejścia poszczególnych korytarzy,

• obliczy trasę zgodną z zasadami zawodów, dla której suma czasów przejść korytarzy składających się na trasę jest najmniejsza,

• wypisze na standardowe wyjście czas potrzebny do przejścia wyznaczonej trasy.

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby całkowite n i m oddzielone pojedynczym odstępem, oznaczające odpowiednio liczbę komnat w jaskini, oraz liczbę łączących je korytarzy, 3 <= n <= 5000, 3 <= m <= 10000. Komnaty są ponumerowane od 1 do n. Komnata wejściowa ma numer 1. W kolejnych m wierszach opisane są poszczególne korytarze. W każdym z tych wierszy znajduje się czwórka liczb naturalnych oddzielonych pojedynczymi odstępami. Czwórka a, b, c, d oznacza, że jaskinie a i b są połączone korytarzem, czas przejścia z jaskini a do b wynosi c, a z b do a wynosi d, 1 <= a,b <= n, a <> b, 1 <= c,d <= 10000. Możesz założyć, że zawsze istnieje przynajmniej jedna trasa spełniająca wymogi zawodów.

Wyjście

Twój program powinien wypisać w pierwszym i jedynym wierszu wyjścia jedną liczbę całkowitą - minimalny czas potrzebny do przebycia trasy spełniającej warunki zawodów.

Przykład

Dla danych wejściowych:

3 3

1 2 4 3

2 3 4 2

1 3 1 1

poprawnym wynikiem jest:

6

Zadanie 9

Dana jest tabliczka czekolady złożona z m*n cząstek. Czekoladę należy połamać na pojedyncze cząstki. Kawałki czekolady możemy łamać wzdłuż pionowych i poziomych linii (zaznaczonych na rysunku liniami przerywanymi) wyznaczających podział czekolady na cząstki. Jedno przełamanie kawałka czekolady wzdłuż wybranej pionowej lub poziomej linii dzieli ten kawałek na dwa mniejsze. Każde przełamanie kawałka czekolady jest obarczone pewnym kosztem wyrażającym się dodatnią liczbą całkowitą. Koszt ten nie zależy od wielkości łamanego kawałka, a jedynie od linii wzdłuż której łamiemy. Oznaczmy koszty łamania wzdłuż kolejnych pionowych linii przez x₁, x₂, ..., x_m-1, a wzdłuż poziomych linii przez y₁, y₂, ..., y_n-1. Koszt połamania całej tabliczki na pojedyncze cząstki to suma kosztów kolejnych przełamań. Należy obliczyć minimalny koszt połamania całej tabliczki na pojedyncze cząstki.

Przykładowo, jeżeli połamiemy czekoladę przedstawioną na rysunku, najpierw wzdłuż linii poziomych, a następnie każdy z otrzymanych kawałków wzdłuż linii pionowych, to koszt takiego połamania wyniesie y₁+y₂+y₃+4*(x₁+x₂+x₃+x₄+x₅).

Zadanie

Napisz program, który:

• wczyta liczby x₁, x₂, ..., x_m-1 i y₁, y₂, ..., y_n-1,

• obliczy minimalny koszt połamania całej tabliczki na pojedyncze cząstki,

• wypisze wynik.

Wejście

W pierwszym wierszu standardowego wejścia zapisane są dwie dodatnie liczby całkowite m i n oddzielone pojedynczym odstępem, 2 <= m,n <= 1000. W kolejnych m-1 wierszach zapisane są liczby x₁, x₂, ..., x_m-1, po jednej w wierszu, 1 <= x_i <= 1000. W kolejnych n-1 wierszach zapisane są liczby y₁, y₂, ..., y_n-1, po jednej w wierszu, 1 <= y_i <= 1000.

Wyjście

Twój program powinien pisać na standardowe wyjście. W pierwszym i jedynym wierszu Twój program powinien wypisać jedną liczbę całkowitą - minimalny koszt połamania całej tabliczki na pojedyncze cząstki.

Przykład

Dla danych wejściowych:

6 4

2

1

3

1

4

4

1

2

poprawnym wynikiem jest:

42

Zadanie 10

Jedno z zadań w bajtockim teście na inteligencje polega na wykreślaniu liczb z zadanego początkowego ciągu

tak, aby otrzymywać w ten sposób różne inne zadane sekwencje. Bajtazar chciałby zostać bajtockim mistrzem

IQ, ale wyjatkowo kiepsko radzi sobie z zadaniami tego typu. Zamierza dużo ćwiczyć i poprosił Cie o napisanie

programu, który pomoże mu szybko sprawdzać odpowiedzi.

Wejscie

Pierwszy wiersz standardowego wejścia zawiera jedna liczbe całkowita m (1 ¬ m ¬ 1 000 000). Drugi wiersz zawiera ciag m liczb całkowitych a1, a2, . . . , am (1 ¬ ai ¬ 1 000 000 dla 1 ¬ i ¬ m) pooddzielanych pojedynczymi odstepami, tworzących początkowy ciąg w zadaniu z testu. Trzeci wiersz wejscia zawiera jedna dodatnia liczbe całkowita n. Kolejne 2n wierszy zawiera opisy ciagów, które maja powstać w wyniku wykreślania różnych liczb z początkowego ciagu. Opis każdego z tych ciągów zajmuje po dwa kolejne wiersze. W pierwszym wierszu każdego opisu znajduje sie liczba całkowita mi (1 ¬ mi ¬ 1 000 000). Drugi wiersz zawiera mi-elementowy ciag liczb całkowitych bi,1, bi,2, . . . , bi,mi (1 ¬ bi,j ¬ 1 000 000 dla 1 ¬ j ¬ mi) pooddzielanych pojedynczymi odstepami. Możesz założyć, ze suma długości podanych n sekwencji nie przekroczy 1 000 000.

Wyjscie

Twój program powinien wypisać na standardowe wyjscie n wierszy. Wiersz o numerze i (dla 1 ¬ i ¬ n) powinien zawierać jedno słowo „TAK” lub „NIE” (bez cudzysłowów), w zaleznosci od tego, czy i-ta sekwencja z wejścia moze powstac w wyniku wykreslenia (tj. usuniecia) pewnych (niekoniecznie kolejnych) liczb z początkowego ciagu. Oczywiście, kolejność liczb w powstałym po wykreśleniach ciagu ma znaczenie (patrz przykład).

Przykład

Dla danych wejsciowych:

7

1 5 4 5 7 8 6

4

5

1 5 5 8 6

3

2 2 2

3

5 7 8

4

1 5 7 4

poprawnym wynikiem jest:

TAK

NIE

TAK

NIE

---