LA - Chop Ahoy! Revisited!

From Algorithmist
Jump to navigation Jump to search

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[edit]

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[edit]

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.

Sample Input[edit]

635
1117
9876
bye

Output for the Sample Input[edit]

1. 2
2. 7
3. 2 

Analyses[edit]

/*ba yade oo */

  1. include <iostream>
  2. include <string>
  3. include <string.h>
  4. include <algorithm>
  5. include <stdio.h>
  6. include <math.h>
  7. include <cstring>
  8. include <sstream>
  9. include <queue>
  10. include <vector>

using namespace std;

  1. define PI 3.14159265358997
  2. define absol(x) ((x)>(0) ? (x):(-1)*(x))
  3. define pow2(x) (x*x)
  4. define EPS 1e-7
  5. define INF 0x7FFFFFFF
  6. define MAX 30

int num[MAX],sum[MAX]; int t[MAX][MAX*10]; int main () {

char ch[MAX]; int len; int Case=1; while (cin>>ch) { if (!strcmp(ch,"bye")) break; len=strlen(ch); sum[0]=0; for (int i=0;i<len;i++) { num[i+1]=ch[i]-'0'; sum[i+1]=sum[i]+num[i+1]; } memset(t,0,sizeof(t)); len++;

//initialize dp table for (int i=0;i<MAX*10;i++) t[0][i]=1; for (int i=sum[1];i<=sum[len-1];i++) t[1][i]=1;

for (int i=2;i<len;i++) for (int k=0;k<=sum[len-1];k++) { for (int j=i-1;j>=0;j--) { int maxi=sum[i]-sum[j]; if (k>=maxi) t[i][k]+=t[j][maxi]; } }

printf("%d. %d\n",Case++,t[len-1][sum[len-1]]); } return 0;

}