| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 18525 | Accepted: 6177 |
Description
maintaining an inventory book. For instance, if he has just made a sign containing the telephone number "5553141", he'll write down the number "5553141" in one column of his book, and in the next column he'll list how many of each digit he used: two 1s, one
3, one 4, and three 5s. (Digits that don't get used don't appear in the inventory.) He writes the inventory in condensed form, like this: "21131435".
The other day, Klyde filled an order for the number 31123314 and was amazed to discover that the inventory of this number is the same as the number---it has three 1s, one 2, three 3s, and one 4! He calls this an example of a "self-inventorying number", and
now he wants to find out which numbers are self-inventorying, or lead to a self-inventorying number through iterated application of the inventorying operation described below. You have been hired to help him in his investigations.
Given any non-negative integer n, its inventory is another integer consisting of a concatenation of integers c1 d1 c2 d2 ... ck dk , where each ci and di is an unsigned integer, every ci is positive, the di satisfy 0<=d1<d2<...<dk<=9, and, for each digit d
that appears anywhere in n, d equals di for some i and d occurs exactly ci times in the decimal representation of n. For instance, to compute the inventory of 5553141 we set c1 = 2, d1 = 1, c2 = 1, d2 = 3, etc., giving 21131435. The number 1000000000000 has
inventory 12011 ("twelve 0s, one 1").
An integer n is called self-inventorying if n equals its inventory. It is called self-inventorying after j steps (j>=1) if j is the smallest number such that the value of the j-th iterative application of the inventory function is self-inventorying. For instance,
21221314 is self-inventorying after 2 steps, since the inventory of 21221314 is 31321314, the inventory of 31321314 is 31123314, and 31123314 is self-inventorying.
Finally, n enters an inventory loop of length k (k>=2) if k is the smallest number such that for some integer j (j>=0), the value of the j-th iterative application of the inventory function is the same as the value of the (j + k)-th iterative application. For
instance, 314213241519 enters an inventory loop of length 2, since the inventory of 314213241519 is 412223241519 and the inventory of 412223241519 is 314213241519, the original number (we have j = 0 in this case).
Write a program that will read a sequence of non-negative integers and, for each input value, state whether it is self-inventorying, self-inventorying after j steps, enters an inventory loop of length k, or has none of these properties after 15 iterative applications
of the inventory function.
Input
Output
n is self-inventorying
n is self-inventorying after j steps
n enters an inventory loop of length k
n can not be classified after 15 iterations
Sample Input
22 31123314 314213241519 21221314 111222234459 -1
Sample Output
22 is self-inventorying 31123314 is self-inventorying 314213241519 enters an inventory loop of length 2 21221314 is self-inventorying after 2 steps 111222234459 enters an inventory loop of length 2
因为是事先看题看不懂 先搜了百度 所以提前知道了人家的思路，就不算自己写的啦~最近看别人代码都是c++ 发现自己似乎已经基本掌握了输入输出 所以特意试试了 发现用printf不能输出string s...还有就是一点要注意 局部数组用j++模式输入数据时 结尾一定要加‘\0’要不会出现很大的问题（一般就是乱码）
思路：
对于每个测试数据， i 从[0-15)求inventory，将每次得到的结果同之前的结果做对比
1、如果当前结果与第 j 个结果相同，那么有以下三种结果:
a. i == 1 && j == 0 ，self-inventorying
b. j == i - 1 ，is self-inventorying after i steps
c. else ，enters an inventory loop of length i - j
2、如果全部不相同，can not be classified after 15 iterations
（人家大神的思路）
#include<iostream>
#include<string>
using namespace std;
string ic(string s)//转换函数把 普通的数转换为文章要求的格式
{
int i;
int len=s.length();
int num[10]= {0};
char xy[80];
for(i=0; i<len; i++)
{
num[s[i]-'0']++;
}
int j=0;
for(i=0; i<10; i++)
{
if(num[i]>0&&num[i]<10)
{
xy[j++]=num[i]+'0';
xy[j++]=i+'0';
}
else if(num[i]>=10)
{
xy[j++]=num[i]/10+'0';
xy[j++]=num[i]%10+'0';
xy[j++]=i+'0';
}
}
xy[j]='\0';
return xy;
}
void ic_xy(string s)//操作函数
{
string tmp=s;
string hp[16];
bool ok=false;
int i,j;
for(i=0; i<15; i++)
{
tmp=ic(tmp);
for(j=0; j<i; j++)
{
if(tmp==hp[j])
{
ok=true;
break;
}
}
if (ok)
{
if (i == 1 && j == 0)
{
cout << s << " is self-inventorying\n";
return;
}
else if (j == i - 1)
{
cout << s << " is self-inventorying after " << i << " steps\n";
return;
}
else
{
cout << s << " enters an inventory loop of length " << i - j << endl;
return;
}
}
hp[i]=tmp;
}
cout << s << " can not be classified after 15 iterations\n";
}
int main()
{
string s;
while(cin>>s)
{
if(s=="-1") break;
ic_xy(s);
}
return 0;
}