0190. Шары кругом

Имя входного файла:	input.txt
Имя выходного файла:	output.txt
Ограничение по времени:	250 ms
Ограничение по памяти:	16 megabytes

Мальчик Петя любит играть с шарами. У него много разных шаров, и он составляет из них разные узоры. Однажды, он выложил N шаров по окружности. Теперь его очень интересует вопрос, сколько способов выбрать K подряд идущих шаров так, чтобы они все были разного цвета. Помогите, пожалуйста, Пете.

Формат входного файла

В первой строке записаны целые числа N и K (1 ≤ K ≤ N ≤ 60000). Во второй строке записаны N чисел - цвета шаров на окружности. Шары перечислены, начиная с ближайшего к Петиному столу, по часовой стрелке. Цвет указан в формате RGB, т.е. числом от 0 до 2²⁴-1.

Формат выходного файла

Выведите ответ на задачу.

Пример:

input.txt	output.txt
10 3 0 1 2 0 2 1 3 4 0 2	8

Источник: Petrozavodsk Winter 2003. SaratovSU #3 Training Contest, Wednesday, February 05

Обсудить       Отправить решение



Версия для печати