← 返回题目列表

Codeforces · 1189/A

A. 基努·里维斯

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

在传奇的《黑客帝国》三部曲中扮演尼奥后,基努·里维斯开始怀疑自己:也许我们真的生活在虚拟现实中?为了确定这是否属实,他需要解决以下问题。

如果一个仅由 0 和 1 组成的字符串包含不同数量的 0 和 1,我们称该字符串为好字符串。例如,1、101、0000 是好的,而 01、1001 和 111000 则不好。

我们得到一个长度为 $$$n$$$ 的字符串 $$$s$$$,仅由零和一组成。我们需要将 $$$s$$$ 切割成尽可能少的子串 $$$s_1, s_2, \ldots, s_k$$$ ,这样它们都是好的。更正式地说,我们必须找到最小的好字符串序列 $$$s_1, s_2, \ldots, s_k$$$,使得它们的串联(连接)等于 $$$s$$$,即 $$$s_1 + s_2 + \dots + s_k = s$$$。

例如,将 110010 切割成 110 和 010 或切割成 11 和 0010 是有效的,因为 110、010、11、0010 都是好的,并且我们不能将 110010 切割成更少数量的子串,因为 110010 本身不好。同时,将 110010 切割成 1100 和 10 是无效的,因为这两个字符串都不好。此外,将 110010 切割成 1, 1, 0010 是无效的,因为它不是最小的,即使所有 $$$3$$$ 字符串都很好。

你能帮助基努吗?我们可以证明解总是存在的。如果有多个最佳答案,请打印其中一个。

输入

输入的第一行包含一个整数 $$$n$$$ ($$$1\le n \le 100$$$) — 字符串 $$$s$$$ 的长度。

第二行包含长度为 $$$n$$$ 的字符串 $$$s$$$,仅由零和一组成。

输出

在第一行中,输出单个整数 $$$k$$$ ($$$1\le k$$$) — 您已将 $$$s$$$ 切成的最小字符串数。

在第二行中,输出 $$$k$$$ 字符串 $$$s_1, s_2, \ldots, s_k$$$ 以空格分隔。每个字符串的长度必须为正。它们的串联必须等于 $$$s$$$ 并且它们都必须是好的。

如果有多个答案,请打印其中一个。

示例

输入 #1

1
1

输出 #1

1
1

输入 #2

2
10

输出 #2

2
1 0

输入 #3

6
100011

输出 #3

2
100 011

注意

在第一个示例中,字符串 1 根本没有被剪切。因为好,所以条件满足。

在第二个示例中,1 和 0 都很好。由于 10 不太好,所以答案确实很小。

在第三个示例中,100 和 011 都很好。由于 100011 不好,所以答案确实很小。