題目傳送門 大緻題意:
題意不難懂,對于任意的數字串n,都可以壓縮存儲為
c1 d1 c2 d2 … ck dk 形式的數字串
而存在一些特别的數字串,其壓縮前後的樣子是一模一樣的
定義這種數字串為self-inventorying
當我們把n看成原串,
A為n壓縮1次後的數字串,
B為n壓縮2次後的數字串(即A壓縮1次後的數字串)
…以此類推
K為n壓縮k次後的數字串(即K-1壓縮k-1次後的數字串)
則可以延伸出數字串n的3種屬性:
1、 n壓縮1次就馬上出現self-inventorying特性,即 n n n n n n n …
2、 n壓縮j次後的數字串J出現self-inventorying特性,即 n A B C…H I J J J J J J J
3、 n壓縮j次後的數字串J,每再壓縮K次,重新出現數字串J,即n A B… J …K J …K J…K J
其中K稱為循環間隔,K>=2。
現給定一字元串,輸出其屬性。 屬性1優于屬性2,屬性2優于屬性3。
/*
Source Code
Problem: 1016 User: 160930010
Memory: 720K Time: 141MS
Language: G++ Result: Accepted
Source Code
*/
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
#include<cstdio>
#include<cmath>
using namespace std;
char ch[100][100];
int main()
{
while(scanf("%s",ch[0])!=EOF&&strcmp(ch[0],"-1")!=0)
{
map<string,int>m;
string s;
s=ch[0];
if(!m.count(s))
m[s]=0;
int len;
int x,y;
x=y=0;
while(true)
{
int a[10];
len=strlen(ch[x]);
for(int i=0;i<=9;i++)
{
a[i]=0;
char kh=i+'0';
for(int j=0;j<len;j++)
{
if(ch[x][j]==kh)
a[i]++;
}
}
y=0;
x++;
for(int i=0;i<=9;i++)
{
if(a[i]!=0)
{
char qh[10];
int q=a[i];
int j=0;
while(q)
{
qh[j++]=(char)(q%10+'0');
q/=10;
}
for(int h=j-1;h>=0;h--)
ch[x][y++]=qh[h];
ch[x][y++]=(char)(i+'0');
}
}
ch[x][y]='\0';
s=ch[x];
if(!m.count(s)&&x<=15)
m[s]=x;
else if(m.count(s)&&x<=15)
{
if(x-m[s]==1&&m[s]!=0)
{
printf("%s is self-inventorying after %d steps\n",ch[0],m[s]);
}
else if(m[s]==0&&x==1)
printf("%s is self-inventorying\n",ch[0]);
else if(x-m[s]>1)
printf("%s enters an inventory loop of length %d\n",ch[0],x-m[s]);
break;
}
else if(x>15)
{
printf("%s can not be classified after 15 iterations\n",ch[0]);
break;
}
}
}
}