1016numbersthatcount.cpp

算法编程题,北京大学OnlineJudge 1016NumbersThatCount

#include<stdio.h>  
#include<math.h>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<sstream>
#include<vector>
#include<set>
#include<map>
using namespace std;


//字符串处理
//变换

char s[1000];
int n;

bool Input(){
	scanf("%s",&s);
	if(strcmp(s,"-1")==0){
		return 0;
	}
	return 1;
}

void Solve(){
	int i,j,k;
	int len=strlen(s);
	map<string,int> mp;
	string str=s;
	int step=0;
	mp[str]=step;
	while(1){
		int c[10];
		memset(c,0,sizeof(c));
		for(i=0;i<str.length();i++){
			c[str[i]-'0']++;
		}
		string ts="";
		char bf[100];
		for(i=0;i<10;i++){
			if(c[i]){
				sprintf(bf,"%d%d",c[i],i);
				ts+=bf;
			}
		}
		if(str==ts){
			if(step==0){
				printf("%s is self-inventorying\n",s);
			}else{
				printf("%s is self-inventorying after %d steps\n",s,step);
			}
			break;
		}
		step++;
		if(mp.find(ts)!=mp.end()){
			j=mp.find(ts)->second;
			printf("%s enters an inventory loop of length %d\n",s,step-j); 
			break;
		}
		mp[ts]=step;
		str=ts;
		if(step>=15){
			printf("%s can not be classified after 15 iterations\n",s);
			break;
		}
	}
	return;
}

int main()
{
	//freopen("in.txt","r",stdin);
	while(Input()){
		Solve();
	}
	return 0;
}