← 返回题目列表

Codeforces · 1119/G

G. 准备战斗

中文机器翻译题面 查看原题

最近Evlampy安装了一款有趣的电脑游戏,其中一个方面是将军队分成几个小组,然后与敌人的小组作战。让我们考虑一下战斗的简化版本。

在最近的战斗中,Evlampy 应该与一支由 $$$m$$$ 团体组成的敌军作战,其中第 $$$i$$$ 拥有 $$$hp_i$$$ 生命值。

Evlampy 的军队由 $$$n$$$ 平等的士兵组成。在每次战斗之前,他应该将他的军队精确地分成 $$$m$$$ 个小组(可能是空的),以便小组的总规模为 $$$n$$$。战斗是一步步进行的。 Evlampy 的每一步都会攻击一组敌人。因此,每个步骤都用 $$$m$$$ 整数数组 $$$a_1, a_2, \ldots, a_m$$$ 来描述,这意味着第 $$$i$$$ 个 Evlampy 小组攻击第 $$$a_i$$$ 个敌方小组。不同的群体可以攻击同一群体,每一步都会独立选择数组$$$a$$$。

每一步之后,每个敌方队伍的生命值都会减少,数量等于在这一步攻击该敌方队伍的 Evlampy 队伍中的士兵总数。一旦敌方生命值为零或负数,就会被消灭。 Evlampy 的士兵不会失去生命值。

步骤示例。绿色圆圈中的数字代表Evlampy队伍中的士兵数量,箭头代表攻击,红色圆圈中的数字代表敌方队伍的生命值,蓝色数字代表该步骤后生命值将减少多少。

Evlampy知道即将到来的战斗将需要整个晚上。他很伤心,因为这样他就没有足够的时间完成作业。现在,Evlampy 希望您编写一个程序,帮助他以尽可能少的步数获胜。你能帮助他吗?

换句话说,找到消灭所有敌人群体所需的最少步骤,并展示一种可能的方法。找到将军队分成 $$$m$$$ 组的要求以及每个步骤的数组 $$$a$$$。

输入

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \leq m \leq n \leq 10^{6}$$$) — Evlampy 军队中的士兵数量和敌军中的团体数量。 $$$m$$$ 也等于 Evlampy 可以将军队分成的最大可能数量。

第二行包含 $$$m$$$ 整数 $$$hp_1, hp_2, \ldots, hp_m$$$ ($$$1 \leq hp_i \leq 10^{6}$$$) — 每个敌人群体的生命值。

保证$$$hp_i$$$的总和不超过$$$10^{6}$$$。

输出

打印一个整数 $$$t$$$ — 赢得战斗所需的最小可能步数。

之后打印 $$$m$$$ 整数 $$$s_1, s_2, \ldots, s_m$$$ ($$$s_i \ge 0$$$, $$$s_1 + s_2 + \ldots + s_m = n$$$),这意味着 Evlampy 军队的第 $$$i$$$ 组应该包含$$$s_i$$$ 士兵。

在接下来的 $$$t$$$ 行中打印 $$$m$$$ 整数 $$$a_1, a_2, \ldots, a_m$$$ ($$$1 \le a_i \le m$$$) - 一个步骤的描述。整数意味着在相应的步骤中,第 $$$i$$$ 个 Evlampy 小组应该攻击第 $$$a_i$$$ 个敌方小组。它可以攻击已经被摧毁的群体。

示例

输入 #1

13 7
6 4 3 7 2 1 5

输出 #1

3
0 1 2 3 1 2 4
2 6 2 4 4 2 4
3 1 7 1 7 7 1
3 1 5 3 7 5 1

输入 #2

6 5
3 3 3 3 3

输出 #2

3
3 3 0 0 0
1 2 3 4 5
3 4 5 5 5
5 5 5 5 5

输入 #3

7 4
1 5 9 2

输出 #3

3
1 2 4 0
1 4 2 3
2 3 3 3
3 3 3 3

注意

第一个示例如下所示。