Однажды Петя узнал очень важную последовательность из \(n\) чисел. Тщательно проанализировав ее, он обнаружил, что она является арифметической прогрессией. Чтобы не забыть он записал ее элементы на \(n\) карточках.
Но затем случилась неприятность. Не зная всю важность этой последовательности, его брат Вовочка взял еще \(n\) карточек и написал на них произвольные числа, а потом перемешал все \(2n\) карточек.
Теперь Петя хочет восстановить исходную последовательность по этим карточкам. К сожалению возможно, что это можно сделать несколькими способами, но Петю устроят любые \(n\) чисел, образующие арифметическую прогрессию.
Петя не может сделать это вручную, поэтому обратился к вам за помощью.
Напомним что последовательность \(a_1, a_2, \ldots, a_n\) называется арифметической прогрессией, если \(a_i = a_{i-1} + d\) для всех \(i\) от 2 до \(n\) и некоторого \(d\). Число \(d\) называется разностью арифметической прогрессии.
В первой строке входного файла находится целое число \(n\) (\(1 \le n \le 100\,000\)). В следующей строке находится \(2n\) целых чисел по модулю не превосходящих \(10^9\) — числа, написанные на карточках, перечисленные в произвольном порядке. Гарантируется, что можно выбрать \(n\) из них так, чтобы они образовывали арифметическую прогрессию.
В первой строке выходного файла выведите \(a_1\) и \(d\) — первый элемент и разность найденной арифметической прогрессии. Если \(d = 0\), число \(a_1\) должно встречаться среди заданных чисел \(n\) раз.
Если существует несколько решений, выведите любое.
Словарь задан массивом отсортированных в лексикографическом порядке строк. Напишите программу эффективного поиска слова в словаре.
На вход программе сначала подается искомое слово, во второй строке — число n (1 <= n <= 100000) — количество слов в словаре. В следующих n строках расположены слова словаря, по одному слову в строке. Все слова состоят только из строчных латинских букв, слова упорядочены по алфавиту (расположены в лексикографическом порядке).
Длина слов не превосходит 20. Пустых слов нет.
Выведите YES или NO в зависимости от того, есть искомое слово в словаре или нет.
abba 4 a ab aba baba
NO
Юные физики Евгений и Родион очень любят музыку, кроме того Родион умеет исполнять любое произведение при помощи бутылок с водой. У них есть \(N\) бутылок бесконечной вместимости. В \(i\)-ой бутылке уже содержится \(a_i\) мл воды. Также у них есть бочонок с \(L\) мл воды, из которого можно переливать любой имеющийся объём воды в любую бутылку. Выливать воду из бутылок нельзя. После того как Евгений заканчивает все переливания, он больше не притрагивается к бутылкам, а Родион начинает играть мелодию.
Мелодия состоит из \(M\) нот \(b_1, b_2, \dots, b_M\), которые обязательно надо исполнять в заданном порядке. Ноту \(b_i\) Родион сможет сыграть, если найдется бутылка с \(b_i\) мл воды. Если очередную ноту он исполнить не может, то сильно огорчается и перестает играть. Евгений стремится наполнить бутылки таким образом, чтобы Родион играл как можно дольше. Помогите ребятам узнать, какое максимальное количество начальных нот данной мелодии сможет сыграть Родион при оптимальных действиях Евгения.
В первой строке входного файла содержатся три целых числа \(N\), \(M\), \(L\) - количество бутылок, длина мелодии и объем бочонка соответственно. Во второй строке через пробел расположены \(N\) чисел \(a_i\) (\(i = 1, 2, \dots N\)) - количество мл в \(i\)-ой бутылке. В третьей строке - \(M\) чисел \(b_i\) (\(i = 1, 2, \dots M\)) - последовательность нот в мелодии (каждая музыкальная нота обозначается своим числом, одинаковые ноты - одинаковыми числами). Все числа целые и неотрицательные.
Выведите единственное число - максимальное количество начальных нот мелодии, которые можно сыграть, оптимально заполнив бутылки.
Тесты состоят из четырёх групп.
6 8 179 4 9 23 15 43 7 3 10 14 7 3 8 7 3
0
5 8 5 5 3 8 14 1 10 7 3 7 12 3 3 6
4
2 2 4 6 13 8 10
1
Одна Очень Престижная Олимпиада, как и все престижные олимпиады в последнее время, состоит из двух туров - регионального и заключительного. Правила отбора во второй тур (заключительный этап) просты:
Известно, что никакие два участника не набрали одинаковое количество баллов. По информации о результатах первого тура помогите жюри установить минимально возможный проходной балл, при котором все правила отбора будут выполнены.
В первой строке входного файла содержатся три целых числа \(N\), \(M\) и \(R\) - число участников первого тура, максимально возможное число участников второго тура и число регионов, из которых могли быть участники (\(1 \le M < N\)). Далее в \(N\) строках содержатся результаты каждого из участников. Каждая строка состоит из четырех целых чисел. Сначала идет \(id\) - уникальный идентификатор участника (\(1 \le id \le N\)), далее номер региона \(region\), в котором данный участник учится (\(1 \le region \le R\)), затем \(score\) - число баллов, набранных участником, четвертое число равно 1, если участник является призером олимпиады прошлого года, и 0 - в противном случае.
Гарантируется, что все идентификаторы участников различны, никакие два участника не набрали одинаковое число баллов, и выполнить все правила отбора возможно.
Выведите одно число - минимальный проходной балл, который можно установить.
Тесты состоят из четырёх групп. Во всех тестах \(0 \le score \le 10^9\).
9 6 5 6 1 799 0 2 4 995 0 1 4 989 1 7 2 538 0 5 4 984 0 8 2 1000 0 3 2 998 0 4 2 823 1 9 1 543 0
985
В одной Очень Известной Летней Школе наиболее популярным видом спорта является волейбол. Для каждого из \(N\) школьников известно его умение играть в волейбол. Перед началом занятий школьников необходимо распределить между двумя тренерами.
Тренеры сочли справедливым следующий алгоритм разделения на две группы. Сначала они выбирают два целых числа \(p\), \(q\) (\(0 < p \le q \le N\)). Затем первый берет себе \(p\) лучших школьников, после чего оба тренера, начиная со второго, берут по очереди по \(q\) лучших школьников из оставшихся, пока их количество не меньше \(q\). В конце очередной тренер просто берет всех оставшихся.
Оба тренера заинтересованы в наиболее справедливом распределении школьников между группами. Поэтому они стремятся найти такие \(p\) и \(q\), чтобы разница суммарных умений между двумя группами школьников оказалась минимальной. При этом, вообще говоря, не обязательно, чтобы количество школьников в каждой из групп было одинаковым.
Помогите тренерам подобрать такие "справедливые" значения \(p\) и \(q\) (\(0 < p \le q \le N\)), при которых разница в суммарных умениях образованных групп школьников по абсолютной величине будет минимальна.
В первой строке входного файла записано единственное целое число \(N\). Во второй строке содержатся \(N\) неотрицательных целых чисел, не превосходящих \(10^9\) - умения школьников играть в волейбол.
Выведите искомые целые значения \(p\) и \(q\) (\(0 < p \le q \le N\)). Если искомых пар несколько, то выведите любую из них.
Тесты состоят из четырёх групп.
8 5 3 3 3 3 3 7 1
1 2