Contest problemset description

Maciej jest koneserem frytek belgijskich. Ciężko dogodzić jego wymaganiom, z tego powodu co roku, w każdą jesień, samodzielnie wybiera się na pole ziemniaków, żeby wybrać ziemniaki najlepszej jakości. Pole składa się z jednej, długiej grządki, w której rośnie N ziemniaków, jeden za drugim. Maciej każdemu ziemniakowi przypisuje pewien stopień okazałości A_i. Oczywiście im ziemniak jest bardziej okazały, tym lepiej.

Maciejowi do zapasów na następny rok potrzebne jest dokładnie K ziemniaków. Zależy mu na tym, żeby sumaryczny stopień okazałości ziemniaków był jak największy. Z drugiej strony zdaje sobie sprawę, że ziemniaki, które rosną w dużej odległości od siebie, będą się od siebie znacząco różniły. Stąd dla danego podciągu ziemniaków (A_i1,…,A_iK), gdzie i₁ < i₂ < …i_K, jego jakość Maciej oblicza jako sumę okazałości ziemniaków minus różnicę odległości dwóch najbardziej odległych ziemniaków, tj.:

$$(\sum^K_{j=1}A_{i_j}) - (i_K - i_1)^2$$

Maciej wyznaczył Ciebie do znalezienia najlepszego podciągu ziemniaków, a w zamian podzieli się z Tobą pysznymi frytkami. Pomóż mu i napisz program, który wyznaczy maksymalną możliwą jakość podciągu K ziemniaków.

Wejście

W pierwszym wierszu standardowego wejścia znajdują się dwie liczby naturalne N, K oznaczające długość grządki ziemniaków oraz liczbę ziemniaków potrzebnych Maciejowi. W następnym wierszu następuje N nieujemnych liczb całkowitych A₁, A₂, …, A_N oznaczających okazałości kolejnych ziemniaków w grządce.

Wyjście

W pierwszym (jedynym) wierszu standardowego wyjścia powinna się znaleźć jedna liczba całkowita oznaczająca maksymalną możliwą jakość podciągu K ziemniaków.

Ograniczenia

2 ≤ K ≤ N ≤ 200 000, 1 ≤ A_i ≤ 10¹².

Przykład

6 3
2 8 1 3 7 3 

9

Ostatnio na zajęciach informatyki Ania zapoznała się z nowym pojęciem: K-pokryciem grafu. Dla danej liczby naturalnej K oraz danego grafu nieskierowanego mówimy, że podzbiór T wierzchołków tego grafu jest K-pokryciem wtedy, kiedy spełnione są dwa następujące warunki:

• Każda krawędź grafu jest incydentna z pewnym wierzchołkiem z T. Innymi słowy, dla każdej krawędzi (u,v) grafu zachodzi u ∈ T lub v ∈ T,
• Jeżeli wierzchołek o numerze v należy do T, to żaden z jego sąsiadów o numerach z przedziału [v−K,v+K] nie należy do T.

Ania, jak każda entuzjastka zadań algorytmicznych, ma swój ulubiony graf nieskierowany. Zaczęła się teraz zastanawiać, czy dla danego K istnieje K-pokrycie jej ulubionego grafu? Pomóż Ani rozwiązać ten problem.

Wejście

W pierwszym wierszu wejścia znajdują się trzy liczby naturalne N, M, Q oznaczające odpowiednio liczbę wierzchołków i liczbę krawędzi grafu Ani oraz liczbę zapytań. W następnych M wierszach następuje opis krawędzi grafu. Każdy wiersz składa się z dwóch liczb naturalnych u, v oznaczających, że w grafie występuje krawędź między wierzchołkami u i v. W następnych Q wierszach następują zapytania. W i-tym wierszu dana jest jedna liczba naturalna K_i.

Wyjście

Należy wypisać Q wierszy. W i-tym wierszu należy wypisać słowo TAK, jeżeli istnieje K_i-pokrycie grafu Ani, a w przeciwnym wypadku należy wypisać NIE.

Ograniczenia

1 ≤ N, M, Q, K_i ≤ 200 000, 1 ≤ u, v ≤ N.

Przykład

3 3 2
1 2
2 3
3 1
1
3

TAK
NIE

Konrad i Szymon uwielbiają wspólne wycieczki rowerowe. Ostatnimi czasy szczególnie podoba im się wycieczka wzdłuż bajtockiego lasu. Widok widziany przez Konrada i Szymona można opisać jako ciąg N drzew o wysokościach A₁, A₂, …, A_N. Las powstał w sposób zupełnie naturalny, dlatego wysokości drzew są losowe. Innymi słowy, można założyć, że każde drzewo z jednostajnym prawdopodobieństwem wyrosło na pewną wysokość z przedziału [1,1 000 000].

Chłopakom zdecydowanie najbardziej przypadły do gustu te części lasu, które z daleka wyglądają najbardziej jednorodnie. Każdemu spójnemu przedziałowi drzew A_l, A_l + 1, …, A_r Konrad i Szymon przypisali stopień jednorodności, który wyraża się następującym wzorem:

$$\frac{\min(\{A_l,\ldots A_r\})}{\max(\{A_l,\ldots,A_r\})}(r - l + 1)$$

Im wyższy stopień jednorodności, tym chłopakom bardziej podoba się spoglądanie na dany fragment lasu. Pomóż im i napisz program, który dla danego ciągu wysokości drzew znajdzie wartość przedziału o największym stopniu jednorodności.

Wejście

W pierwszym wierszu standardowego wejścia znajduje się jedna liczba naturalna N określająca liczbę drzew w lesie. W drugim wierszu wejścia następuje ciąg N liczb całkowitych A₁, …, A_N poodzielanych pojedynczymi odstępami, określający wysokości kolejnych drzew lasu.

Wyjście

W pierwszym wierszu standardowego wyjścia powinna się znaleźć jedna liczba określająca wartość przedziału drzew o maksymalnym stopniu jednorodności. Odpowiedź zostanie zaakceptowana jeżeli będzie się różnić od poprawnej (błąd względny lub bezwzględny) o nie więcej niż 10^{-6}.

Ograniczenia

1 ≤ N ≤ 500 000, 1 ≤ A_i ≤ 1 000 000. Wartości ciągu to liczby całkowite, zostały wylosowane jednostajnie ze zbioru [1,1 000 000].

Przykład

5
5 2 8 4 7 

1.5000000000

Zuzi oraz Irynie zostało powierzone zadanie przebudowania centrum miasta, które składa się z ciągu N budynków o wysokościach A₁, …, A_N, każdy o szerokości 1. Miasto jest różnorodne, zatem żadne dwa budynki nie mają tej samej wysokości. Podczas przebudowy zmieniany ma być pewien spójny przedział budynków. W tym czasie remontowane budynki, ze względów bezpieczeństwa, powinny zostać zasłonięte ochronną płachtą. Podczas przebudowy pewnego przedziału budynków, płachta powinna zasłonić całkowicie wszystkie budynki, ale ze względu na to, że jest prostokątna, może się zdarzyć, że za pewnymi częściami płachty nie będzie żadnej części budynku.

Zuzia i Iryna muszą zatem zamówić odpowiednie płachty. Dziewczyny zaczęły się zastanawiać, dla danego pola powierzchni K, ile jest przedziałów budynków, które dałoby się zasłonić płachtą o polu K, ale takich, których nie dałoby zasłonić się mniejszą płachtą? Pomóż im i napisz program, który będzie odpowiadał na to pytanie.

Wejście

W pierwszym wierszu standardowego wejścia znajdują się dwie liczby naturalne N, Q oznaczające odpowiednio liczbę budynków oraz liczbę zapytań. W drugim wierszu wejścia znajduje się ciąg parami różnych liczb A₁, A₂, …, A_N oznaczających wysokości kolejnych budynków w mieście. W następnych Q wierszach znajduje się opis zapytań, i-te zapytanie składa się z jednej dodatniej liczby całkowitej K_i.

Wyjście

Należy wypisać Q wierszy. W i-tym wierszu należy wypisać odpowiedź na zapytanie dziewczyn dla wartości K_i.

Ograniczenia

1 ≤ N ≤ 1 000 000, 1 ≤ Q ≤ 1000, 1 ≤ K_i, A_i ≤ 10¹². Wartości ciągu A_i są parami różne.

Przykład

6 2
5 2 6 3 4 1 
8
18

2
3

Zachary, Michał i Antoni w ramach pracy wakacyjnej zajmują się pilnowaniem owiec pasących się na polanie. Pasterze nie mogą dopuścić, żeby jakakolwiek owca opuściła teren polany. Żeby ułatwić sobie trochę pracę, postanowili postawić płot i zbudować zagrodę, do której zagoniliby wszystkie owce.

Teren polany można reprezentować jako wielokąt wypukły na płaszczyźnie. Chłopaki, skoro jest ich trzech, chcieliby wybrać trzy punkty tego wielokąta i poprowadzić między nimi ogrodzenie. Po zbudowaniu zagrody część owiec będzie się już w niej znajdować (w szczególności te, które stoją w miejscu, przez które będzie przechodził płot), jednakże należałoby zagonić do niej wszystkie pozostałe zwierzęta.

Owce tego lata są wyjątkowo leniwe i uparte, więc zaganianie ich kosztuje Zacharego, Michała i Antoniego wiele wysiłku. Chcieliby zbudować zagrodę tak, żeby później musieć zagonić do niej jak najmniejszą liczbę owiec. Poprosili Cię o pomoc w wyznaczeniu jak powinna wyglądać zagroda.

Wejście

W pierwszym wierszu standardowego wejścia znajdują się dwie liczby naturalna N, M oznaczające kolejno liczbę wierzchołków wielokąta wypukłego opisującego kształt polany oraz liczbę owiec. W następnych N wierszach następuje opis polany. Każdy wiersz składa się z dwóch liczb całkowitych x, y oznaczających, że w punkcie x, y znajduje się wierzchołek wielokąta. Wierzchołki podane są w kolejności wg wskazówek zegara. W następnych M wierszach znajdują się współrzędne kolejnych owiec. Każdy wiersz składa się z dwóch liczb całkowitych x, y określających, że w punkcie x, y stoi owca.

Wyjście

W pierwszym wierszu wyjścia powinny znaleźć się trzy liczby naturalne Z, M, A oznaczające numery wierzchołków wielokąta określającego kształt polany, które powinny być wierzchołkami trójkątnej zagrody zbudowanej przez chłopaków. Wśród wszystkich możliwych odpowiedzi należy podać najmniejszą leksykograficznie.

Ograniczenia

1 ≤ N, M ≤ 2000,  − 10⁹ ≤ x, y ≤ 10⁹. Możesz założyć, że współrzędne owiec znajdują się wewnątrz wielokąta (w szczególności mogą znajdować się na jego bokach lub wierzchołkach).

Przykład

5 5
-3 3
0 4
4 1
2 -1
-1 -3
-1 2
0 3
-1 -1
1 2
-1 -2

1 2 5

Marcin niedawno zapoznał się z problemem ustawiania hetmanów na szachownicy, którego treść jest następująca: mając daną szachownię o wymiarach N × N należy ustawić na niej N hetmanów tak, żeby żaden hetman nie atakował żadnego innego. Dla przypomnienia, hetman atakuje wszystkie figury, które stoją w tym samym rzędzie, kolumnie lub przekątnej co dany hetman.

W ramach rozgrzewki Marcin postanowił poukładać sobie hetmany na różne sposoby na szachownicy. Niestety, hetmanów jest tak dużo, że zaczął gubić się w sprawdzaniu czy na pewno żaden hetman nie atakuje żadnego innego. Marcin poprosił Cię o napisanie programu, który będzie to sprawdzał.

Wejście

W pierwszym wierszu strandardoweg wejścia znajdują się dwie liczby naturalne oddzielone pojedynczym odstępem N i M oznaczające odpowiednio wymiar szachownicy oraz liczbę postawionych hetmanów. W następnych M wierszach następują opisy położenia hetmanów. Każdy wiersz składa się z dwóch liczb całkowitych X, Y oznaczających, że w X-tym rzędzi oraz Y-tej kolumnie szachownicy stoi hetman.

Wyjście

W jednym wierszu standardowego wyjścia powinno znajdować się słowo DOBRZE, jeżeli żaden hetman nie atakuje innego hetmana oraz słowo ATAK w przeciwynym przypadku.

Ograniczenia

1 ≤ X, Y ≤ N ≤ 1 000 000, 1 ≤ M ≤ 1 000 000. Można założyć, że żadni dwaj hatmanowie nie stoją na jednym polu.

Przykład

4 3
1 1
4 2
3 4

DOBRZE

2 2
1 1
2 2

ATAK

Amelia i Tymon uwielbiają chodzić na długie spacery. Szczególnie często zdarza się, że Tymon odprowadza Amelię ze szkoły do jej domu. Żeby urozmaicić sobie przechadzki, starają się wybierać różne możliwe trasy.

Sieć spacerową Amelii i Tymona można opisać jako N skrzyżowań połączonych drogami. Szkoła znajduje się przy skrzyżowaniu o numerze 1, a dom Amelii przy skrzyżowaniu o numerze N. Para nie chce krążyć zbyt długo przed dotarciem do domu, dlatego po każdej drodze łączącej dwa skrzyżowania mogą przejść tylko w jednym kierunku. Nie chcieliby również trafić dwukrotnie do skrzyżowania, przez które już przechodzili. Można zatem powiedzieć, że ich sieć spacerowa stanowi acykliczny graf skierowany.

Tomek, który jest dobrym znajomym Amelii i Tymona, został ostatnio głównym inspektorem do spraw rozbudowy dróg w ich mieście. Tymon poprosił Tomka, żeby ten rozbudował drogi w mieście w taki sposób, żeby liczba różnych możliwych tras spacerowych ze szkoły do domu Amelii była podzielna przez K. Tomek, jak to dobry kumpel, chciałby spełnić prośbę Tymona. Jednakże, skoro dopiero awansował na swoje stanowisko, nie chciałby, żeby rozbudowa była zbyt duża. Zdecydował zatem, że może pozwolić sobie jedynie na wybranie już istniejącej pary skrzyżowań, między którymi istnieje droga, a następnie zwielokrotnienie tej drogi (tzn. z jednego skrzyżowania do drugiego można będzie przejść na wiele sposobów, a nie tylko jeden). Tomek dla każdej ulicy chciałby zatem wiedzieć, ile razy co najmniej powinna ona zostać zwielokrotniona lub dowiedzieć się, że nie da się jej zwielokrotnić tak, żeby spełnić jego oczekiwania. Zadanie znalezenia odpowiedzi powierzył Tobie!

Wejście

W pierwszym wierszu standardowego wejścia znajdują się trzy liczby naturalne N, M oraz K, oznaczające kolejno liczbę skrzyżowań, liczbę dróg oraz stałą wyznaczoną przez Tymona. W następnych M wierszach następuje opis dróg w mieście Amelii i Tymona. Każdy opis składa się z pary dwóch liczb u i v oznaczających, że istnieje droga ze skrzyżowania u do skrzyżowania o numerze v.

Wyjście

Należy wypisać M wierszy na standardowe wyjście. W i-tym wierszu powinna znajdować się jedna liczba całkowita opisująca ile co najmniej razy i-ta droga musi zostać zwielokrotniona, aby liczba ścieżek ze szkoły do domu Amelii była podzielna przez K lub liczba  − 1 jeżeli to nie jest możliwe.

Ograniczenia

1 ≤ N, M ≤ 1 000 000, 2 ≤ K ≤ 10⁹. Można założyć, że graf na wejściu jest acykliczny i spójny, oraz że każda krawędź u, v podana na wejści spełnia warunek u < v.

Przykład

4 5 4
1 2
2 3
2 4
3 4
1 4

-1
2
2
2
2

Olga w ostatnim czasie zainteresowała się ogrodnictwem. Z tego powodu chciałaby kupić sobie działkę, na której mogłaby rozwijać swoje zainteresowanie. Udała się zatem do swojego znajomego Filipa, który zajmuje się sprzedażą ziemi. Filip przedstawił jej aktualną sytuację na rynku. Do dyspozycji jest powierzchnia o wymiarach N × M, podzielona na kwadraty o długości 1. Każdy kwadrat ma określoną żyzność, wyrażoną przez jedną liczbę całkowitą.

Olga chciałaby kupić działkę o polu powierzchni K (czyli taką, która jest złożona z dokładnie K dostępnych kwadratów). Ponadto, wybrana przez Olgę działka powinna być spójna. Dokładniej, z każdego wybranego kwadratu ziemi powinno dać się dostać do każdego innego, ale przechodzić można jedynie między kwadratami o sąsiadujących bokach. Dla przykładu, następujące wybory działki tworzą spójny obszar:

.##   ###  .##.
.#.   #.#  ##.#
.#.   ###  .###

Ale spójne nie są działki:

.#.  #.
...  .#
.##

Dodatkowo, wśród wszystkich możliwych wyborów działek Olga chciałaby wybrać taką, która ma największą sumaryczną żyzność. Filip powiedział Oldze, że sytuacja na rynku jest napięta, zatem nie powinna zwlekać z decyzją o zakupie. Pomóż jej i napisz program, który znajdzie działkę o największej sumarycznej żyzności.

Wejście

W pierwszym wierszu standardowego wejścia znajdują się trzy liczby całkowite podzielane pojedynczymi odstępami N, M, K oznaczające odpowiednio szerokość i wysokość ziemi oraz pole powierzchni szukanej działki. W następnych N wierszach znajdują się ciągi po M liczb całkowitych, określających żyzności poszczególnych kwadratów ziemi.

Wyjście

W jednym wierszu standardowego wyjścia należy wypisać jedną liczbę całkowitą oznaczającą maksymalną sumaryczną żyzność ziemi wśród wszystkich wyborów działki.

Ograniczenia

1 ≤ N, M ≤ 20, 1 ≤ K ≤ 12, wartość bezwzględna żyzności każdego kwadratu nie przekracza 10⁹.

Przykład

3 3 3
1 3 -5 
-2 7 -3 
1 -1 8 

14

Ryszard bardzo lubi trójkąty równoboczne. W tym roku dostał na urodziny od rodziców zestaw wielu podłużnych patyczków o długościach będącymi dodatnimi liczbami naturalnymi. Od tej pory jedyna rzecz, którą robi w wolnym czasie, to układanie z tych patyczków trójkątów równobocznych! Naszła go ochota, żeby ułożyć trójkąt równoboczny, którego pole wynosi co najmniej N centymetrów kwadratowych. Z drugiej strony, chciałby to zrobić przy pomocy możliwie krótkich patyczków (wtedy dłuższe zostaną na jakiś ciekawszy trójkąt). Pomóż mu i powiedz, ile co najmniej centymetrów muszą mieć patyczki, żeby ułożyć trójkąt równoboczny spełniający oczekiwania Ryszarda.

Wejście

W pierwszym i jedynym wierszu standardowego wejścia znajduje się jedna liczba naturalna N.

Wyjście

W pierwszym i jedynym wierszu standardowego wyjścia powinna się znaleźć jedna dodatnia całkowita liczba oznaczająca długość w centymetrach najkrótszych patyczków, z jakich da się ułożyć trójkąt równoboczny o polu co najmniej N.

Ograniczenia

0 ≤ N ≤ 10¹⁸.

Przykład

7

5