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.


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.


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.



1. 2
2. 7
3. 2

hide comments
Varun Vohra: 2014-10-26 11:46:30

simple recursion gives ac in 0.00s
but with memoisation, time increases to 0.01s :P

Rajat (1307086): 2014-10-08 01:26:56

Solved using top down DP style......with tabulation.
Still waiting to solve DP without any help.

Last edit: 2014-10-08 01:28:02
abhi: 2014-08-09 11:34:33

little bit like assembly line problem

aqfaridi: 2014-06-14 21:36:59

@Rav why should we use scanf ??
I got ACed simply with cin,cout

Last edit: 2014-06-14 21:37:15
Rav: 2014-06-03 20:23:51

@aqfarid u r right a got my mistake

Last edit: 2014-07-03 08:15:01
Ruslan: 2014-04-24 13:47:57

Are there any tricky cases for DP solution?

Last edit: 2014-04-24 13:52:03
Adamos Ttofari: 2014-04-22 09:06:12

forgot the k. n part costed me a WA (feeling stupid)

Abdullah Enes ÖNCÜ: 2013-01-19 12:20:03

Recursion solution is faster than DP solution.

Srijan Khare: 2012-12-24 16:55:51

simple recursive solution got AC,no dp needed...small enough constraints :)

张翼德: 2012-12-19 07:14:52

easy 2D dp :D :D
take care of output format... that single space costed me 1 WA :/

Last edit: 2012-12-19 07:15:41

Added by:~!(*(@*!@^&
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