Другое «Задача 10. Очень быстрая сортировка.»,
алгоритмы и структуры данных в Новосибирске

Задача 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; Внимание! Изменение типа данных и/или метода генерации элементов массива может привести (и на различных компиляторах приводит) к другой последовательности!