Contest problemset description


Podarek
(A)
Limit pamięci: 128 MB
Limit czasu: 1.00 s

Podczas wakacyjnej wycieczki Jasio odwiedził niewielką, zabytkową miejscowość. Jednym z miejsc, które szczególnie chciał zobaczyć, był stary kościół o pięknych zdobieniach.

Na miejscu spotkał starszą kobietę, mieszkankę tej okolicy. Staruszka opowiedziała mu kilka ciekawych historii związanych z kościołem i jego mieszkańcami. Jasio z zainteresowaniem słuchał opowieści, a na koniec serdecznie podziękował za miłą rozmowę.

Na pożegnanie kobieta postanowiła wręczyć mu podarek – własnoręcznie wykonaną, piękną chustę ozdobioną niezwykłym wzorem. Wzór składał się z liczb ułożonych symetrycznie, tak jak pokazano na przykładzie.

Jasio był zachwycony prezentem. Chciałby jednak zobaczyć, jak wyglądałaby taka chusta w innych rozmiarach. Pomóż mu ją zaprojektować!

Wejście

Jedyna linia wejścia zawiera liczbę całkowitą N – rozmiar wzoru.

Wyjście

Wypisz wzór chusty składający się z 2N + 1 wierszy. Liczby w każdym wierszu powinny być oddzielone pojedynczymi spacjami. W przykładach poniżej można zobaczyć jak wygląda wzór dla N = 2 i N = 3.

Ograniczenia

2 ≤ N ≤ 9.

Podzadania

Podzadanie Dodatkowe warunki Punkty
1 N ≤ 4 15
2 brak 85

Przykład

Wejście Wyjście Wyjaśnienie
2
    0
  0 1 0
0 1 2 1 0
  0 1 0
    0

Tak wygląda wzór dla N = 2.

Wejście Wyjście Wyjaśnienie
3
      0
    0 1 0
  0 1 2 1 0
0 1 2 3 2 1 0
  0 1 2 1 0
    0 1 0
      0

A tak wygląda wzór dla N = 3.


Wybieranie Składów
(B)
Limit pamięci: 128 MB
Limit czasu: 1.00 s

Na dzisiejszej lekcji WF-u uczniowie będą grać w piłkę nożną, więc muszą podzielić sie na dwie drużyny. Jaś i Małgosia są kapitanami drużyn i na razie ich składy liczą odpowiednio A i B osób.

Jest jeszcze C uczniów, którzy nie zostali jeszcze wybrani do żadnego składu. Część z tych uczniów zostanie przydzielona do składów w następujący sposób. Jaś i Małgosia będą wybierać na zmianę, zaczynając od Jasia. W swojej turze każde z nich może wybrać pewną liczbę (być może 0) jeszcze nie wybranych uczniów i przyłączyć ich do swojego składu.

Wybieranie składów kończy się, jeżeli oboje kapitanów zdecyduje się nie wybierać już więcej zawodników do swojego składu, czyli jeżeli zarówno Jaś, jak i Małgosia wybiorą 0 uczniów w kolejnych turach. Nie wszyscy uczniowie muszą zostać wybrani do składu. Niewybrani uczniowie będą grać w zbijaka.

Powiedzmy, że po całym procesie wybierania w składzie Jasia jest X osób a w składzie Małgosi Y. Małgosia chciałaby żeby mecz był jak najbardziej wyrównany, więc chciałaby, żeby liczba |X−Y| była jak najmniejsza. Jaś natomiast chciałby żeby któryś skład miał dużą przewagę (może to być nawet skład Małgosi), dlatego chciałby żeby liczba |X−Y| była jak największa.

Określ, ile będzie wynosić |X−Y|, jeżeli Jaś i Małgosia dokonują optymalnych decyzji.

Wejście

W pierwszym (jedynym) wierszu wejścia znajdują się trzy liczby całkowite: A, B i C.

Wyjście

W pierwszym (jedynym) wierszu wyjścia powinna się znaleźć jedna liczba całkowita, oznaczająca wartość |X−Y|.

Ograniczenia

0 ≤ A, B, C ≤ 109.

Przykład

Wejście Wyjście Wyjaśnienie
3 6 3
3

Jaś może wybrać 0 osób. Wtedy dla Małgosi najlepszą opcją również będzie wybranie 0 osób. Po jej turze wybieranie się kończy i składy liczą 3 i 6 osób, więc wynik to 6 − 3 = 3.

Wejście Wyjście Wyjaśnienie
3 6 10
7

Jaś może wybrać wszystkie 10 osób. Jedynym wyborem Małgosi i Jasia w następnych turach jest wybranie 0 osób (bo nie mają kogo wybierać) i wtedy składy będą liczyć 13 i 6 osób, więc wynik to 13 − 6 = 7.

Wejście Wyjście
5 5 4
4

Odwracanie Znaków
(C)
Limit pamięci: 128 MB
Limit czasu: 2.00 s

W laboratorium zapisano ciąg liczb całkowitych. Jedyna dostępna operacja pozwala jednocześnie odwrócić znaki dwóch sąsiednich liczb.

Dla tablicy A składającej się z N elementów możesz dowolną liczbę razy (być może zero razy) wykonać następującą operację:

  • wybierz indeks i spełniający 1 ≤ i < N,
  • zastąp Ai przez  − Ai oraz Ai + 1 przez  − Ai + 1.

Do rozwiązania jest T niezależnych zestawów testowych. Dla każdego z nich wyznacz największą możliwą sumę wszystkich elementów tablicy po wykonaniu wybranych operacji.

Wejście

W pierwszym wierszu znajduje się liczba całkowita T - liczba zestawów testowych.

Opis każdego zestawu testowego składa się z dwóch wierszy. W pierwszym z nich znajduje się liczba całkowita N - długość tablicy.

W drugim wierszu znajduje się N liczb całkowitych A1, A2, …, AN - początkowe wartości elementów tablicy.

Wyjście

Dla każdego zestawu testowego wypisz w osobnym wierszu jedną liczbę całkowitą - największą sumę elementów tablicy, jaką można uzyskać.

Ograniczenia

1 ≤ T ≤ 1000, 2 ≤ N ≤ 200 000,  − 109 ≤ Ai ≤ 109, suma wartości N we wszystkich zestawach testowych nie przekracza 200 000

Przykład

Wejście Wyjście Wyjaśnienie
5
3
-1 -1 -1
5
1 5 -5 0 2
3
1 2 3
6
-1 10 9 8 7 6
2
-1 -1
1
13
6
39
2

Wyjaśnijmy pierwszy i drugi zestaw. W pierwszym wybieramy pierwszą parę (−1,−1) i zmieniamy znaki obu liczb. Tablica zmienia się z [−1,−1,−1] na [1,1,−1], a suma jej elementów wynosi 1 + 1 − 1 = 1. W drugim zestawie wybieramy sąsiednie elementy  − 5 i 0. Po zmianie ich znaków otrzymujemy tablicę [1,5,5,0,2], której suma wynosi 1 + 5 + 5 + 0 + 2 = 13.

Wejście Wyjście Wyjaśnienie
6
2
-5 2
4
-2 -2 3 3
4
0 -7 -8 -9
5
-4 1 1 1 1
2
-1 0
3
1000000000 1000000000 1000000000
3
10
24
6
1
3000000000

Wyjaśnijmy pierwszy i drugi zestaw. W pierwszym jedyną parę (−5,2) zmieniamy na (5,−2). Otrzymana suma to 5 − 2 = 3. W drugim zestawie wybieramy pierwszą parę (−2,−2) i zmieniamy znaki obu elementów. Powstaje tablica [2,2,3,3], a suma jej elementów wynosi 2 + 2 + 3 + 3 = 10.


Kiedy Dostawa?
(D)
Limit pamięci: 256 MB
Limit czasu: 2.00 s

Bajtek znalazł w sklepie internetowym wymarzoną koszulkę. Niestety okazało się, że jego rozmiar jest obecnie niedostępny! Nie chcąc przegapić kolejnej dostawy, Bajtek zapisał się na listę oczekujących, dzięki czemu będzie mógł odebrać koszulkę, gdy tylko pojawi się ona w magazynie.

Bajtek nie należy jednak do cierpliwych osób. Postanowił więc napisać do sklepu wiadomość z pytaniem, ile najdłużej będzie musiał czekać na swoją koszulkę.

Pech chciał, że na wiadomość Bajtka musi odpowiedzieć pracownik, który dopiero dziś rozpoczął pracę w sklepie.

Pracownik wie, że każdego dnia do sklepu przyjeżdża dostawa koszulek w jednym z trzech rozmiarów: S, M lub L. Dostawy odbywają się według ustalonego harmonogramu składającego się z N dni, który powtarza się cyklicznie.

Harmonogram jest opisany napisem S długości N. W i-tym dniu cyklu dostarczane są koszulki w rozmiarze Si. Po ostatnim dniu harmonogram rozpoczyna się ponownie od pierwszego dnia.

Pracownik otrzymał harmonogram oraz informację, że Bajtek potrzebuje koszulki w rozmiarze C. Nie zdążył jednak dowiedzieć się, który dzień cyklu właśnie trwa. Wie jedynie, że dzisiejsza dostawa zawiera koszulki w rozmiarze D.

Pomóż pracownikowi odpowiedzieć na wiadomość Bajtka. Wyznacz największą możliwą liczbę dni, które Bajtek będzie musiał czekać na najbliższą dostawę koszulek w rozmiarze C. Przyjmij, że jeśli odpowiedni rozmiar zostanie dostarczony jeszcze dzisiaj, czas oczekiwania wynosi 0 dni.

Wejście

W pierwszym wierszu znajdują się liczba całkowita N oraz dwa znaki C i D. Oznaczają one odpowiednio długość harmonogramu, rozmiar poszukiwany przez Bajtka oraz rozmiar znajdujący się w dzisiejszej dostawie.

W drugim wierszu znajduje się napis S długości N, złożony wyłącznie ze znaków S, M i L. Opisuje on harmonogram dostaw.

Wyjście

Wypisz jedną liczbę całkowitą - największą możliwą liczbę dni oczekiwania na najbliższą dostawę koszulek w rozmiarze C.

Ograniczenia

1 ≤ N ≤ 106, C, D ∈ {S, M, L}, |S| = N, każdy znak napisu S należy do zbioru {S, M, L}, znaki C i D występują w napisie S

Podzadania

Podzadanie Dodatkowe warunki Punkty
1 SN = C 40
2 Bez dodatkowych ograniczeń 60

Przykład

Wejście Wyjście Wyjaśnienie
5 L S
SLLSM
3

Dostawy rozmiaru S znajdują się na pozycjach 0 i 3. Z pozycji 0 do najbliższej dostawy L trzeba czekać 1 dzień. Z pozycji 3 harmonogram prowadzi kolejno przez M, S i L, więc oczekiwanie trwa 3 dni. Większa z tych wartości to 3.

Wejście Wyjście Wyjaśnienie
1 S S
S
0

Jedyna dostawa ma rozmiar S. Poszukiwany rozmiar jest dostarczany dzisiaj, więc czas oczekiwania wynosi 0 dni.

Wejście Wyjście Wyjaśnienie
6 M L
MLSSSL
5

Dostawy rozmiaru L znajdują się na pozycjach 1 i 5. Z pozycji 1 harmonogram prowadzi przez S, S, S, L, a następnie M, więc oczekiwanie trwa 5 dni. Z pozycji 5 dostawa M następuje po 1 dniu. Większa z tych wartości to 5.


Początkujący Wspinacz
(E)
Limit pamięci: 256 MB
Limit czasu: 1.00 s

Bajtek od zawsze uwielbiał chodzić po górach, a niedawno postanowił rozpocząć również treningi wspinaczki. Aby sprawdzić swoje umiejętności, planuje wyprawę na szlak składający się z N kolejnych szczytów. Każdy z nich ma określoną wysokość.

Bajtek może rozpocząć wyprawę od dowolnego szczytu i zakończyć może również po dowolnym szczycie. Następnie będzie poruszał się wyłącznie do przodu, zdobywając kolejne szczyty, bez możliwości zawracania ani pomijania któregokolwiek z nich.

Ponieważ dopiero zaczyna swoją przygodę ze wspinaczką, zna swoje ograniczenia. Wie, że podczas jednej wyprawy może zdobyć co najwyżej D szczytów o wysokości większej lub równej H. Pozostałych szczytów może zdobyć dowolnie wiele.

Bajtek chciałby, aby jego wyprawa była jak najdłuższa, ale nie wie, od którego szczytu powinien ją rozpocząć. Postanowił więc poprosić Cię o pomoc!

Napisz program, który wyznaczy największą liczbę szczytów, jakie Bajtek może zdobyć podczas jednej wyprawy, oraz znajdzie wszystkie szczyty, od których może rozpocząć wyprawę o tej długości.

Wejście

W pierwszym wierszu znajdują się trzy liczby całkowite N, H oraz D: liczba szczytów, minimalna wysokość wysokiego szczytu oraz maksymalna dozwolona liczba wysokich szczytów podczas jednej wyprawy.

W drugim wierszu znajduje się N liczb całkowitych A1, A2, …, AN, oznaczających wysokości kolejnych szczytów.

Wyjście

W pierwszym wierszu wypisz największą liczbę szczytów, które Bajtek może zdobyć podczas jednej wyprawy.

W drugim wierszu wypisz liczbę szczytów, od których Bajtek może rozpocząć wyprawę o maksymalnej długości.

W trzecim wierszu wypisz numery tych szczytów w kolejności rosnącej, oddzielone pojedynczymi spacjami. Szczyty są numerowane od 1 do N.

Jeżeli Bajtek nie może zdobyć nawet jednego szczytu, w pierwszych dwóch wierszach wypisz 0, a trzeci wiersz pozostaw pusty.

Ograniczenia

1 ≤ N ≤ 106, 0 ≤ D ≤ N, 1 ≤ H ≤ 109, 1 ≤ Ai ≤ 109

Podzadania

Podzadanie Dodatkowe warunki Punkty
1 N ≤ 103 30
2 Bez dodatkowych ograniczeń 70

Przykład

Wejście Wyjście Wyjaśnienie
6 5 0
5 1 1 5 1 1
2
2
2 5

Ponieważ D = 0, Bajtek nie może zdobyć żadnego szczytu o wysokości co najmniej 5. Najdłuższe możliwe wyprawy prowadzą przez szczyty od 2 do 3 oraz od 5 do 6. Obie mają długość 2, dlatego możliwe numery szczytów startowych to 2 i 5.

Wejście Wyjście Wyjaśnienie
6 5 0
5 6 7 8 9 10
0
0

Każdy ze szczytów ma wysokość co najmniej 5, a D = 0. Bajtek nie może więc zdobyć nawet jednego szczytu. Maksymalna długość wyprawy i liczba możliwych szczytów startowych wynoszą 0, a trzeci wiersz pozostaje pusty.

Wejście Wyjście Wyjaśnienie
8 10 2
10 1 2 10 3 4 10 5
7
1
2

Bajtek może zdobyć najwyżej dwa szczyty o wysokości co najmniej 10. Rozpoczynając od szczytu numer 2, może dojść aż do szczytu numer 8. Taka wyprawa ma długość 7 i obejmuje dwa wysokie szczyty: 4 i 7. Nie można rozpocząć wcześniej ani wydłużyć tej wyprawy, ponieważ wtedy obejmowałaby również szczyt numer 1, czyli trzeci wysoki szczyt. Jedynym możliwym numerem szczytu startowego jest zatem 2.


Pielęgnacja Trawnika
(F)
Limit pamięci: 128 MB
Limit czasu: 3.00 s

Na rozległym polu znajduje się N skupisk chwastów. Skupisko o indeksie i leży w punkcie o współrzędnych (Ri,Ci) i początkowo zawiera Ai chwastów. Wszystkie pary współrzędnych (Ri,Ci) są różne, jednak kilka skupisk może znajdować się w tym samym wierszu lub w tej samej kolumnie.

Bajtek musi przeprowadzić dokładnie jedną operację pielęgnacji. Wybiera w tym celu jedno skupisko o indeksie k. Przyjmijmy, że R = Rk, C = Ck oraz X = Ak, gdzie X oznacza liczbę chwastów w wybranym skupisku przed wykonaniem operacji.

Następnie Bajtek próbuje usunąć po X chwastów z każdego skupiska znajdującego się w wierszu R lub w kolumnie C. Liczba chwastów nie może jednak spaść poniżej zera. Jeżeli w skupisku jest mniej niż X chwastów, Bajtek usuwa je wszystkie. Dokładniej, końcowa liczba chwastów w skupisku o indeksie i wynosi

$$ B_i = \begin{cases} \max(0, A_i - X) & \text{gdy } R_i = R \text{ lub } C_i = C,\\ A_i & \text{w przeciwnym przypadku.} \end{cases} $$

Jeżeli skupisko znajduje się jednocześnie w wybranym wierszu i wybranej kolumnie, operacja jest wykonywana na nim tylko raz. Dotyczy to wybranego skupiska, którego końcowa wartość jest równa Bk = 0. Każda wartość Bi jest więc nieujemna.

Bajtek chce tak wybrać skupisko, aby największa końcowa liczba chwastów w pojedynczym skupisku była możliwie najmniejsza. Pomóż mu wyznaczyć tę wartość.

Wejście

W pierwszym wierszu znajduje się liczba całkowita T - liczba niezależnych zestawów testowych.

Opis każdego zestawu testowego rozpoczyna się od wiersza zawierającego liczbę całkowitą N - liczbę skupisk chwastów.

W każdym z kolejnych N wierszy znajdują się trzy liczby całkowite Ri, Ci oraz Ai - odpowiednio numer wiersza, numer kolumny i początkowa liczba chwastów w skupisku o indeksie i.

W obrębie jednego zestawu testowego wszystkie pary (Ri,Ci) są różne.

Wyjście

Dla każdego zestawu testowego wypisz w osobnym wierszu jedną liczbę całkowitą - najmniejszą możliwą wartość max1 ≤ i ≤ NBi po wykonaniu dokładnie jednej operacji pielęgnacji.

Ograniczenia

1 ≤ T ≤ 104, 1 ≤ N ≤ 106, 1 ≤ Ri, Ci, Ai ≤ 109, suma wartości N we wszystkich zestawach testowych nie przekracza 106

Podzadania

Podzadanie Dodatkowe warunki Punkty
1 Ri, Ci ≤ 50 10
2 Ri, Ci ≤ 1000 40
3 Bez dodatkowych ograniczeń 50

Przykład

Wejście Wyjście Wyjaśnienie
3
3
1 1 5
1 2 8
2 1 7
3
1 1 4
2 2 6
3 3 5
4
1 10 9
1 20 6
2 10 7
2 20 4
3
5
4

W pierwszym zestawie wybieramy skupisko (1,1) o wartości 5. Po operacji wartości wynoszą 0, 3 i 2, więc największa z nich to 3.

W drugim zestawie żadne dwa skupiska nie leżą w tym samym wierszu ani w tej samej kolumnie. Po wybraniu skupiska o wartości 6 tylko ono zmienia wartość na 0, a największą z pozostałych wartości jest 5.

W trzecim zestawie wybieramy skupisko (1,10) o wartości 9. Z pierwszego, drugiego i trzeciego skupiska usuwamy odpowiednio 9, 6 i 7 chwastów, ponieważ liczba chwastów nie może być ujemna. Końcowe wartości to 0, 0, 0 i 4, zatem odpowiedź wynosi 4.

Wejście Wyjście Wyjaśnienie
3
1
1 1 100
4
5 1 3
5 2 10
5 3 6
5 4 1
4
1000000000 1000000000 4
999999999 999999998 10
999999997 999999996 7
999999995 999999994 2
0
0
7

W pierwszym zestawie istnieje tylko jedno skupisko. Po jego wybraniu pozostaje w nim 0 chwastów.

W drugim zestawie wszystkie skupiska znajdują się w wierszu 5. Wybieramy skupisko o wartości 10 i usuwamy wszystkie chwasty z każdego skupiska. Końcowe wartości to 0, 0, 0 i 0, więc ich maksimum jest równe 0.

W trzecim zestawie każde skupisko leży w innym wierszu i innej kolumnie. Wybieramy skupisko o wartości 10; zmienia się ono na 0, a największa spośród pozostałych wartości wynosi 7.


Pociąg Do Sum
(G)
Limit pamięci: 1024 MB
Limit czasu: 2.00 s

Bajtek jest odpowiedzialny za przygotowanie pociągu na coroczną paradę kolejową. Tegoroczny skład ma być wyjątkowy, dlatego Bajtek opracował specjalny plan jego budowy.

Plan jest permutacją a1, a2, …, ad liczb od 1 do d, gdzie d jest nieparzyste.

Na jego podstawie Bajtek buduje pociąg składający się z dwóch rodzajów wagonów: lekkich, ważących 1 tonę, oraz ciężkich, ważących P ton, gdzie

$$ P=1+2+\ldots+d=\frac{d(d+1)}{2}. $$

Wagony są ustawiane w następującej kolejności:

  • najpierw a1 lekkich wagonów,
  • następnie a2 ciężkich wagonów,
  • potem a3 lekkich wagonów,
  • następnie a4 ciężkich wagonów,
  • i tak dalej, aż do ustawienia wszystkich wagonów.

W ten sposób powstaje pociąg składający się z dokładnie P wagonów. Ponieważ d jest nieparzyste, pierwszy i ostatni wagon są lekkie.

Przed paradą pociąg musi przejść kontrolę techniczną. W tym celu pracownik stacji waży wszystkie możliwe niepuste spójne fragmenty pociągu, czyli fragmenty składające się z kolejnych wagonów.

Stacyjna waga ma jednak pewne ograniczenie: podczas jednego pomiaru może znajdować się na niej co najwyżej jedna grupa kolejnych ciężkich wagonów. Innymi słowy, ważony fragment nie może zawierać ciężkich wagonów należących do dwóch różnych grup w utworzonym pociągu.

Pracownik skrupulatnie zapisał wyniki wszystkich dozwolonych pomiarów. Niestety, przez nieuwagę pomieszał swoje notatki, a oryginalny plan budowy pociągu gdzieś zaginął.

Bajtek musi teraz odtworzyć plan, zanim rozpocznie się parada. Pomóż mu znaleźć dowolną permutację, na podstawie której mógł powstać pociąg dający dokładnie takie same wyniki pomiarów.

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby całkowite P i m, oznaczające odpowiednio liczbę wagonów w pociągu oraz liczbę wykonanych pomiarów.

W drugim wierszu znajduje się m liczb całkowitych s1, s2, …, sm - masy wszystkich niepustych spójnych fragmentów pociągu zawierających co najwyżej jedną grupę ciężkich wagonów, podane w dowolnej kolejności.

Jeżeli kilka różnych fragmentów ma taką samą masę, wynik ten występuje na wejściu odpowiednią liczbę razy.

Możesz założyć, że dane wejściowe zostały wygenerowane zgodnie z opisanym procesem dla pewnej permutacji liczb od 1 do d, gdzie d jest nieparzyste oraz $P=\frac{d(d+1)}2$. Dodatkowo 3 ≤ d ≤ 99 oraz m ≤ 800 000

Wyjście

Wypisz d liczb całkowitych - permutację a1, a2, …, ad, która mogła posłużyć do zbudowania opisanego pociągu.

Jeżeli istnieje wiele poprawnych odpowiedzi, możesz wypisać dowolną z nich.

Ograniczenia

Grupa Dodatkowe warunki Punkty
1 3 ≤ d ≤ 9, m ≤ 700 16
2 d ≤ 21, m ≤ 8 000 30
3 d ≤ 47, m ≤ 85 000 30
4 d ≤ 99, m ≤ 800 000 24

Przykład

Wejście Wyjście Wyjaśnienie
6 21
15 15 6 7 16 7 14 3 12 1 6 1 2 1 13 14 9 8 13 1 2 
1 2 3 

Dla d = 3 oraz permutacji [1,2,3] mamy

$$ P=\frac{3\cdot4}{2}=6. $$

Powstały pociąg składa się z wagonów o następujących masach:

[1,6,6,1,1,1].

Zawiera on tylko jedną grupę ciężkich wagonów, dlatego każdy jego niepusty spójny fragment może zostać zważony.

Łącznie istnieje $\frac{6\cdot7}{2}=21$ takich fragmentów. Ich masy, wraz z powtórzeniami, są dokładnie liczbami podanymi na wejściu.

Drugi test przykładowy powstał z permutacji [1, 2, 3, 4, 5]