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
shivam_2296: 2017-12-25 18:12:03

AC in one go..!!
love DP ;)

Last edit: 2017-12-25 18:12:19
javafreak: 2017-12-20 19:31:41

dp with bit - n^2 log(n) solution

amitboss: 2017-12-09 15:18:22

very simple problem , just think recursion , no need of memorization

aditya9125: 2017-07-10 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: 2017-06-01 09:04:52

only recursion will do!!

hhakobyan: 2017-05-09 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: 2017-03-23 14:58:06

nice DP

vengatesh15: 2017-03-05 11:42:23

Recursion pass....

kira28: 2017-01-08 08:08:27

Even simple recursion manages to get accepted xD xD

coolio_1: 2016-10-01 14:37:30

simple recursion works!!

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