USACO 2.2.3 Runaround Numbers 循环数
This post is written in Chinese. Please consider using Google Translate
开始看到这道题一头雾水,这道题叙述得并不是很好理解。我大致解释一下:输入一个数N,输出以这个数大的循环数(注意:比这个数大,至少等于N+1)。
什么是循环数? 题上给了个并不太好例子,我用147这个数解释:
- 从1开始往后数1位,就是4
- 然后从4开始往后数4位,回到开头再数是7
- 然后从7开始往后数7位,要数两圈在回到开头是1
数数的过程中要数到每一位,并且最后再回到开头,以上这样的数就是循环数。
这道题不用想得太复杂,就是从N+1开始往后枚举每一个自然数,直到找到循环数为止。
注意:111不是循环数:题上说了“没有重复数字的整数”
/*
ID: cmykrgb1
PROG: runround
LANG: C++
*/
#include <stdio.h>
#include <string.h>
FILE *fi,*fo;
unsigned long int n;
int py(int i,int j,int m)
{
while (!(i+j<=m)) j=j-m;
return i+j;
}
int rode(unsigned long int n)
{
char s[11];
int m,i,j,k;
int v[11];
sprintf(s+1,"%ld",n);
m=strlen(s+1);
v[1]=v[2]=v[3]=v[4]=v[5]=v[6]=v[7]=v[8]=v[9]=v[10]=0;
for (k=1;k<=m;k++)
if (!v[s[k]-48])
v[s[k]-48]=1;
else return 1;
v[1]=v[2]=v[3]=v[4]=v[5]=v[6]=v[7]=v[8]=v[9]=v[10]=0;
i=1;
for (k=1;k<=m-1;k++)
{
v[i]=1;
j=py(i,s[i]-48,m);
if (v[j])
return 1;
i=j;
}
j=py(i,s[i]-48,m);
if (s[j]==s[1])
return 0;
return 1;
}
int main(void)
{
fi=fopen("runround.in","r");
fo=fopen("runround.out","w");
fscanf(fi,"%ld",&n);
n++;
fclose(fi);
while (rode(n))
n++;
fprintf(fo,"%ldn",n);
fclose(fo);
return 0;
}