ez_code   2년 전

문제

이진 문자열은 0과 1로 이루어진 비지 않은 문자열입니다. 예시로는 010110, 1, 11101 등이 있습니다. edit(S, T)로 나타내는 두 이진 문자열 S와 T 사이 편집 거리는, S를 T로 수정하기 위해 필요한 개별 문자 편집(삽입, 삭제, 교체)의 최소 횟수입니다.  예를 들어, 0011과 1100의 편집 거리는 4입니다: 0011 -> 011 -> 11 -> 110 -> 1100. 1100101과 1110100의 편집 거리는 2입니다: 1100101 -> 1110101 -> 1110100.

아유는 이진 문자열 S를 가지고 있습니다. 그녀는 S와 길이가 같으면서 S와의 편집 거리가 최대인 이진 문자열을 찾고 싶습니다. 엄밀히 말해 그녀는 |S| = |Tmax|이고, |S| = |T'|를 만족하는 모든 이진 문자열 T'에 대해 edit(S, Tmax) >= edit(S, T')인 이진 문자열 Tmax를 찾으려 합니다. 

당신의 도움이 필요합니다! 하지만 문제를 쉽게 만들기 위해, 당신은 S와 T 사이 편집 거리가 S의 길이의 절반보다 크고 S와 길이가 같은 이진 문자열 T를 아무거나 출력하면 됩니다. 엄밀히 말해, 당신은 |S| = |T|이고 edit(S, T) > |S| / 2인 이진 문자열 T를 출력해야 합니다.

물론 임의의 이진 문자열 S에 대해 edit(S, Tmax) > |S| / 2임을 증명할 수 있으므로 원한다면 Tmax를 출력해도 됩니다. 임의의 이진 문자열 S에 대해 해가 존재함도 증명됩니다. 하나 이상의 유효한 답이 있을 경우, 아무거나 출력해도 됩니다.

입력

입력에 이진 문자열 S가 주어집니다. (1 <= |S| <= 2000)

출력

edit(S, T) > |S| / 2를 만족하는 S와 길이가 같은 이진 문자열 T를 한 줄에 출력합니다. 

댓글을 작성하려면 로그인해야 합니다.