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 [635] 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 [1117] 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.

Input

Your program will be tested on a number of test cases. Each test case is specified 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 identified 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

Added by:psetter
Date:2009-07-05
Time limit:1s-2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:ANARC 2005

hide comments
2015-12-04 08:38:54 Prateek Agarwal
Wthout memoization!
2015-10-02 05:25:28 Anubhav Gupta
Awesome question!!!
2015-09-09 09:28:14 Harsh Vardhan Ladha
My 100th :D
did with top-down DP!

Last edit: 2015-09-09 09:31:29
2015-08-28 01:00:20 Apoorv Dwivedi
why is recursion better than dp for this question?
2015-06-14 20:39:28 Rishabh Joshi
Nice Problem.
Took size 30 and assumed max of sum is 256. got AC.
2015-06-11 11:31:48 Rishit Sanmukhani
1. Simple recursion works.
2. Be careful of input/output format
2015-05-10 21:01:33 Shubham Jadhav
simple recursion without memoization works..
2015-04-28 15:01:46 GAURAV CHANDEL
dp needs practice...
2014-12-24 02:26:55 Mauro Persano
Very nice problem, but had to filter out non-digit characters from input before my Scheme solution was accepted. Careful with garbage at the end of input lines. :-(
2014-10-29 08:36:37 Infinity
DP would be a bad choice here if you want the best :P

p.s. i used dp

Last edit: 2014-10-29 09:57:39
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.