站点图标 陌路寒暄

2.2.3 Runaround Numbers 循环数

code

2.2.3 Runaround Numbers 循环数

时间： 1ms        内存：64M

描述：

循环数是那些不包括0这个数字的没有重复数字的整数 (比如说, 81362) 并且同时具有一个有趣的性质, 就像这个例子:

如果你从最左边的数字开始 ( 在这个例子中是8) 数最左边这个数字个数字到右边(回到最左边如果数到了最右边),你会停止在另一个新的数字(如果没有停在一个不同的数字上，这个数就不是循环数). 就像: 8 1 3 6 2 从最左边接下去数8个数字: 1 3 6 2 8 1 3 6 所以下一个数字是6.
重复这样做 (这次从“6”开始数6个数字) 并且你会停止在一个新的数字上: 2 8 1 3 6 2, 也就是2.
再这样做 (这次数两个): 8 1
再一次 (这次一个): 3
又一次: 6 2 8 这是你回到了起点, 在从每一个数字开始数1次之后. 如果你在从每一个数字开始数一次以后没有回到起点, 你的数字不是一个循环数。
给你一个数字 M (在1到9位之间), 找出第一个比 M大的循环数, 并且一定能用一个无符号长整形数装下。

输入：

仅仅一行, 包括M

输出：

仅仅一行，包括第一个比M大的循环数。

示例输入：

81361

示例输出：

81362

提示：

参考答案（内存最优[1268]）：

/*
ID: supersnow0622
PROG: test
LANG: C++
*/
#include <iostream>
#include <fstream>
#include <string>
#include<math.h>
#include<memory.h>
using namespace std;
int used[10],exist[10];
bool allused()
{
  for(int i=1;i<10;i++)
    if(exist[i]==1&&used[i]==0)
      return false;
    return true;
}
bool judge(unsigned int n)
{
   memset(exist,0,sizeof(exist));
   string str="";
   int temp,sum=0;
   while(n!=0)
   {
     temp=n%10;
     if(temp==0||exist[temp]==1)
     return false;
     exist[temp]=1;
     sum+=temp;
     str+=temp+'0';
     n/=10;
   }

   memset(used,0,sizeof(used));
   int index=str.length()-1;
   used[str[index]-'0']=1;
    while(!allused())
    {
        index-=str[index]-'0';
        index=(index+str.length()*10)%str.length();
        if(used[str[index]-'0']) return false;
        used[str[index]-'0']=1;
        if(str[index]==str[str.length()-1])
          return false;
     }
        index-=str[index]-'0';
        index=(index+str.length()*10)%str.length();
    if(str[index]==str[str.length()-1])
     return true;
return false;
}
int main() {
 //   ofstream fout ("test.out");
  //  ifstream fin ("test.in");
    unsigned int M;
    cin>>M;
    for(unsigned int i=M+1;i<1<<24;i++)
    {
       if(judge(i))
       {
         cout<<i;
         break;
       }
    }
    return 0;
}

参考答案（时间最优[48]）：

/*
ID:ytjiang1
TASK:runround
LANG:C++
*/
#include <iostream>
#include <fstream>
#include <string.h>
using namespace std;
int che[10];
int main()
{
    long long num;
  //  ifstream cin ("runround.in");
  //  ofstream cout ("runround.out");
    cin>>num;
    num++;
    int n[20];
    while(1)
    {
        memset(che,0, sizeof(che));
        che[0] = 1;
        int wei=0;
        int i = 0;
        int t = num;
        while(t)
        {
            wei ++;
            if(che[t % 10] == 1)
            {
                num ++;
                t = num;
                wei = 0;
                memset(che,0, sizeof(che));
                che[0] = 1;
                continue;
            }
            che[t % 10] = 1;
            t /= 10;
        }
        t = num;
        i = wei;
        while(i)
        {
            i--;
            n[i] = t % 10;
            t /= 10;
        }

        int ans[20];
        memset(ans, 0, sizeof(ans));
        i = 0;
        t = n[0];
        int now = 0;
        while(i<wei)
        {

            now =(t + now )% wei;
            if(ans[now] == 1)
                 break;
            ans[now] = 1;
            t = n[now];
            i++;
        }
        if(i == wei)
        {
              cout<<num<<endl;
            break;
        }
        else
            num ++;

    }
    return 0;
}

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。

退出移动版