Problem 57: Runaround Numbers
Runaround Numbers

Runaround numbers are integers with unique digits, none of which is zero (e.g., 81362) that also have an interesting property, exemplified by this demonstration:

  • If you start at the left digit (8 in our number) and count that number of digits to the right (wrapping back to the first digit when no digits on the right are available), you'll end up at a new digit (a number which does not end up at a new digit is not a Runaround Number). Consider: 8 1 3 6 2 which cycles through eight digits: 1 3 6 2 8 1 3 6 so the next digit is 6.
  • Repeat this cycle (this time for the six counts designed by the `6') and you should end on a new digit: 2 8 1 3 6 2, namely 2.
  • Repeat again (two digits this time): 8 1
  • Continue again (one digit this time): 3
  • One more time: 6 2 8 and you have ended up back where you started, after touching each digit once. If you don't end up back where you started after touching each digit once, your number is not a Runaround number.

Given a number M (that has anywhere from 1 through 9 digits), find and print the next runaround number higher than M, which will always fit into an unsigned long integer for the given test data.

PROGRAM NAME: runround

INPUT FORMAT

A single line with a single integer, M

SAMPLE INPUT (file runround.in)

81361

OUTPUT FORMAT

A single line containing the next runaround number higher than the input value, M.

SAMPLE OUTPUT (file runround.out)

81362

题意:

例如对81362,默认取第一个数‘8',向后数8位,如果位数不够8个,则继续从头开始数起,直到‘6’,接着是‘2’,再接着
是‘1’,再到‘3’,这样所有数都visit过了。接着再到‘8’,能回到起点(必须要回到起点)。在满足以上条件下,要求
每位上的数是唯一的且不含0,这样的一个数就是runround number。

对给出的n,求出n后面得第一个runround number。

代码如下:
/*
LANG: C
TASK: runround
*/
#include
<stdio.h>
int s[20];
int T[10];
int turn(int n)
{
    
int i = 0;
    
while (n)
    {
        s[i] 
= n % 10;
        T[s[i]] 
= 0;//初始化标记数组T 
        i++;
        n 
/= 10;
    }
    
return i;
}
int Ok(int len)
{
    
int i, pre, r, local;
    
if (len == 0)
    {
        
return 0;
    }
    
for (i = len - 1; i >= 0; i--)
    {
        
if (s[i] == 0 || T[s[i]] == 1)//判0和判是否存在数重复 
        {
            
return 0;
        }
        T[s[i]] 
= 1;//对扫过的数标记 
    }
    
for (i = len - 1; i >= 0; i--)
    {
        T[s[i]] 
=  0;
    }
    pre 
= s[len-1];
    T[pre] 
= 1;
    r 
= 1;
    local 
= len - 1;
    
while (1)
    {
        pre 
%= len;
        
//寻找下一个数的下标 
        if (local - pre >= 0)//如果下一个数在pre后面,及下标小于pre的下标 
        {
            local 
=  local - pre;
        }
        
else
        {
            local 
= len + (local - pre);//如果下一个数在pre前面,即下标大于pre的下标 
        }
        pre 
= s[local];
        
if (r == len)//全部扫描过 
        {
            
if (pre == s[len-1])//如果能回到起点 
            {
                
return 1;
            }
            
else
            {
                
return 0;
            }
        }
        
else if (r != len && T[pre])//在没扫描所有数就返回到被标记过的数,则一定不能返回起点 
        {
            
return 0;
        }        
        T[pre] 
= 1;//标记扫描过的数 
        r++;//扫描个数加1    
    }                 
}
int main()
{
    freopen(
"runround.in""r", stdin);
    freopen(
"runround.out""w", stdout);
    
int n, len, t, i;
    scanf(
"%d"&n);
    
for (i = n + 1; ; i++)
    {
        len 
= turn(i);
        t 
= Ok(len);
        
if (t)
        {
            
break;
        }
    }
    printf(
"%d\n", i);
    fclose(stdin);
    fclose(stdout);
    
//system("pause");
    return 0;    
}