| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 512 MB | 9 | 3 | 3 | 42.857% |
Андрей работает судьей на чемпионате по гипершашкам. В каждой игре в гипершашки участвует три игрока. По ходу игры каждый из игроков набирает некоторое положительное целое число баллов. Если после окончания игры первый игрок набрал a баллов, второй — b, а третий c, то говорят, что игра закончилась со счетом a:b:c.
Андрей знает, что правила игры гипершашек устроены таким образом, что в результате игры баллы любых двух игроков различаются не более чем в k раз
После матча Андрей показывает его результат, размещая три карточки с очками игроков на специальном табло. Для этого у него есть набор из n карточек, на которых написаны числа x1, x2, …, xn. Чтобы выяснить, насколько он готов к чемпионату, Андрей хочет понять, сколько различных вариантов счета он сможет показать на табло, используя имеющиеся карточки.
Требуется написать программу, которая по числу k и значениям чисел на карточках, которые имеются у Андрея, определяет количество различных вариантов счета, которые Андрей может показать на табло.
Первая строка входного файла содержит два целых числа: n и k (3 ≤ n ≤ 100 000, 1 ≤ k ≤ 109).
Вторая строка входного файла содержит n целых чисел x1, x2, …, xn (1 ≤ xi ≤ 109).
Выходной файл должен содержать одно целое число — искомое количество различных вариантов счета.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 15 | 3 ≤ n ≤ 100 000, k = 1, 1 ≤ xi ≤ 100 000 |
| 2 | 23 | 3 ≤ n ≤ 100, 1 ≤ k ≤ 100, 1 ≤ xi ≤ 100 |
| 3 | 30 | 3 ≤ n ≤ 100 000, 1 ≤ k ≤ 109, 1 ≤ xi ≤ 109, все xi различны |
| 4 | 32 | 3 ≤ n ≤ 100 000, 1 ≤ k ≤ 109, 1 ≤ xi ≤ 109 |
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 раза.
Olympiad > Russian Olympiad in Informatics > Russian Olympiad in Informatics Regional > Russian Olympiad in Informatics Regional 2016 6번