시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 1024 MB | 55 | 16 | 14 | 29.787% |
다음 조건을 만족하는 길이가 $n$인 수열 $A=\{a_1,$ $\cdots ,$ $a_n\}$을 추진력이 $f_A$인 추진력 수열이라 하자.
예를 들어, 수열 $A=\{2,$ $3,$ $4,$ $8\}$은 $d=1$, $f_A=2$일 때 모든 조건을 만족하므로 추진력 수열이다.
추진력 수열 $\{2,$ $3,$ $4,$ $8\}$으로 추진력을 얻는 모습
숫자로만 이루어진 문자열 $S$가 주어질 때, $S=(a_1,$ $\cdots ,$ $a_n$을 공백 없이 이어 붙인 문자열$)$을 만족하는 추진력 수열 $A=\{a_1,$ $\cdots ,$ $a_n\}$가 존재하는지 확인하는 프로그램을 작성해 보자.
단, $a_i$를 문자열로 바꿀 때는 앞에 불필요한 0
을 붙일 수 없으며, $f_A$가 너무 크면 다리에 쥐가 나기 때문에 $f_A$를 최소화하는 $A$를 찾아야 한다.
첫째 줄에 문자열 $S$가 주어진다. $S$의 길이는 $3$ 이상 $2\, 348$ 이하이고, $S$의 각 문자는 0
, 1
, 2
, 3
, 4
, 5
, 6
, 7
, 8
, 9
중 하나이다.
단, 첫 번째 문자가 0
인 문자열은 주어지지 않는다.
$S$에 대해 문제의 조건에 맞는 추진력 수열 $A$가 존재한다면, $f_A$를 정수로 출력한다. $A$가 두 개 이상 존재하는 경우에는 가능한 $f_A$ 중 가장 작은 것을 출력한다.
만약 문제의 조건에 맞는 추진력 수열 $A$가 존재하지 않으면 0
을 출력한다.
2348
2
문제에 언급된 예시이다.
100000000010000000012000000002
0
$A = \{1\,000\,000\,000,$ $1\,000\,000\,001,$ $2\,000\,000\,002\}$는 $10^9$ 이상인 수가 들어있기 때문에 추진력 수열이 아니다.
123
0
$A = \{1,$ $2,$ $3\}$은 $ 3 = 2 \cdot f_A $ 를 만족하는 $2$ 이상의 정수 $f_A$가 존재하지 않으므로 추진력 수열이 아니다.