[AdditionalFile3191.zip](file://AdditionalFile3191.zip?type=additional_file)

#3191. 「ROI 2019 Day2」花环

标签: 传统 | 时间限制: 2000 ms | 内存限制: 512 MiB |

题目描述

译自 ROI 2019 Day2 T1. Гирлянда

P11084 [ROI 2019] 灯串 (Day 2)

题目背景

翻译自 ROI 2019 D2T1。

对于一个由 0 和 1 组成的序列，“美丽的”的定义是：如果这个序列的第一个 1 前面 0 的数量和最后一个 1 后面 0 的数量相等，且每两个 1 之间的 0 的数量也等于这个数值，则称这个序列是“美丽的”。

例如，0101010 和 11111 是“美丽的”，而 10101 和 010100001000001010000 就不是“美丽的”。

题目描述

给定一串由 0 和 1 组成的序列（保证 1 的数量不为 $0$），需要删除其中任意位置的一些元素，使得剩下的序列构成最长的美丽的串。

输入格式

第一行输入一个数 $n$，表示这个序列的长度。

第二行输入一个字符串 $s$，只由 0 和 1 组成，表示这个序列。

输出格式

第一行输出一个数 $m$，表示删除后剩下的序列长度。

第二行输出通过删除操作后剩下的这个“美丽的”序列。

如果有多种方案，输出任意一种。注意：全为 0 的串不是“美丽的”。

输入输出样例 #1

输入 #1

10
0100100000

输出 #1

7
0001000

输入输出样例 #2

输入 #2

3
111

输出 #2

3
111

输入输出样例 #3

输入 #3

7
0100101

输出 #3

5
01010

说明/提示

设原串有 $k$ 个 $1$。