Олимпиадный тренинг

Задача . Running Laps


Задача

Темы: жадные алгоритмы

Фермер Джон заставил N своих коров (1 <= N <= 100,000) бежать L раз по круглому треку длиной C. Все коровы начинают в одной точке трека и бегут с разными скоростями. Гонка заканчивается, когда самая быстрая корова достигнет финиша (пробежав общее расстояние LC).
ФД заметил несколько случаев, когда одна корова обгоняла другую, и хочет узнать, сколько раз такой обгон случился за все время гонки.
Более строго, событие для подсчета определяется парой коров (x,y) и временем t (меньшим или равным времени конца гонки), когда корова X обгоняла корову y в момент времени t. Помогите ФД подсчитать общее количество таких обгонов за все время гонки.
PROBLEM NAME: running
Формат входных данных
* Строка 1: Три разделенных пробелами целых числа: N, L, C. (1 <= L,C <= 25,000).
* Строки 2..1+N: Строка i+1 содержит скорость коровы i, целое число в диапазоне 1..1,000,000.
Формат выходных данных
* Строка 1: Общее количество обгонов во время гонки.
Примечание
Гонка длится 2 единицы времени, поскольку именно столько времени нужно самой быстрой корове (с номером 2) добраться до финиша. За это время случится 4 обгона: корова 2 обгонит коров 1 и 4, и корова 3 обгонит коров 1 и 4.
Примеры
№Входные данныеВыходные данные
1 
4 2 100
20
100
70
1
 
4
Статистика успешных решений по компиляторам
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет