USACO/runround

Runaround Numbers循环数

目录

 [隐藏] 

• 1 描述
• 2 格式
• 3 SAMPLE INPUT
• 4 SAMPLE OUTPUT

[编辑] 描述

循环数是那些不包括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 这时你回到了起点,在经过每个数字一次后回到起点的就是循环数。如果你经过每一个数字一次以后没有回到起点, 你的数字不是一个循环数。

给你一个数字 M (在1到9位之间), 找出第一个比 M大的循环数, 输出数据保证结果能用一个无符号长整型数（42亿≈2^32-1）装下。（追加提醒：循环数每个数位都必须要访问到）

[编辑] 格式

PROGRAM NAME: runround

INPUT FORMAT:

(file runround.in)

仅仅一行, 包括M

OUTPUT FORMAT:

(file runround.out)

仅仅一行，输出第一个比M大的循环数。

[编辑] SAMPLE INPUT

81361

[编辑] SAMPLE OUTPUT

81362

/*ID: liluvu1LANG: C++TASK: runround*/#include <stdio.h>#include <string.h>#include <stdlib.h>char s[9];int set[9];char *myitoa(int num,char *str,int radix){     /* 索引表*/    char index[]="0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";    unsigned unum; /* 中间变量 */    int i=0,j,k;    /* 确定unum的值 */    if(radix==10&&num<0) /* 十进制负数 */    {    unum=(unsigned)-num;    str[i++]='-';    }    else unum=(unsigned)num; /* 其他情况 */    /* 转换 */       do{        str[i++]=index[unum%(unsigned)radix];        unum/=radix;    }while(unum);    str[i]='\0';    /* 逆序 */    if(str[0]=='-') k=1; /* 十进制负数 */    else k=0;    char temp;    for(j=k;j<=(i-1)/2;j++)    {        temp=str[j];        str[j] = str[i-1+k-j];        str[i-1+k-j] = temp;    }    return str;}int isValid(int i){	memset(s, 0x0, sizeof(s));	myitoa(i, s, 10);	int len = strlen(s);	for (int j = 0; j < len; j++){		if (s[j] == '0')			return 0;	}	for (int j = 0; j < len-1; j++){		for (int k = j+1; k < len; k++){			if (s[j] == s[k])				return 0;		}	}	return 1;}int isAllSet(int len) {	for (int k = 0; k < len; k++){		if (set[k] == 0)			return 0;	}	return 1;}int isAround(int i){	memset(s, 0x0, sizeof(s));	memset(set, 0x0, sizeof(set));	myitoa(i, s, 10);	int len = strlen(s);		int j = 0;	set[j] = 1;	int next = 0;	while (1) {		next = (j+(s[j]-'0')) % len;		if (set[next]  && next != 0) {			return 0;		} else {			j = next;		}		set[j] = 1;		if (isAllSet(len) && j == 0)			return 1;	}}int main(){	FILE *fin = NULL;	FILE *fout = NULL;	fin = fopen("runround.in", "r");	fout = fopen("runround.out", "w");	int n;	fscanf(fin, "%d\n", &n);			unsigned int i = n+1;	while (i) {		if (isValid(i)) {			if (isAround(i)) {				break;			}		}		i++;	}	fprintf(fout, "%d\n", i);	return 0;}