Дан массив из элементов. Какие числа являются
-ым,
-ым, ...,
-ым в порядке неубывания в этом массиве?
В первой строке входного файла содержатся три числа: -- размер массива, а также границы интервала
и
, при этом
,
.
Во второй строке находятся числа ,
,
,
,
, по модулю не превосходящие
. Вы должны получить элементы массива, начиная с третьего, по формуле:
. Все вычисления должны производится в 32-битном знаковом типе, переполнения должны игнорироваться.
Обращаем Ваше внимание, что массив из 32-битных целых чисел занимает в памяти 160 мегабайт! Будьте аккуратны!
Подсказка: эту задачу лучше всего решать модификацией быстрой сортировки. Однако сортировка массива целиком по времени, скорее всего, не пройдет, поэтому нужно подумать, как модифицировать быструю сортировку, чтобы не сортировать те части массива, которые не нужно сортировать.
Эту задачу, скорее всего, нельзя решить ни на Python, ни на PyPy. Мы не нашли способа сгенерировать 32-битных целых чисел и при этом уложиться в ограничение по времени. Если у Вас тоже не получается, попробуйте другой язык программирования!
В первой и единственной строке выходного файла выведите -ое,
-ое, ...,
-ое в порядке неубывания числа в массиве
. Числа разделяйте одним пробелом.
input.txt
5 3 4
2 3 5 1 2
output.txt
13 48
input.txt
5 3 4
200000 300000 5 1 2
output.txt
2 800005
Во втором примере элементы массива равны:
[1, 2, 800005, −516268571, 1331571109]