Chop Ahoy! Revisited!
시간 제한1초메모리 제한128 MB
숫자 문자열을 연속한 그룹으로 나눌 때 각 그룹의 자릿수 합이 오른쪽으로 갈수록 작아지지 않도록 나누는 경우의 수를 센다.
문제
숫자로만 이루어진 비어 있지 않은 문자열이 주어진다. 원래 순서를 유지한 채 이 숫자들을 연속된 여러 그룹으로 나눌 수 있는데, 다음 규칙을 지켜야 한다. 마지막 그룹을 제외한 모든 그룹에 대해, 그 그룹에 속한 숫자들의 합이 바로 오른쪽 그룹에 속한 숫자들의 합보다 작거나 같아야 한다. 각 숫자는 정확히 하나의 그룹에 속한다.
예를 들어 문자열 635는 하나의 그룹 [635]로 두거나, 두 그룹 [6 | 35]로 나눌 수 있다(6 ≤ 8 이므로 유효하다). 이 두 가지가 전부이다.
또 다른 예로 문자열 1117은 [1117], [1 | 117], [1 | 1 | 17], [1 | 11 | 7], [1 | 1 | 1 | 7], [11 | 17], [111 | 7]의 총 7가지로 나눌 수 있다.
주어진 숫자 문자열에 대해 이러한 유효한 그룹 나누기의 총 개수를 구하는 프로그램을 작성하라.
입력
입력은 여러 개의 테스트 케이스로 이루어지며, 각 테스트 케이스는 한 줄에 하나씩 주어진다. 각 줄에는 길이가 25 이하인 십진 숫자로만 이루어진 문자열 하나가 들어 있다. 마지막에는 bye라는 단어만 있는 줄이 오며, 이 줄은 테스트 케이스에 포함되지 않는다.
출력
각 테스트 케이스마다 다음 형식으로 한 줄씩 출력한다.
k. n
여기서 k는 테스트 케이스 번호(1부터 시작)이고, n은 해당 테스트 케이스의 유효한 그룹 나누기 개수이다.