ANARC05H  Chop Ahoy! Revisited!
Given a nonempty string composed of digits only, we may group these digits into subgroups (but maintaining their original order) if, for every subgroup but the last one, the sum of the digits in a subgroup is less than or equal to the sum of the digits in the subgroup immediately on its right. Needless to say, each digit will be in exactly one subgroup.
For example, the string 635 can only be grouped in one subgroup [635] or in two subgroups as follows: [635] (since 6 < 8.) Another example is the string 1117 which can be grouped in one subgroup [1117] or as in the following: [1117], [1117], [1117], [1117], [1117] and [1117] 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.
Input
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.
Output
For each test case, write the result using the following format:
k. n
where k is the test case number (starting at 1,) and n is the result of this test case.
Example
Input: 635 1117 9876 bye Output: 1. 2 2. 7 3. 2
hide comments
javafreak:
20171220 19:31:41
dp with bit  n^2 log(n) solution


amitboss:
20171209 15:18:22
very simple problem , just think recursion , no need of memorization


armageddon117:
20171114 14:05:33
bad problem/judge management, wasted time and too many TLEs :/


armageddon117:
20171114 13:52:55
30 random strings, all of length 25 took 0.006s on my machine, judge says TLE :/ 

aditya9125:
20170710 09:54:01
don't know about the strictness of the test cases but I used DP, and feeling even more confident than if I had solved it through recursion with memoization. 

sonu:
20170601 09:04:52
only recursion will do!! 

hhakobyan:
20170509 08:55:00
I wasted 10+ WA on this piece of shit problem because getline() was getting some random crap at the end of the string 

datbeohbbh:
20170323 14:58:06
nice DP 

vengatesh15:
20170305 11:42:23
Recursion pass.... 

kira28:
20170108 08:08:27
Even simple recursion manages to get accepted xD xD 
Added by:  ~!(*(@*!@^& 
Date:  20090705 
Time limit:  1s2s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  ANARC 2005 