Задача 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;
Внимание! Изменение типа данных и/или метода генерации элементов массива может привести (и на различных компиляторах приводит) к другой последовательности!
Надежда
Ярославский педагогический колледж
Анастасия выполнила заказ досрочно и очень качественно. Рекомендую данного автора однозначно!
Мила
Коломенский политехнический институт (филиал Московского политехнического университета)
Спасибо большое за помощь. Всё супер!!! Отзывчивый исполнитель! Рекомендую.
Куаныш
Автотранспортный Колледж
Виктория очень хороший исполнитель))) Выполнила работу очень быстро.Всем советую
Владимир
УрГУПС
Есть не большие ошибки, но не критичные и на сдачу предмета не повлияли. Спасибо!