Для переноски бревна нужно выбрать двух человек, разница в росте которых не превышает \(M\).
Даны значения роста \(N\) человек. Определите количество способов выбрать двоих из них так, чтобы разница их роста была не больше \(M\).
Программа получает на вход числа \(N\) и \(M\) в первой строке (\(1\le N\le 10^5\), \(M\ge 0\)), во второй строке записано \(N\) натуральных чисел через пробел — значения роста.
Программа должна вывести одно целое число — искомое количество способов.
| Ввод | Вывод |
|---|---|
4 2 |
4 |
Дана строка, состоящая только из символов “0” и “1”. Найдите количество непустых подстрок данной строки, содержащих ровно \(k\) единиц.
Первая строка входных данных содержит целое число \(k\) (\(0\le k\le 10^6\)). Во второй строке записана непустая строка \(s\), длина которой не превосходит \(10^6\) символов.
Программа должна вывести одно целое число — количество подстрок данной строки, содержащих ровно \(k\) единиц.
| Ввод | Вывод |
|---|---|
1 |
6 |
Дана строка длиной не более \(10^6\) символов, содержащая только строчные латинские буквы и знаки вопроса. Определите, сколько существует подстрок данной строки, которые при некоторой замены знаков вопроса все буквы были бы одинаковыми.
| Ввод | Вывод |
|---|---|
ab?c |
6 |
aa??b?c |
19 |
Объяснение первого примера. Описанному условию отвечают четыре подстроки из одного символа,
подстрока b? и подстрока ?c.
Как показывает опыт, для создания успешной футбольной команды важны не только умения отдельных её участников, но и сплочённость команды в целом. Характеристикой умения игрока является показатель его профессионализма (ПП). Команда является сплочённой, если ПП каждого из игроков не превосходит суммы ПП любых двух других (в частности, любая команда из одного или двух игроков является сплоченной). Перед тренерским составом молодёжной сборной Москвы была поставлена задача сформировать сплочённую сборную с максимальной суммой ПП игроков (ограничений на количество игроков в команде нет).
Ваша задача состоит в том, чтобы помочь сделать правильный выбор из \(N\) человек, для каждого из которых известен его ПП.
В первой строке входных данных записано целое число \(N\) (\(0\le N\le 30000\)). В последующих \(N\) строках записано по одному целому числу \(P_i\) (\(0\le P_i\le 60000\)), представляющему собой ПП соответствующего игрока.
В первой строке через пробел выведите число игроков, отобранных в команду, и их суммарный ПП. В последующих строках выведите номера игроков, вошедших в команду, в произвольном порядке — по одному числу в строке. Нумерация игроков должна соответствовать порядку перечисления игроков во входных данных. Если ответов несколько, выведите любой из них.
| Ввод | Вывод |
|---|---|
4 |
3 11 |
5 |
2 120 |
Даны \(N\) отрезков. Определите, сколькими способами можно выбрать из них три отрезка так, чтобы из них можно было составить невырожденный треугольник. Решение должно иметь сложность \(O(n^2)\).
Первая строка входных данных содержит число \(N\) (\(1\le N\le 3000\)). Во второй строке записано \(N\) натуральных чисел не превосходящих \(10^9\) — длины отрезков.
Программа должна вывести единственное число: искомое количество способов.
| Ввод | Вывод |
|---|---|
4 |
2 |
Аллея состоит из \(N\) посаженных в один ряд деревьев, каждое одного из \(K\) видов. Решено было вырубить аллею, но сохранив при этом часть деревьев. Деревья, которые не будут вырублены, должны идти подряд, причем должно остаться хотя бы по одному дереву каждого из \(K\) видов. Определите, какое наименьшее число деревьев необходимо сохранить.
В первой строке входных данных даны два числа \(N\) и \(K\) (\(1 \le K\le N \le 250000\)). Во второй строке записаны \(N\) чисел, $i$-е число второй строки задает вид $i$-го дерева аллеи. Гарантируется, что присутствует хотя бы одно дерево каждого цвета.
Программа должна вывести два числа: номер первого и последнего дерева, которые нужно оставить на аллее. Если ответов несколько, выведите любой из них.
| Ввод | Вывод |
|---|---|
5 3 |
2 4 |
6 4 |
2 6 |