수 이어 쓰기
시간 제한2초메모리 제한128 MB
1부터 N까지 이어붙인 문자열에서 일부 숫자를 지운 뒤 남은 부분 문자열이 주어질 때, 가능한 가장 작은 N을 구합니다.
문제
1부터 N까지의 모든 정수를 차례대로 공백 없이 이어 쓰면 123456789101112...N과 같은 문자열이 된다.
이 문자열에서 일부 숫자를 지웠고, 숫자를 하나도 지우지 않았을 수도 있다. 남은 숫자들은 원래 순서를 유지한 채 이어 붙여져 있다.
남은 숫자 문자열이 주어질 때, 이 문자열을 만들 수 있는 가능한 N 중 최솟값을 구하시오.
입력
첫째 줄에 지워진 뒤 남은 숫자 문자열이 주어진다. 문자열의 길이는 최대 3,000이다.
출력
주어진 문자열을 만들 수 있는 가능한 N 중 최솟값을 출력한다.