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

hide comments
anupam_akib: 2021-05-25 20:36:53

No need to use DP here. Backtracking solution works for me.

ayushpandia: 2020-11-23 19:43:57

Bottom-up solution was a challenge for me

aryan29: 2020-03-30 20:54:12

Easy DP

Last edit: 2020-03-30 21:21:08
dkkv0000: 2020-01-19 17:15:04

easy peasy lemon squeezy AC in one go!!!!!!!!!

dmorgans: 2019-05-27 12:17:30

it is a backtracking problem with memoization

zakir068: 2019-02-26 17:39:36

dont need to memorize.
Just get the concept (example in the question helps) and recursion;

md_meraj1319: 2018-12-29 09:20:09

this is not a dp problem..

manjeet_: 2018-07-18 19:18:46

similar to this:- https://www.spoj.com/problems/ROCK/

soham_12345: 2018-06-16 10:19:29

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. :(

Edit: NVM got AC. Dp work fine. Hint: Complexity : O(n^2*max_sum)

Last edit: 2018-06-16 10:24:08
waqar_ahmad224: 2018-03-17 10:17:30

Nice one , solved using backtracking , AC in 1 go


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