| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
小弟的代码,就是不过,那位大虾给个数据测试一下?^-^/*
* 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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator