Страница: 1 Отображать по:
#3335
Лыжные гонки
  

Во время лыжных соревнований \(N\) спортсменов стартуют с интервалом в 1 минуту. Скорость каждого лыжника на дистанции постоянна: \(i\)-й лыжник преодолевает 1 км за \(w_i\) минут. Длина трассы равна \(L\) км. Считается, что \(i\)-й лыжник обогнал \(j\)-го (совершил обгон), если он стартовал позже \(j\)-го, а пришёл к финишу раньше него. Подсчитайте суммарное число совершённых во время гонки обгонов.

Входные данные

Первая строка входного файла содержит два целых числа \(N\) и \(L\). Во второй строке через пробел расположены \(N\) целых чисел \(w_i\).

Выходные данные

Выведите единственное число - суммарное количество обгонов.

Примечания

Во всех тестах \(1 \le L \le 10^9\), \(1 \le w_i \le 10^9\) при \(i = 1, 2, \dots, N\). Тесты состоят из трёх групп.

  1. Тесты 1 и 2 из условия, оцениваются в 0 баллов.
  2. В тестах этой группы \(1 \le N \le 10\,000\), эти тесты оцениваются в 50 баллов, при этом баллы начисляются только при прохождении всех тестов группы.
  3. Off-line группа, \(1 \le N \le 500\,000\). При этом баллы за тесты этой группы ставятся только тогда, когда программа проходит все тесты предыдущей группы. Если программа не проходит хотя бы один из тестов группы 1, то баллы за тесты группы 2 не ставятся. Тесты этой группы оцениваются независимо друг от друга.
Примеры
Входные данные
2 1
20 19
Выходные данные
0
Входные данные
5 3
3 6 2 4 1
Выходные данные
7
#3336
Волейбол
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

В одной Очень Известной Летней Школе наиболее популярным видом спорта является волейбол. Для каждого из \(N\) школьников известно его умение играть в волейбол. Перед началом занятий школьников необходимо распределить между двумя тренерами.

Тренеры сочли справедливым следующий алгоритм разделения на две группы. Сначала они выбирают два целых числа \(p\), \(q\) (\(0 < p \le q \le N\)). Затем первый берет себе \(p\) лучших школьников, после чего оба тренера, начиная со второго, берут по очереди по \(q\) лучших школьников из оставшихся, пока их количество не меньше \(q\). В конце очередной тренер просто берет всех оставшихся.

Оба тренера заинтересованы в наиболее справедливом распределении школьников между группами. Поэтому они стремятся найти такие \(p\) и \(q\), чтобы разница суммарных умений между двумя группами школьников оказалась минимальной. При этом, вообще говоря, не обязательно, чтобы количество школьников в каждой из групп было одинаковым.

Помогите тренерам подобрать такие "справедливые" значения \(p\) и \(q\) (\(0 < p \le q \le N\)), при которых разница в суммарных умениях образованных групп школьников по абсолютной величине будет минимальна.

Входные данные

В первой строке входного файла записано единственное целое число \(N\). Во второй строке содержатся \(N\) неотрицательных целых чисел, не превосходящих \(10^9\) - умения школьников играть в волейбол.

Выходные данные

Выведите искомые целые значения \(p\) и \(q\) (\(0 < p \le q \le N\)). Если искомых пар несколько, то выведите любую из них.

Примечания

Тесты состоят из четырёх групп.

  1. Тест 1, из условия, оценивается в 0 баллов.
  2. В тестах этой группы \(2 \le N \le 300\). Эта группа оценивается в 30 баллов, баллы начисляются только при прохождении всех тестов группы.
  3. В тестах этой группы \(2 \le N \le 2\,000\). Эта группа также оценивается в 30 баллов, они начисляются только при прохождении всех тестов группы.
  4. Offline-группа, \(1 \le N \le 100\,000\). Баллы за тесты этой группы начисляются только при прохождении всех тестов 1-й и 2-й групп. Тесты этой группы оцениваются независимо друг от друга.

Примеры
Входные данные
8
5 3 3 3 3 3 7 1
Выходные данные
1 2
Страница: 1 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест