问题
화환은 하나 이상 k개의 꽃을 포함하는 꽃과 구슬로 이루어진 사슬이다.
화환의 길이는 화환을 구성하는 원소의 수이다.
화환은 각 꽃에 대해 왼쪽에 있는 가장 가까운 꽃까지의 구슬의 수(또는 왼쪽에 꽃이 없다면, 왼쪽에 있는 구슬의 수)가
오른쪽에 있는 가장 가까운 꽃까지의 구슬의 수(또는 오른쪽에 꽃이 없다면, 오른쪽에 있는 구슬의 수)와 같으면 '아름답다'라고 한다.
'0'을 구슬, '1'을 꽃이라고 하자.
예를 들어 화환 "0001000"은 아름답지만, 화환 "001010"은 아름답지 않다.
첫 번째 꽃의 왼쪽에 두 개의 구슬이 있고 오른쪽에 하나의 구슬이 있기 때문이다.
"000"은 꽃이 포함되어 있지 않기 때문에 화환이 아니다.
화환이 주어지면 몇 개의 원소를 삭제할 수 있다.
화환이 주어지면, 주어진 화환에서 몇 개의 원소를 제거하여 얻을 수 있는 가장 긴 아름다운 화환을 찾는 프로그램을 작성하시오.
输入
첫 번째 줄에는 원래 화환의 길이인 n이 주어진다.
두 번째 줄에는 원래 화환의 모습이 '0'과 '1'의 문자열로 주어진다.
원래 화환에는 최소 하나 이상의 '1'(꽃)이 포함되어 있다.
输出
첫 번째 줄에 원래 화환에서 몇 개의 원소를 삭제하여 생긴 가장 긴 아름다운 화환의 길이를 출력하시오.
두 번째 줄에 해당 아름다운 화환을 출력하시오.
정답으로 가능한 것이 여러 개인 경우, 그 중 하나를 출력하시오.
子任务
| 编号 | 分数 | 条件 |
|---|---|---|
| #1 | 20分 | n <= 15 |
| #2 | 20分 | n <= 1,000, k <= 2 |
| #3 | 20分 | n <= 1,000, k <= 15 |
| #4 | 16分 | n <= 1,000 |
| #5 | 10分 | n <= 100,000, k <= 50 |
| #6 | 14分 | n <= 500,000 |
示例 #1
10
0100100000
7
0001000
示例 #2
3
111
3
111
示例 #3
7
0100101
5
01010
需要登录才能编写代码。