1834.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1834 on 2006-08-25 at 00:31:31 */ 
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int L = 35;

char word[L];
int len, id, pk[L];

int find(int);
int cmp(int, int, int, int);

int main()
{
	while(gets(word) != NULL && word[0] != '#') {
		len = strlen(word);
		int kind = 0;
		if(word[0] == '0') {
			if(len == 1 || word[1] == '0') kind = 0;
			else kind = 1;
		} else {
			for(id = len-1; id > 0; id--) {
				if(word[id] == '0') continue;
				memset(pk, -1, sizeof(pk));
				kind += find(0);
			}
		}
		printf("The code %s ", word);
		if(kind == 0) printf("is invalid.\n");
		else printf("can represent %d numbers.\n", kind);
	}
	
	return 0;
}

int find(int p)
{
	if(p == id) return 1;
	else if(word[p] == '0') return find(p+1);
	else if(pk[p] != -1) return pk[p];
	else {
		pk[p] = 0;
		for(int i = p; i < id; i++) {
			if(cmp(p, i+1, id, len) >= 0) break;
			pk[p] += find(i+1);
		}
		return pk[p];
	}
}
int cmp(int ab, int ae, int bb, int be)
{
	int l1 = ae-ab, l2 = be-bb;
	if(l1 != l2) return l1-l2;
	for(int i = 0; i < l1; i++)
		if(word[i+ab] != word[i+bb]) return word[i+ab]-word[i+bb];
	return 0;
}