ANARC05H - Chop Ahoy! Revisited!
Given a non-empty string composed of digits only, we may group these digits into sub-groups (but maintaining their original order) if, for every sub-group but the last one, the sum of the digits in a sub-group is less than or equal to the sum of the digits in the sub-group immediately on its right. Needless to say, each digit will be in exactly one sub-group.
For example, the string 635 can only be grouped in one sub-group  or in two sub-groups as follows: [6-35] (since 6 < 8.) Another example is the string 1117 which can be grouped in one sub-group  or as in the following: [1-117], [1-1-17], [1-11-7], [1-1-1-7], [11-17] and [111-7] but not any more, hence the total number of possibilities is 7.
Write a program that computes the total number of possibilities of such groupings for a given string of digits.
Your program will be tested on a number of test cases. Each test case is speciﬁed on a separate line. Each line contains a single string no longer than 25, and is made of decimal digits only.
The end of the test cases is identiﬁed by a line made of the word "bye" (without the quotes.) Such line is not part of the test cases.
For each test case, write the result using the following format:
where k is the test case number (starting at 1,) and n is the result of this test case.
Input: 635 1117 9876 bye Output: 1. 2 2. 7 3. 2
Bottom-up solution was a challenge for me
Easy DPLast edit: 2020-03-30 21:21:08
easy peasy lemon squeezy AC in one go!!!!!!!!!
it is a backtracking problem with memoization
dont need to memorize.
this is not a dp problem..
similar to this:- https://www.spoj.com/problems/ROCK/
Hey can anyone give any corner case? I tried many testcases including string length 25 and even compared it with actual output from spoj toolkit but WA. :(
Nice one , solved using backtracking , AC in 1 go
There are no overlapping subproblems , hence it is not a DP problem. The tag is incorrect.