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

相關日誌