Edit Distance
면접 대비시간 제한1초메모리 제한512 MB
이진 문자열 S가 주어질 때, 길이가 같고 S와의 편집 거리가 길이의 절반을 넘는 이진 문자열 T를 아무거나 출력한다.
문제
A binary string is a non-empty sequence of 0’s and 1’s, e.g., 010110, 1, 11101, etc. The edit distance of two binary strings S and T, denoted by edit(S, T), is the minimum number of single-character edit (insert, delete, or substitute) to modify S into T. For example, the edit distance of 0011 and 1100 is 4, i.e. 0011 → 011 → 11 → 110 → 1100. The edit distance of 1100101 and 1110100 is 2, i.e. 1100101 → 1110101 → 1110100.
Ayu has a binary string S. She wants to find a binary string with the same length as S that maximizes the edit distance with S. Formally, she wants to find a binary string Tmax such that |S| = |Tmax| and edit(S, Tmax) ≥ edit(S, T') for all binary string T' satisfying |S| = |T'|.
She needs your help! However, since she wants to make your task easier, you are allowed to return any binary string T with the same length as S such that the edit distance of S and T is more than half the length of S. Formally, you must return a binary string T such that |S| = |T| and edit(S, T) > |S|/2.
Of course, you can still return Tmax if you want, since it can be proven that edit(S, Tmax) > |S|/2 for any binary string S. This also proves that there exists a solution for any binary string S. If there is more than one valid solution, you can output any of them.
입력
Input contains a binary string S (1 ≤ |S| ≤ 2000).
출력
Output in a line a binary string T with the same length as S that satisfies edit(S, T) > |S|/2.