Codeforces Round 293 (Div. 2) |
---|
Закончено |
После скобочных последовательностей Артур увлекся теорией чисел. И у него появилась новая любимая последовательность длины n (a1, a2, ..., an), состоящая из целых чисел, и целое число k, не превышающее n.
Эта последовательность обладала следующим свойством. Если выписать суммы всех ее подотрезков, состоящих из k подряд идущих элементов (a1 + a2 ... + ak, a2 + a3 + ... + ak + 1, ..., an - k + 1 + an - k + 2 + ... + an), то элементы выписанной последовательности будут строго возрастать.
Например, для следующего примера: n = 5, k = 3, a = (1, 2, 4, 5, 6) последовательность сумм будет иметь вид: (1 + 2 + 4, 2 + 4 + 5, 4 + 5 + 6) = (7, 11, 15), а значит последовательность a удовлетворяет описанному свойству.
Очевидно, в последовательности сумм будет n - k + 1 элемент.
Кто-то (не будем говорить кто) заменил в последовательности Артура некоторые числа на знаки вопроса (если число заменяется, то ровно на один знак вопроса). Нужно восстановить последовательность, чтобы она удовлетворяла нужному свойству, и при этом минимизировать сумму |ai|, где |ai| — абсолютная величина ai.
В первой строке следуют два целых числа n и k (1 ≤ k ≤ n ≤ 105), обозначающих соответственно количество чисел в последовательности Артура и длины подотрезков.
В следующей строке следуют через пробел n элементов ai (1 ≤ i ≤ n).
Если ai = ?, значит i-й элемент последовательности Артура был заменен на знак вопроса.
В противном случае, ai ( - 109 ≤ ai ≤ 109) — i-й элемент последовательности Артура.
Если Артур что-то напутал, и последовательности, соответствующей данной информации нет, выведите единственную строку «Incorrect sequence» (без кавычек).
В противном случае, выведите в первую строку выходных данных n целых чисел — любимую последовательность Артура. Если таких последовательностей несколько, выведите последовательность с минимальной суммой |ai|, где |ai| — абсолютная величина ai. Если и таких последовательностей несколько, разрешается вывести любую из них. Элементы последовательности следует выводить без лидирующих нулей.
3 2
? 1 2
0 1 2
5 1
-10 -9 ? -7 -6
-10 -9 -8 -7 -6
5 3
4 6 7 2 9
Incorrect sequence
Название |
---|