USACO 2.2.3 Runaround Numbers 循環數

本文正體字版由OpenCC轉換

開始看到這道題一頭霧水，這道題敘述得並不是很好理解。我大致解釋一下：輸入一個數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

相關日誌