В центре города Че есть пешеходная улица - одно из самых популярных мест для прогулок жителей города. По этой улице очень приятно гулять, ведь вдоль улицы расположено \(n\) забавных памятников.
Девочке Маше из города Че нравятся два мальчика из ее школы, и она никак не может сделать выбор между ними. Чтобы принять окончательное решение, она решила назначить обоим мальчикам свидание в одно и то же время. Маша хочет выбрать два памятника на пешеходной улице, около которых мальчики будут ее ждать. При этом она хочет выбрать такие памятники, чтобы мальчики не увидели друг друга. Маша знает, что из-за тумана мальчики увидят друг друга только в том случае, если они будут на расстоянии не более \(r\) метров.
Маше заинтересовалась, а сколько способов есть выбрать два различных памятника для организации свиданий.
В первой строке входного файла находятся два целых числа \(n\) и \(r\) (\(2 \le n \le 300\,000\), \(1 \le r \le 10^9\)) - количество памятников и максимальное расстояние, на котором мальчики могут увидеть друг друга.
Во второй строке задано \(n\) положительных чисел \(d_1, \ldots, d_n\), где \(d_i\) - расстояние от \(i\)-го памятника до начала улицы. Все памятники находятся на разном расстоянии от начала улицы. Памятники приведены в порядке возрастания расстояния от начала улицы (\(1 \le d_1 < d_2 < \ldots < d_n \le 10^9\)).
Выведите одно число - число способов выбрать два памятника для организации свиданий.
Примичание
В первом примере Маша может выбрать памятники под номерами 1 и 4 или памятники 2 и 4.
| Ввод | Вывод |
|---|---|
4 4 1 3 5 8 |
2 |
2 4 1 5 |
0 |
Глеб обожает шоппинг. Как-то раз он загорелся идеей подобрать себе майку и штаны так, чтобы выглядеть в них максимально стильно. В понимании Глеба стильность одежды тем больше, чем меньше разница в цвете элементов его одежды.
В наличии имеется \(N\) (1 ≤ \(N\) ≤ 100 000) маек и \(M\) (1 ≤ \(M\) ≤ 100 000) штанов, про каждый элемент известен его цвет (целое число от 1 до 10 000 000). Помогите Глебу выбрать одну майку и одни штаны так, чтобы разница в их цвете была как можно меньше.
Сначала вводится информация о майках: в первой строке целое число N (1 ≤ N ≤ 100 000) и во второй N целых чисел от 1 до 10 000 000 — цвета имеющихся в наличии маек. Гарантируется, что номера цветов идут в возрастающем порядке (в частности, цвета никаких двух маек не совпадают).
Далее в том же формате идёт описание штанов: их количество M (1 ≤ M ≤ 100 000) и в следующей строке M целых чисел от 1 до 10 000 000 в возрастающем порядке — цвета штанов.
Выведите пару неотрицательных чисел — цвет майки и цвет штанов, которые следует выбрать Глебу. Если вариантов выбора несколько, выведите любой из них.
| Ввод | Вывод |
|---|---|
2 3 4 3 1 2 3 |
3 3 |
2 4 5 3 1 2 3 |
4 3 |
Глеб обожает шоппинг. Как-то раз он загорелся идеей подобрать себе кепку, майку, штаны и ботинки так, чтобы выглядеть в них максимально стильно. В понимании Глеба стильность одежды тем больше, чем меньше разница в цвете элементов его одежды.
В наличии имеется \(N\)1 кепок, \(N\)2 маек, \(N\)3 штанов и \(N\)4 пар ботинок (1 ≤ \(N\)\(i\) ≤ 100 000). Про каждый элемент одежды известен его цвет (целое число от 1 до 100 000). Комплект одежды — это одна кепка, майка, штаны и одна пара ботинок. Каждый комплект характеризуется максимальной разницей между любыми двумя его элементами. Помогите Глебу выбрать максимально стильный комплект, то есть комплект с минимальной разницей цветов.
Для каждого типа одежды i (i = 1, 2, 3, 4) сначала вводится количество Ni элементов одежды этого типа, далее в следующей строке — последовательность из Ni целых чисел, описывающих цвета элементов. Все четыре типа подаются на вход последовательно, начиная с кепок и заканчивая ботинками. Все вводимые числа целые, положительные и не превосходят 100 000.
Выведите четыре целых числа — цвета соответственно для кепки, майки, штанов и ботинок, которые должен выбрать Глеб из имеющихся для того, чтобы выглядеть наиболее стильно. Если ответов несколько, выведите любой.
| Ввод | Вывод |
|---|---|
3 1 2 3 2 1 3 2 3 4 2 2 3 |
3 3 3 3 |
1 5 4 3 6 7 10 4 18 3 9 11 1 20 |
5 6 9 20 |
Как показывает опыт, для создания успешной футбольной команды важны не только умения отдельных её участников, но и сплочённость команды в целом. Характеристикой умения игрока является показатель его профессионализма (ПП). Команда является сплочённой, если ПП каждого из игроков не превосходит суммы ПП любых двух других (в частности, любая команда из одного или двух игроков является сплоченной). Перед тренерским составом молодёжной сборной Москвы была поставлена задача сформировать сплочённую сборную с максимальной суммой ПП игроков (ограничений на количество игроков в команде нет).
Ваша задача состоит в том, чтобы помочь сделать правильный выбор из \(N\) человек, для каждого из которых известен его ПП.
В первой строке входного файла записано целое число \(N\) (\(1 \le N \le 30\,000\)). В последующих \(N\) строках записано по одному целому числу \(P_i\) (\(0 \le P_i \le 60\,000\)), представляющему собой ПП соответствующего игрока.
В первой строке через пробел выведите число игроков, отобранных в команду, и их суммарный ПП. В последующих строках выведите номера игроков, вошедших в команду, в произвольном порядке — по одному числу в строке. Нумерация игроков должна соответствовать порядку перечисления игроков во входном файле. Если ответов несколько, выведите любой из них.
| Ввод | Вывод |
|---|---|
4 1 5 3 3 |
3 11 3 4 2 |
5 100 20 20 20 20 |
2 120 2 1 |
Дядя Фёдор, кот Матроскин и Шарик решили обновить забор вокруг своего сада в Простоквашино. Матроскин и Шарик, недолго думая, вкопали \(N\) столбов вдоль одной из сторон участка. Это очень сильно расстроило Дядю Фёдора, так как его друзья забыли о самом главном — калитка должна находиться именно на этой стороне, и для неё необходимо было оставить проём шириной как минимум \(W\). Теперь им придётся выкапывать некоторые столбы.
Чтобы работа не пропадала даром, выкопать надо как можно меньше столбов. Помогите Дяде Фёдору определить, какие именно столбы надо выкопать. После выкапывания столбов должен найтись промежуток (между двумя оставшимися столбами, или между оставшимся столбом и концом стороны участка, или между двумя концами стороны участка) ширины больше или равной \(W\).
Первая строка содержит два целых числа \(N\) и \(W\) — количество вкопанных столбов и минимально необходимую ширину проёма для калитки соответственно. Гарантируется, что \(0 \le N \le 30000\) и что \(0 \le W \le 60000\).
Будем считать, что вдоль интересующей нас стороны участка введена ось координат. Во второй строке входного файла находятся два числа \(L\) и \(R\) — координаты левого и правого конца этой стороны \((L \lt R)\). Далее следуют \(N\) чисел — координаты вкопанных столбов. Все координаты (включая \(L\) и \(R\)) — различные целые числа, по модулю не превосходящие \(30000\). Гарантируется, что все столбы вкопаны между левым и правым концами стороны.
В первой строке выходного файла должно быть минимальное число столбов, которые надо выкопать. Далее должны следовать номера этих столбов. Столбы нумеруются в том порядке, как они указаны во входном файле, начиная с 1.
Если решений несколько, то вы можете вывести любое. Если решения нет, то выведите в выходной файл одну строку, содержащую число \(-1\).
| Ввод | Вывод |
|---|---|
3 2 2 6 3 4 5 |
1 2 |
3 2 1 6 4 3 5 |
0 |
3 5 1 7 5 3 4 |
3 2 1 3 |
Студенты одного из вузов спроектировали робота для частичной автоматизации процесса сборки авиационного двигателя.
В процессе сборки двигателя могут встречаться операции 26 типов, которые обозначаются строчными буквами латинского алфавита. Процесс сборки состоит из \(N\) операций.
Предполагается использовать робота один раз для выполнения части подряд идущих операций из процесса сборки.
Память робота состоит из \(K\) ячеек, каждая из которых содержит одну операцию. Операции выполняются последовательно, начиная с первой, в том порядке, в котором они расположены в памяти. Выполнив последнюю из них, робот продолжает работу с первой. Робота можно остановить после любой операции. Использование робота экономически целесообразно, если он выполнит хотя бы \(K\) + 1 операцию.
Требуется написать программу, которая по заданному процессу сборки определит количество экономически целесообразных способов использования робота.
В первой строке входного файла записано число \(K\gt 0\) — количество операций, которые можно записать в память робота.
Вторая строка состоит из \(N\gt K\) строчных латинских букв, обозначающих операции - процесс сборки двигателя. Операции одного и того же типа обозначаются одной и той же буквой.
Выходной файл должен содержать единственное целое число — количество экономически целесообразных способов использования робота.
| Ввод | Вывод |
|---|---|
2 zabacabab |
5 |
2 abc |
0 |
В парке города Питсбурга есть чудесная аллея, состоящая из \( N \) посаженных в один ряд деревьев, каждое одного из \( K \) сортов. В связи с тем, что Питсбург принимает открытый чемпионат Байтландии по программированию, было решено построить огромную арену для проведения соревнований. Так, согласно этому плану вся аллея подлежала вырубке. Однако министерство деревьев и кустов воспротивилось этому решению, и потребовало оставить некоторые из деревьев в покое. Согласно новому плану строительства все деревья, которые не будут вырублены, должны образовывать один непрерывный отрезок, являющийся подотрезком исходного. Каждого из \( K \) видов деревьев требуется сохранить хотя бы по одному экземпляру. На вас возложена задача найти отрезок наименьшей длины, удовлетворяющий указанным ограничениям.
В первой строке входного файла находятся два числа \(N\) и \(K\) (\(1\le N, K\le 250000\)). Во второй строке входного файла следуют \(N\) чисел (разделенных пробелами), \(i\)-ое число второй строки задает цвет \(i\)-ого слева дерева в аллее. Гарантируется, что присутствует хотя бы одно дерево каждого цвета.
В выходной файл выведите два числа, координаты левого и правого концов отрезка минимальной длины, удовлетворяющего условию. Если оптимальных ответов несколько, выведите любой.
| Ввод | Вывод |
|---|---|
5 3 1 2 1 3 2 |
2 4 |
6 4 2 4 2 3 3 1 |
2 6 |