首页 > 代码库 > USACO Section 2.2 Runaround Numbers

USACO Section 2.2 Runaround Numbers

/*
ID: lucien23
PROG: runround
LANG: C++
*/

#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;

int main()
{
	ifstream infile("runround.in");
	ofstream outfile("runround.out");
	if(!infile || !outfile)
	{
		cout << "file operation failure!" << endl;
		return -1;
	}

	unsigned long M;
	infile >> M;
	int numCnt[9];
	while (1) 
	{
		M++;

		char strNum[10];
		sprintf(strNum, "%ld", M);
		int len = strlen(strNum);
		//验证M中无0
		if (strchr(strNum, '0') != NULL)
		{
			continue;
		}
		//验证M中所有的数字都不一样
		int *flags = new int[len]();
		int i;
		for (i=0; i<9; i++)
		{
			numCnt[i] = 0;
		}
		for (i=0; i<len; i++)
		{
			numCnt[strNum[i]-'0'-1]++;
		}
		for (i=0; i<9; i++)
		{
			if (numCnt[i] >= 2)
				break;
		}
		if (i < 9)
		{
			continue;
		}
		//验证数字规律
		int pos = 0;
		i = 0;
		while (i++ < len)
		{
			flags[pos] = 1;
			int count = strNum[pos] - '0';
			pos = (count + pos) % len;
		}

		for (i=0; i<len; i++)
		{
			if (flags[i] == 0)
			{
				break;
			}
		}
		delete[] flags;
		//判断规律是否符合
		if (i == len && pos == 0)
		{
			outfile << M <<endl;
			break;
		}
	}

	return 0;
}