USACO 2.2.3 Runaround Numbers 循环数

开始看到这道题一头雾水,这道题叙述得并不是很好理解。我大致解释一下:输入一个数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;
}

相关日志