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