← 返回题目列表

Codeforces · 44/I

I. 玩具

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

小玛莎喜欢把她的玩具堆放在地板上。她也讨厌有人碰她的玩具。有一天,玛莎把她所有的玩具分成几堆,然后她的哥哥萨莎来了,把所有的玩具堆成了一堆。玛莎看到后非常难过并开始哭泣。萨莎仍然无法让玛莎平静下来,妈妈很快就会回家并惩罚萨莎让玛莎哭泣。这就是为什么他决定恢复桩的排列。然而,他完全不记得玩具以前是如何撒谎的。玛莎当然记得,但她还不能说话,只能在萨莎按照以前撒谎的方式摆放玩具时高兴地大喊来帮助萨莎。这意味着萨莎必须以各种可能的方式排列玩具,直到玛莎认识到所需的排列方式。堆和每堆中玩具的相对位置是无关紧要的,这就是为什么如果可以找到两个这样的玩具,当以第一种方式排列时,它们位于同一堆中,而如果以第二种方式排列,则两种玩具排列方式被认为是不同的。莎莎正在寻找最快的方法,尝试所有的方法,因为妈妈很快就会来。莎莎的每一个动作都可以从任意一堆玩具中取出一个玩具并将其移动到任何其他一堆(因此可能会出现新的一堆,也可能会出现旧的一堆)。 Sasha 想要找到动作的顺序,这样所有的桩排列变体都会被精确地尝试一次。帮助萨沙。我们记得,最初所有的玩具都堆放在一堆。

输入

第一行包含一个整数 n (1 ≤ n ≤ 10) — 玩具的数量。

输出

在第一行打印玩具排列成堆的不同变体的数量。然后按照 Sasha 应该尝试的顺序打印所有将玩具排列成堆的方法(即,每一种下一种方法都必须通过语句中描述的操作从前一种方法产生)。每种方式都应按以下格式打印。每堆玩具应按数字升序排列。然后,应按照其中第一个玩具的编号升序对这堆玩具进行排序。在一行上输出每种方式。比照。指定输出数据格式的示例。如果解不唯一,则输出其中任意一个。

示例

输入 #1

3

输出 #1

5
{1,2,3}
{1,2},{3}
{1},{2,3}
{1},{2},{3}
{1,3},{2}