Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
2273. Гипершашки
Комбинаторика, теория ПойаСканирование, метод двух указателей
Олимпиадные задачи на русском языке
| 01/02/2016 | Региональный этап олимпиады школьников по информатике. II тур. (6) |
| 03/10/2022 | «Базовая олимпиадная подготовка» (second level) - Метод двух указателей (проводит novink ) (D) |
Ограничения: время – 1s/2s, память – 256MiB Ввод: game.in или стандартный ввод Вывод: game.out или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Андрей работает судьей на чемпионате по гипершашкам. В каждой игре в гипершашки участвует три игрока. По ходу
игры каждый из игроков набирает некоторое положительное целое число баллов. Если после окончания игры первый игрок
набрал `a` баллов, второй – `b`, а третий – `c`, то говорят, что игра закончилась со счетом `a:b:c`.
Андрей знает, что правила игры гипершашек устроены таким образом, что в результате игры баллы любых двух игроков
различаются не более чем в `k` раз.
После матча Андрей показывает его результат, размещая три карточки с очками игроков на специальном табло.
Для этого у него есть набор из `n` карточек, на которых написаны числа `x_1,\ x_2,\ …,\ x_n`. Чтобы выяснить,
насколько он готов к чемпионату, Андрей хочет понять, сколько различных вариантов счета он сможет показать на
табло, используя имеющиеся карточки.
Требуется написать программу, которая по числу `k` и значениям чисел на карточках, которые имеются у Андрея,
определяет количество различных вариантов счета, которые Андрей может показать на табло.
Формат входного файла
Первая строка входного файла содержит два целых числа: `n` и `k` (`3 ≤ n ≤ 100 000`, `1 ≤ k ≤ 10^9`).
Вторая строка входного файла содержит n целых чисел `x_1,\ x_2,\ …,\ x_n` (`1 ≤ x_i ≤ 10^9`).
Формат выходного файла
Выходной файл должен содержать одно целое число - искомое количество различных вариантов счета.
Пример ввода
5 2 1 1 2 2 3
Пример вывода
9
Пояснение к примеру
В приведенном примере Андрей сможет показать следующие варианты счета: 1:1:2, 1:2:1,
2:1:1, 1:2:2, 2:1:2, 2:2:1, 2:2:3, 2:3:2, 3:2:2. Другие тройки чисел, которые
можно составить с использованием имеющихся карточек, не удовлетворяют заданному
условию, что баллы любых двух игроков различаются не более чем в `k\ =\ 2` раза.
Описание подзадач и системы оценивания
В этой задаче четыре подзадачи. Баллы за подзадачу начисляются только в случае, если все
тесты для данной подзадачи пройдены.
Внимание! Тест из примера не подходит под ограничения для подзадач 1 и 3, но решение
принимается на проверку только в том случае, если оно выводит правильный ответ на тесте
из примера. Решение должно выводить правильный ответ на тест, даже если оно рассчитано
на решение только каких-либо из подзадач 1 и 3.
Подзадача 1 (15 баллов)
`3 ≤ n ≤ 100 000`, `k\ =\ 1`, `1 ≤ x_i ≤ 100 000`
Подзадача 2 (23 балла)
`3 ≤ n ≤ 100`, `1 ≤ k ≤ 100`, `1 ≤ x_i ≤ 100`
Подзадача 3 (30 баллов)
`3 ≤ n ≤ 100 000`, `1 ≤ k ≤ 10^9`, `1 ≤ x_i ≤ 10^9`, все `x_i` различны.
Подзадача 4 (32 балла)
`3 ≤ n ≤ 100 000`, `1 ≤ k ≤ 10^9`, `1 ≤ x_i ≤ 10^9`
По запросу сообщается результат окончательной проверки на каждом тесте.
Источник: региональный этап Всероссийской олимпиады по информатике 2015/2016, http://neerc.ifmo.ru/school/ 