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;
}

上次修改时间 2017-02-03

相关日志