Chop Ahoy! Revisited!
Time limit1sMemory limit128 MB
Count the ways to split a digit string into consecutive groups whose digit sums are non-decreasing across groups.
- Level
Medium6 of 10
- Topics
- Dynamic programming, Prefix sum
- Solved
- No attempts yet
Problem
You are given a non-empty string made up of decimal digits only. Keeping their original order, you may split these digits into consecutive sub-groups subject to one rule: for every sub-group except the last one, the sum of the digits in that sub-group must be less than or equal to the sum of the digits in the sub-group immediately to its right. Every digit belongs to exactly one sub-group.
For example, the string 635 can be kept as the single sub-group [635], or split into two sub-groups [6 | 35] (valid because 6 ≤ 8). Those are the only two possibilities.
As another example, the string 1117 can be grouped as [1117], [1 | 117], [1 | 1 | 17], [1 | 11 | 7], [1 | 1 | 1 | 7], [11 | 17], and [111 | 7] — seven groupings in total.
Write a program that, for a given string of digits, computes the total number of such valid groupings.
Input
The input consists of several test cases, one per line. Each line holds a single string of at most 25 decimal digits. The list ends with a line containing the word bye; that line is not itself a test case.
Output
For each test case, print one line in the following format:
k. n
where k is the test case number (starting from 1) and n is the number of valid groupings for that test case.