시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 92 29 22 31.884%

문제

문자열 S가 다음과 같은 두 가지 조건을 만족하면 특별한 문자열이라고 한다.

  • S의 모든 글자는 '0' 또는 '1' 이다.
  • S를 두 부분 UV로 나누었을 때, U가 V보다 사전순으로 앞서야 한다. 

예를 들어, S = "00101"은 특별한 문자열 이다. 이유는 "0" < "0101", "00" < "101", "001" < "01", "0010" < "1" 이기 때문이다.

길이가 N인 특별한 문자열 S가 주어진다. 이때, 길이가 N인 모든 특별한 문자열을 사전 순으로 정렬했을 때, S의 다음에 오는 특별한 문자열을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 특별한 문자열 S가 주어진다. S의 길이 N은 1보다 크거나 같고, 50보다 작거나 같은 자연수이다.

출력

S의 사전 순으로 다음에 오는 특별한 문자열을 출력한다. 만약, S가 사전순으로 마지막으로 오는 특별한 문자열인 경우에는 -1을 출력한다.

예제 입력 1

01

예제 출력 1

-1

예제 입력 2

00101

예제 출력 2

00111

예제 입력 3

0010111

예제 출력 3

0011011

출처

  • 문제를 번역한 사람: baekjoon
  • 잘못된 번역을 찾은 사람: jh05013