Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

小弟的代码,就是不过,那位大虾给个数据测试一下?^-^

Posted by liuyao8885 at 2006-02-06 09:51:26 on Problem 1016
/*
 * problem: PKU 1016
 * author: 刘尧
 * date: 2006.2.5 
 * experience: 
 */

#include <iostream>
#include <string>

using namespace std;

bool self(string);
bool selfByStep(string);
bool loop(string);

int step;
int k;

int main()
{
	string input;

	cin >> input;

	while (input != "-1")
	{
		if (self(input))
		{
			cout << input << " is self-inventorying" << endl;
		}
		else if (selfByStep(input))
		{
			cout << input << " is self-inventorying after " << step << " steps" << endl; 
		}
		else if (loop(input))
		{
			cout << input << " enters an inventory loop of length " << k << endl; 
		}
		else
		{
			cout << input << "can not be classified after 15 iterations" << endl;
		}

		cin >> input;
	}
	return 0;
}

bool self(string str)
{
	int num[10];
	int i;

	/*
	 * initialize
	 */
	for (i = 0; i < 10; i++)
	{
		num[i] = 0;
	}

	for (i = 0; i < str.size(); i++)
	{
		num[(int)(str[i] - '0')]++;
	}

	string newString;

	for (i = 0; i <= 9; i++)
	{
		if (num[i] != 0)
		{
			if (num[i] / 10 != 0)
			{
				newString += (char)(num[i] / 10 + '0');
			}
			newString += (char)(num[i] % 10 + '0');
			newString += (char)(i + '0');
		}
	}

	if (newString == str)
	{
		return true;
	}
	return false;
}

bool selfByStep(string str)
{
	int i;
	int j;
	int num[10];
	string oldString;
	string newString;

	oldString = str;
	newString = "";
	step = 0;
	
	for (j = 0; j < 15; j++)
	{
		/*
		 * initialize
		 */
		for (i = 0; i < 10; i++)
		{
			num[i] = 0;
		}

		for (i = 0; i < oldString.size(); i++)
		{
			num[(int)(oldString[i] - '0')]++;
		}

		for (i = 0; i <= 9; i++)
		{
			if (num[i] != 0)
			{
				if (num[i] / 10 != 0)
				{
					newString += (char)(num[i] / 10 + '0');
				}
				newString += (char)(num[i] % 10 + '0');
				newString += (char)(i + '0');
			}
		}

		if (oldString == newString)
		{
			step = j;
			return true;
		}

		oldString = newString;
		newString = "";
	}

	return false;
}

bool loop(string str)
{
	int i;
	string tmp[16];

	tmp[0] = str;

	for (i = 1; i <= 15; i++)
	{
		int num[10];
		int j;
		/*
		 * initialize
		 */
		for (j = 0; j < 10; j++)
		{
			num[j] = 0;
		}

		for (j = 0; j < tmp[i - 1].size(); j++)
		{
			num[(int)(tmp[i - 1][j] - '0')]++;
		}

		for (j = 1; j <= 9; j++)
		{
			if (num[j] != 0)
			{
				if (num[j] / 10 != 0)
				{
					tmp[i] += (char)(num[i] / 10 + '0');
				}
				tmp[i] += (char)(num[i] % 10 + '0');
				tmp[i] += (char)(i + '0');
			}
		}
	}

	for (k = 2; k <= 15; k++)
	{
		for (i = 15; i > 15 - k; i--)
		{
			if (i - k >= 0)
			{
				if (tmp[i - k] == tmp[i])
					return true;
			}
		}
	}
	return false;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator