← 返回题目列表

AtCoder · kupc2020_d

D. 摇杆组合

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

配点 : {200} 点

問題文

。长度为 1,3,5,7,...,2N-1 的棒子各有 1 根,总计 N 根棒子。

你被棒子商要求,为了在商店出售,通过粘合剂将棒子粘合,让棒子的长度统一。

随后 2 剩余不少于

根棒子,请输出一种使得粘合后剩下的所有棒子长度相等的棒子粘合方法。 如果不存在这样的连接方法,则impossible。

但是,当连接多个棒时,连接后的棒的长度等于用于粘合的棒的长度之和,不能舍弃或切断棒。

制約

  • 输入全部为整数。
  • 2 \leq N \leq 10^5

入力

输入将以以下格式从标准输入给出。

N

出力

如果存在满足问题描述条件的连接方法 1 行,将追加后剩余的棒的数量 M 到下一行的开头 m + 1 (1 \leq m \leq M) 行 m 为制造第几根棒而连接的棒的数量 l_m 在同一行 m 为制造第几根棒而连接的棒的长度 x_{m,i} (1 \leq i \leq l_m) 用空格分隔 l_m 输出个数。

此外,如果满足问题描述条件的组合有多个,输出其中任意一个都可以。

如果不存在满足条件的连接方法impossible。

  • 2 \leq M \leq N
  • 1 \leq l_m \leq N (1 \leq m \leq M)
  • \sum_{m}{l_m} = N
  • x_{m,i} \in \{1, 3, 5, ..., 2N-1\} (1 \leq i \leq l_m)
  • x_{m,i} 则相互不同。
  • \sum_{i}{x_{1,i}} = \sum_{i}{x_{2,i}} = ... = \sum_{i}{x_{M,i}}
  • 输出全部用整数进行。
M
l_1 x_{1,1} x_{1,2} ... x_{1,l_1}
l_2 x_{2,1} x_{2,2} ... x_{1,l_2}
:
l_M x_{M,1} x_{M,2} ... x_{M,l_M}

入力例 1

4

出力例 1

2
2 1 7
2 3 5

长度 1,3,5,7 的棒 1, 7 和 3, 5 分开后各自粘合,可以得到长度 8 的棒 2 根,这符合条件。


入力例 2

2

出力例 2

impossible

长度 1 和长度 3 的 已知 2 无论如何连接书籍,也不会成为比原来更长的棒子。 2 超过原长度的棒子不会产生。


入力例 3

3

出力例 3

impossible

长度 1,3,5 的 已知 3 在只有~本的情况下,也不存在满足条件的连接方法。