Петя хочет повесить картину на стену. Для этого ему нужно просверлить в стене дырку, вбить в нее дюбель и вкрутить в него саморез. Петя покопался в кладовке и нашел n сверел и m дюбелей. Петя хочет найти сверло и дюбель одного радиуса. Однако, таких может не быть, в этом случае он хочет подобрать сверло и дюбель, чтобы разность их диаметров была как можно меньше. Помогите Пете.
В первой строке входного файла заданы целые числа n и m (1 ≤ n, m ≤ 105). Во второй строке заданы n целых чисел — диаметры сверел. В следующей строке заданы m целых чисел — диаметры дюбелей. Диаметры заданы в неубывающеам порядке, все диаметры — числа от 1 до 109)
Выведите минимальную возможную разницу диаметров сверла и дюбеля
3 2
1 8 15
5 6
2
3 3
1 3 5
3 4 6
0
В центре города Че есть пешеходная улица — одно из самых популярных мест для прогулок жителей города. По этой улице очень приятно гулять, ведь вдоль улицы расположено n забавных памятников.
Девочке Маше из города Че нравятся два мальчика из ее школы, и она никак не может сделать выбор между ними. Чтобы принять окончательное решение, она решила назначить обоим мальчикам свидание в одно и то же время. Маша хочет выбрать два памятника на пешеходной улице, около которых мальчики будут ее ждать. При этом она хочет выбрать такие памятники, чтобы мальчики не увидели друг друга. Маша знает, что из-за тумана мальчики увидят друг друга только в том случае, если они будут на расстоянии не более r метров. Маше заинтересовалась, а сколько способов есть выбрать два различных памятника для организации свиданий.
В первой строке входного файла находятся два целых числа n и r (2 ≤ n ≤ 300 000, 1 ≤ r ≤ 109) — количество памятников и максимальное расстояние, на котором мальчики могут увидеть друг друга.
Во второй строке задано n положительных чисел d1, ..., dn, где di — расстояние от i-го памятника до начала улицы. Все памятники находятся на разном расстоянии от начала улицы. Памятники приведены в порядке возрастания расстояния от начала улицы (1 ≤ d1 < d2 < ... < dn ≤ 109).
Выведите одно число — число способов выбрать два памятника для организации свиданий.
4 4
1 3 5 8
2
В приведенном примере Маша может выбрать памятники 1 и 4 или памятники 2 и 4.
Строка называется бинарной, если она состоит только из символов «0» и «1».
Строка v называется подстрокой строки w, если она имеет ненулевую длину, и ее можно прочитать, начиная с некоторой позиции, в строке w. Например, у строки «010» есть шесть подстрок: «0», «1», «0», «01», «10», «010». Две подстроки считаются различными, если их позиции вхождения различны. Другими словами, каждую подстроку нужно учитывать столько раз, сколько она встречается.
Дана бинарная строка s. Ваша задача — найти количество ее подстрок, содержащих ровно k единиц.
В первой строке записано единственное целое число k (0 ≤ k ≤ 106). Во второй строке записана непустая бинарная строка s. Длина s не превосходит 106 символов.
Выведите одно целое число — количество подстрок данной строки, содержащих ровно k символов «1».
1
1010
6
Всем известно, что корабль «Черная жемчужина» на самом деле существует. Долгое время им командовал всем извеcтный капитан Джек Воробей. И этот корабль, вместе со своим капитаном прошел огонь, воду и медные трубы. Так же учеными установлено, что «Черная жемчужина» является самым быстроходным кораблем в мире. Она даже быстрее, чем «Разящий» и «Летучий голландец», про который говорят, что он ходит быстрее ветра.
После ограбления сокровищницы на Исла де Муэрте на команду «Чёрной Жемчужины» легло проклятие, которое повлияло и на сам корабль: паруса корабля порвались, а само судно стал окружать жутковатый туман. Снять проклятие было достаточно сложно, и поэтому никто не стал этого делать.
В трюме корабля, на самой гнилой доске самой дальней стены, написана загадка, которая является ключом к снятию проклятия. Доска очень старая, и из-за этого некоторые буквы на ней стерлись. Согласно легендам, в загадке не было пробелов, то есть она выглядела как одно слово. Поскольку загадку восстановить уже нельзя, снять проклятие не представляется возможным. Однако, его можно попробовать смягчить.
Если верить Мудрецу, для смягчения проклятия нужно выбросить за борт большой мешок с золотом. За каждую подстроку слова-загадки, в которой, при каком-нибудь заполнении пропусков буквами, все буквы могли оказаться одинаковыми, в мешок необходимо положить одну монету.
Вам дана загадка, определите, сколько монет нужно выбросить за борт для смягчения проклятия.
Во входном файле дана строка, длина которой не превышает 106. Строка состоит из строчных латинских букв и знаков вопроса, обозначающих стертую букву (пропуск).
Выведите одно число — ответ на задачу.
ab?c
6
aa??b?c
19
Описанным в условии требованиям отвечают ровно шесть подстрок слова-загадки из первого примера: