#P4789. [BalkanOI2018] Zalmoxis

[BalkanOI2018] Zalmoxis

题目描述

翻译自 BalkanOI 2018 Day2 T3「Zalmoxis

「ZalPunch」 是一种修改数列的方式,每次 ZalPunch 可以将数列中的任意一个正整数 xx 原地替换成两个 (x1)(x-1)

  • 正确示范:[1,1]ZalPunch[0,0,1][1, 1]\xrightarrow{ZalPunch}[0, 0, 1]
  • 正确示范:[1,23,3]ZalPunch[1,22,22,3][1,23,3]\xrightarrow{ZalPunch}[1,22,22,3]
  • 错误示范:[1,3]ZalPunch[2,1,2][1,3]\xrightarrow{ZalPunch}[2,1,2](第一个 2 不在原位)。

从数列 [30][30] 开始,用 ZalPunch 修改该数列任意多次,所得到的所有数列都称为 「ZalSequence」(含数列 [30][30])。
给你一个有 NN 项的数列 SS,请在其中插入 KK 个数(不是使用 KK 次 ZalPunch),使之变成 ZalSequence。保证有解。

输入格式

第一行有两个整数 N,KN, K
第二行有 NN 个整数,表示数列 SS

输出格式

输出 N+KN+K 个整数,表示新数列。

5 1
29 27 25 25 28
29 27 25 25 26 28

1 5
29
29 28 27 26 25 25

提示

样例解释 1

[30][29,29][29,28,28][29,27,27,28][30] → [29, 29] →[29, 28, 28] →[29, 27, 27, 28] [29,27,26,26,28]→[29, 27, 26, 26, 28] [29,27,25,25,26,28]→ [29, 27, 25, 25, 26, 28]

样例解释 2

[30][29,29][29,28,28][29,28,27,27][30] → [29, 29] →[29, 28, 28] →[29, 28, 27, 27] [29,28,27,26,26]→[29, 28, 27, 26, 26] [29,28,27,26,25,25]→[29, 28, 27, 26, 25, 25]

对于 30%30\% 的数据,K=1K=1
对于所有数据,1N,K106,1 ≤ N,K ≤ 10^6, 1N+K1061 ≤ N + K ≤ 10^6

感谢 Planet6174 提供的翻译

感谢 @tiger2005 提供的 SPJ