Remix
给定一个由 n 个整数组成的多重集 S。你需要重复执行下列三步操作,直到 S 中只剩一个整数:
- 选择 S 的一个子多重集 T,满足 ∣T∣≥2。
- 从 S 中删除 T 的全部元素。
- 向 S 中插入一个整数 max(T)−min(T)。
请构造一系列操作,使最后剩下的整数尽可能大。
输入格式
第一行一个整数 n,2≤n≤105。
第二行 n 个整数 S1,S2,…,Sn,0≤Si≤105。数值可以重复,也可以为 0;它们按出现次数构成多重集。
输出格式
第一行输出操作次数 k,1≤k≤n−1。
接下来 k 行,每行先输出所选子多重集的大小 m,再输出其中的 m 个数值 T1,T2,…,Tm,顺序任意,2≤m≤n。这些数值不是初始下标。
操作按输出顺序执行。每步的 T 必须是此前所有操作完成后当前 S 的子多重集;如果某个数值被选取多次,当前必须有足够多个副本。最后必须恰好剩一个整数,并且达到最大可能值。可以输出任意一种最优操作序列。
原样例
7
33 24 63 48 97 90 93
4
3 33 93 90
2 63 60
2 48 24
3 97 24 3
原样例说明
样例可以按下表操作。表中带下划线的值表示该步新插入的数:
| 步骤 |
选取的 T |
操作后的 S |
| 0 |
— |
{24,33,48,63,90,93,97} |
| 1 |
{33,90,93} |
{24,48,60,63,97} |
| 2 |
{60,63} |
{3,24,48,97} |
| 3 |
{24,48} |
{3,24,97} |
| 4 |
{3,24,97} |
{94} |
四步后只剩 94。可以证明不存在使最终整数更大的操作序列。