| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 512 MB | 106 | 35 | 27 | 44.262% |
Гирлянда --- это цепочка из элементов: флажков и шариков, содержащая хотя бы один флажок. Длиной гирлянды называется количество элементов, из которых она состоит.
Гирлянда считается красивой, если для каждого флажка количество подряд идущих шариков слева от него до ближайшего слева флажка или до начала гирлянды равно количеству подряд идущих шариков справа от него до ближайшего справа флажка или до конца гирлянды.
Обозначим шарик символом <<0>>, а флажок --- символом <<1>>. Например, гирлянда <<0001000>> является красивой, а гирлянда <<001010>> --- нет, поскольку слева от первого флажка два шарика, а справа от него --- один шарик. Отметим, что цепочка <<000>> не является гирляндой, так как не содержит ни одного флажка.
Задана гирлянда, разрешается удалить некоторые её элементы.
Требуется написать программу, находящую по описанию гирлянды самую длинную красивую гирлянду, которую можно получить из заданной удалением элементов.
Первая строка содержит целое число $n$ --- количество элементов в исходной гирлянде (1ドル \leq n \leq 500,000円$).
Вторая строка содержит описание гирлянды в виде строки из $n$ символов <<0>> и <<1>>. Строка содержит хотя бы один символ <<1>>.
В первой строке выведите число $m$ --- длину получившейся красивой гирлянды (1ドル \leq m \leq n$).
Во второй строке выведите получившуюся красивую гирлянду.
Если существует несколько решений, выведите любое из них.
Обозначим через $k$ количество флажков в исходной гирлянде.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 20 | $n \le 15$ |
| 2 | 20 | $n \le 1000,ドル $k \le 2$ |
| 3 | 20 | $n \le 1000,ドル $k \le 15$ |
| 4 | 16 | $n \le 1000$ |
| 5 | 10 | $n \le 100,000円,ドル $k \le 50$ |
| 6 | 14 | $n \le 500,000円$ |
10 0100100000
7 0001000
3 111
3 111
7 0100101
5 01010