Задача 10. Очень быстрая сортировка.
Ограничение по времени: 1.5 секунд
Ограничение по памяти: 512 мегабайт
Имеется рекуррентная последовательность A1, A2, …, AN, строящаяся по следующему правилу:
A1 = K
Ai+1 = (Ai ? M) % (232 – 1) % L
Требуется найти сумму всех нечетных по порядку элементов в отсортированной по неубыванию последовательности по модулю L.
Для входных данных
5 7 13 100
последовательность будет такой:
{7; 7 ? 13%100 = 91; 91 ? 13%100 = 83; 83 ? 13%100 = 79; 79 ? 13%100 = 27}, то есть {10; 91; 83; 79; 27}.
Отсортированная последовательность {7; 27; 79; 83; 91}.
Сумма элементов на нечетных местах = (7 + 79 + 91)%100 = 77.
Формат входных данных:
N K M L
5000000 ? N ? 60000000, 0 ? K, L, M ? 232 – 1
Формат выходных данных:
RESULT
Примеры:
Стандартный ввод Стандартный вывод
5 7 13 100 77
Замечание. Для представления элементов последовательности необходимо использовать тип данных unsigned int.
Для получения массива используйте цикл:
a[0] = K;
for (int i = 0; i < N-1; i++)
a[i+1] = (unsigned int) ((a[i]*unsigned long long)M)&0xFFFFFFFFU)%L;
Внимание! Изменение типа данных и/или метода генерации элементов массива может привести (и на различных компиляторах приводит) к другой последовательности!
Надежда
УрГУПС
Татьяна очень ответственный, честный, добросовестный исполнитель. Всем советую!!!
Эльвира
РЭУ им. Плеханова
Задание выполнено отлично! 19 баллов из 20 возможных! Спасибо большое:)
Максим
ТУСУР
Данный исполнитель выполнил ту работу от которой многие отказывались или не справлялись.
Юлия
СПБГЭУ
Отлично выполнила работу! Спасибо вам огромное!Настоящий профессионал своего дела)