Блог пользователя bet_hendl

Автор bet_hendl, 13 лет назад, По-русски

Максимальное время работы на одном тесте:

1 секунда

Максимальный объем используемой памяти:

64 мегабайт

 

Числовая последовательность задана рекуррентной формулой: ai+1=(kai+b)mod m. Найдите её наибольшую возрастающую подпоследовательность.

Формат входных данных

Программа получает на вход пять целых чисел: длину последовательности n (1≤n≤105), начальный элемент последовательности a1, параметры k, b, m для вычисления последующих членов последовательности (1≤m≤104, 0≤k<m, 0≤b<m, 0≤a1<m).

Формат выходных данных

Требуется вывести наибольшую возрастающую подпоследовательность данной последовательности, разделяя числа пробелами. Если таких последовательностей несколько, необходимо вывести одну (любую) из них.

Пример

Входные данные

Выходные данные

5 41 2 1 100

41 67 71


Примечание.

В данном примере последовательность состоит из 5 элементов: a1 = 41, ai+1 = (2ai + 1) mod 100, то есть последовательность имеет вид 41, 83, 67, 35, 71.
  • Проголосовать: нравится
  • -35
  • Проголосовать: не нравится

»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Сгенерируйте последовательность за O(N), затем стандартный алгоритм на возрастающую последовательность.