Codeforces Round 880 (Div. 1) |
---|
Закончено |
Для участия в лотерее пришли $$$n$$$ человек, пронумерованных от $$$1$$$ до $$$n$$$. Каждый получил билет с целым числом от $$$0$$$ до $$$m$$$.
В лотерее равновероятно вытягивается одно целое целевое число от $$$0$$$ до $$$m$$$. Победителями объявляются $$$k$$$ билетов (или меньше, если участников недостаточно) с числами, наиболее близкими к целевому. В случае ничьей победителем объявляется билет, принадлежащий человеку с меньшим номером.
Байтек решил принять в ней участие. Он знает значения на билетах всех предыдущих участников. Он может выбрать любое значение на своем билете, но, к сожалению, поскольку он получил его последним, номер Байтека равен $$$n + 1$$$.
Байтек хочет выиграть в лотерею. Таким образом, он хочет узнать, какое число он должен выбрать, чтобы максимизировать шансы на выигрыш. Он хочет узнать наименьшее целое число в случае, если таких целых чисел много. Ваша задача — найти число и рассчитать шансы на выигрыш.
В первой строке входных данных находятся целые числа $$$n$$$, $$$m$$$ и $$$k$$$ ($$$1 \leq n \leq 10^6$$$, $$$0 \leq m \leq 10^{18}$$$, $$$1 \leq k \leq 10^6$$$).
В следующей строке находятся $$$n$$$ целых чисел, обозначающих номера на билетах, полученных людьми, участвующими в лотерее. Эти числа — целые числа в диапазоне от $$$0$$$ до $$$m$$$.
Вы должны вывести два целых числа. Первое должно быть равно количеству значений целевого числа (от $$$0$$$ до $$$m$$$), при котором Байтек выигрывает, если оптимально выберет свой билет. Второе должно быть равно целому числу, которое Байтек должен выбрать, чтобы максимизировать свой шанс на выигрыш в лотерею.
3 6 2 1 4 5
4 2
7 7 1 2 4 7 3 0 1 6
1 5
В первом примере Байтек выиграет при $$$4$$$-х целевых значениях (а именно $$$0, 1, 2, 3$$$), если выберет целое число $$$2$$$, которое является наименьшим оптимальным значением. Если он выберет $$$3$$$, он также выиграет в четырех случаях, но это значение не является наименьшим.
Название |
---|