poj 1016 Numbers That Count
Numbers That Count
| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 23488 | Accepted: 8023 |
Description
"Kronecker's Knumbers" is a little company that manufactures plastic digits for use in signs (theater marquees, gas station price displays, and so on). The owner and sole employee, Klyde Kronecker, keeps track of how many digits of each type he has used by 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
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
A sequence of non-negative integers, each having at most 80 digits, followed by the terminating value -1. There are no extra leading zeros.
Output
For each non-negative input value n, output the appropriate choice from among the following messages (where n is the input value, j is a positive integer, and k is a positive integer greater than 1):
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
数字计算
描述
“克罗内克的Knumbers”是一家生产塑料数字的小公司，用于标识(剧院的帐篷、加油站的价格显示器等等)。该公司唯一的员工克莱德·克罗内克(Klyde Kronecker)通过建立一个存货账簿来记录他使用过的每种数字的数量。例如，如果他刚刚做了一个包含电话号码“5553141”的标志，他就会在他的本子的一栏里写下这个数字“5553141”，然后在下一栏里列出他使用的每个数字的个数:两个1，一个3，一个4，和三个5。(不被使用的数字不会出现在库存中。)他以简写的形式写下清单，如:“21131435”。
前几天，Klyde发了一个数字31123314的订单，惊奇地发现这个数字的库存和这个数字一样——它有三个1，一个2，三个3和一个4!他把这称为一个“自库存数字”的例子，现在他想找出哪些数字是自库存的，或者通过迭代应用下面描述的库存操作得到一个自库存数字。你是被雇来协助他调查的。
给定任意一个非负整数n，它的库存是由一系列整数c1 d1 c2 d2…Ck dk，其中每个ci和di都是无符号整数，每个ci都是正的，di满足0<=d1< dk < = 9,为每一位d出现在n, d = di发生一些我和d ci乘以小数表示的n。例如,要计算库存的5553141我们c1 = 2, d1 = 1, c2 = 1, d2 = 3,等等,给21131435。数字1000000000000有库存12011(“12个0，一个1”)。
整数n如果等于它的库存，则称为自库存。如果j是最小的数，则称为j步后(j>=1)的自库存，使库存函数的第j次迭代应用的值为自库存。例如，21221314是2步后的自查，因为21221314的库存是31321314，所以31321314的库存是31123314,31123314是自查。
最后，n进入一个长度为k (k>=2)的库存循环，如果k是最小的数，使得对于某个整数j (j>=0)，库存函数的第j次迭代应用的值与(j + k)第j次迭代应用的值相同。例如，314213241519进入一个长度为2的库存循环，因为314213241519的库存是412223241519，而412223241519的库存是314213241519，即原来的数字(在本例中我们有j = 0)。
编写一个程序，读取一个非负整数序列，对于每个输入值，声明它是自库存，在j步后自库存，进入长度为k的库存循环，还是在库存函数的15次迭代应用后没有这些特性。
输入
一个非负整数序列，每个不超过80位，后面跟着结束值-1。没有额外的前导零。
输出
对于每个非负输入值n，从以下消息中输出相应的选项(其中n为输入值，j为正整数，k为大于1的正整数):
n是self-inventorying
N是j步后的自我盘点
N进入一个长度为k的库存循环
N迭代15次后不能分类
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
代码：
#include
#include
void R(char n[85],char t[85])
{
int i,j;
int time[10]={0};
for(i=0;n[i];i++)
time[ n[i]-'0' ]++;
for(i=0,j=0;i<10;i++)
{
if(time[i])
{
if(time[i]<10)
{
t[j++]=time[i]+'0';
t[j++]=i+'0';
}
else
{
t[j++]=time[i]/10+'0';
t[j++]=time[i]%10+'0';
t[j++]=i+'0';
}
}
}
t[j]='\0';
return;
}
int main()
{
int i,j;
int flag1,flag2,flag3;
char n[16][85];
while(scanf("%s",n[0])&&(n[0][0]!='-'))
{
flag1=flag2=flag3=0;
for(i=1;i<=15;i++)
{
R(n[i-1],n[i]);
}
if(!strcmp(n[0],n[1]))
{
flag1=1;
}
if(!flag1)
{
for(i=1;i<15;i++)
{
if(!strcmp(n[i],n[i+1]))
{
flag2=i;
break;
}
}
if(!flag2)
{
for(j=1;j<=15;j++)
{
for(i=0;i<=j-2;i++)
{
if(!strcmp(n[i],n[j]))
{
flag3=j-i;
break;
}
}
if(flag3)
break;
}
}
}
if(flag1)
printf("%s is self-inventorying\n",n);
else if(flag2)
printf("%s is self-inventorying after %d steps\n",n,flag2);
else if(flag3)
printf("%s enters an inventory loop of length %d\n",n,flag3);
else
printf("%s can not be classified after 15 iterations\n",n);
}
return 0;
}