Kirk and a Binary String (easy version)

题意翻译

题目描述 给你一个二进制字符串$s$，让你求出一个新的二进制字符串$t$，使其满足以下条件： 1. 新字符串的$0$的个数尽可能多。 1. 对于每个$l,r(1≤l≤r≤n)$，两个字符串的最长不下降子序列等长。 输入格式 一行，一个二进制字符串$s$。 输出格式 一行，满足条件的二进制字符串$t$。

题目描述

The only difference between easy and hard versions is the length of the string. You can hack this problem only if you solve both problems. Kirk has a binary string $ s $ (a string which consists of zeroes and ones) of length $ n $ and he is asking you to find a binary string $ t $ of the same length which satisfies the following conditions: - For any $ l $ and $ r $ ( $ 1 \leq l \leq r \leq n $ ) the length of the longest non-decreasing subsequence of the substring $ s_{l}s_{l+1} \ldots s_{r} $ is equal to the length of the longest non-decreasing subsequence of the substring $ t_{l}t_{l+1} \ldots t_{r} $ ; - The number of zeroes in $ t $ is the maximum possible. A non-decreasing subsequence of a string $ p $ is a sequence of indices $ i_1, i_2, \ldots, i_k $ such that $ i_1 < i_2 < \ldots < i_k $ and $ p_{i_1} \leq p_{i_2} \leq \ldots \leq p_{i_k} $ . The length of the subsequence is $ k $ . If there are multiple substrings which satisfy the conditions, output any.

输入输出格式

输入格式

The first line contains a binary string of length not more than $ 2\: 000 $ .

输出格式

Output a binary string which satisfied the above conditions. If there are many such strings, output any of them.

输入输出样例

输入样例 #1

110

输出样例 #1

010

输入样例 #2

010

输出样例 #2

010

输入样例 #3

0001111

输出样例 #3

0000000

输入样例 #4

0111001100111011101000

输出样例 #4

0011001100001011101000

说明

In the first example: - For the substrings of the length $ 1 $ the length of the longest non-decreasing subsequnce is $ 1 $ ; - For $ l = 1, r = 2 $ the longest non-decreasing subsequnce of the substring $ s_{1}s_{2} $ is $ 11 $ and the longest non-decreasing subsequnce of the substring $ t_{1}t_{2} $ is $ 01 $ ; - For $ l = 1, r = 3 $ the longest non-decreasing subsequnce of the substring $ s_{1}s_{3} $ is $ 11 $ and the longest non-decreasing subsequnce of the substring $ t_{1}t_{3} $ is $ 00 $ ; - For $ l = 2, r = 3 $ the longest non-decreasing subsequnce of the substring $ s_{2}s_{3} $ is $ 1 $ and the longest non-decreasing subsequnce of the substring $ t_{2}t_{3} $ is $ 1 $ ; The second example is similar to the first one.

题意翻译

题目描述 给你一个二进制字符串$s$，让你求出一个新的二进制字符串$t$，使其满足以下条件： 1. 新字符串的$0$的个数尽可能多。 1. 对于每个$l,r(1≤l≤r≤n)$，两个字符串的最长不下降子序列等长。 输入格式 一行，一个二进制字符串$s$。 输出格式 一行，满足条件的二进制字符串$t$。