Страница: 1 Отображать по:
#3334
Проходной балл
  

Одна Очень Престижная Олимпиада, как и все престижные олимпиады в последнее время, состоит из двух туров - регионального и заключительного. Правила отбора во второй тур (заключительный этап) просты:

  1. Призеры олимпиады прошлого года приглашаются на заключительный этап вне зависимости от набранных ими в первом туре баллов.
  2. Все участники, набравшие не меньше баллов, чем установленный жюри проходной балл, проходят во второй тур.
  3. Если в каком-либо из регионов ни один участник по первым двум правилам во второй тур не прошел, то на заключительный этап приглашается участник из этого региона, набравший в нем максимальное количество баллов (это не касается регионов, от которых участников не было).
  4. На второй тур можно пригласить не более \(M\) участников.

Известно, что никакие два участника не набрали одинаковое количество баллов. По информации о результатах первого тура помогите жюри установить минимально возможный проходной балл, при котором все правила отбора будут выполнены.

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

В первой строке входного файла содержатся три целых числа \(N\), \(M\) и \(R\) - число участников первого тура, максимально возможное число участников второго тура и число регионов, из которых могли быть участники (\(1 \le M < N\)). Далее в \(N\) строках содержатся результаты каждого из участников. Каждая строка состоит из четырех целых чисел. Сначала идет \(id\) - уникальный идентификатор участника (\(1 \le id \le N\)), далее номер региона \(region\), в котором данный участник учится (\(1 \le region \le R\)), затем \(score\) - число баллов, набранных участником, четвертое число равно 1, если участник является призером олимпиады прошлого года, и 0 - в противном случае.

Гарантируется, что все идентификаторы участников различны, никакие два участника не набрали одинаковое число баллов, и выполнить все правила отбора возможно.

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

Выведите одно число - минимальный проходной балл, который можно установить.

Примечания

Тесты состоят из четырёх групп. Во всех тестах \(0 \le score \le 10^9\).

  1. Тест 1 из условия, оценивается в 0 баллов.
  2. В тестах этой группы все числа на входе не превосходят 1000. Эта группа оценивается в 30 баллов, при этом баллы начисляются только при прохождении всех тестов группы.
  3. В тестах этой группы \(1 \le R \le M \le 10\,000\), \(M < N \le 100\,000\). Эта группа также оценивается в 30 баллов, баллы начисляются только при прохождении всех тестов группы.
  4. В тестах этой группы, \(1 \le R \le M < N \le 100\,000\). Баллы за тесты этой группы начисляются только при прохождении всех тестов 1-й и 2-й групп. Каждый из тестов оценивается независимо от других.
Примеры
Входные данные
9 6 5
6 1 799 0
2 4 995 0
1 4 989 1
7 2 538 0
5 4 984 0
8 2 1000 0
3 2 998 0
4 2 823 1
9 1 543 0
Выходные данные
985
#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
#3337
Забор
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

На одну Очень Известную Планету упал метеорит. Метеорит в атмосфере распался на \(N\) кусков, каждый из которых упал в свою точку.

Чтобы куски метеорита не были испорчены любопытными туристами, для проведения научных исследований решили построить один забор, которым огородить не менее \(K\) кусков метеорита. Естественно, что забор должен быть минимально возможной длины, и внутри него должны оказаться любые \(K\) (или больше) кусков метеорита (кусок считается лежащим внутри забора как когда он лежит строго внутри, так и когда забор проходит непосредственно через него).

Конечно, ученые хотят огородить как можно больше кусков, но как всегда, все упирается в деньги. Главный бухгалтер решил составить такую таблицу: для каждого \(K\) от 1 до \(N\) определить, какой минимальной длины нужно построить забор, чтобы внутри него оказалось не менее \(K\) кусков метеорита. Помогите ему.

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

В первой строке входного файла записано единственное целое число \(N\). В каждой из следующих \(N\) строк записано по паре целых чисел, по модулю не превосходящих \(1\,000\) - координаты точек, куда упали куски метеорита. Никакие два куска не упали в одну и ту же точку.

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

Выведите \(N\) чисел, \(i\)-е (\(1 \le i \le N\)) должно быть равно минимальной длине забора, внутри которого окажется не менее \(K\) кусков метеорита. Выведенный ответ будет сравниваться с правильным с точностью до \(10^{-6}\).

Примечания

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

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

Примеры
Входные данные
4
0 0
0 1
1 0
1 1
Выходные данные
0.000000000
2.000000000
3.414213562
4.000000000
Входные данные
3
1 1
0 0
2 0
Выходные данные
0.000000000
2.828427125
4.828427125
Страница: 1 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест