Run, Run, Runaround Numbers

王朝other·作者佚名  2006-01-10
窄屏简体版  字體: |||超大  

Run, Run, Runaround Numbers

An N-digit runaround number is characterized as follows:

It is an integer with exactly N digits, each of which is between 1 and 9, inclusively. The digits form a sequence with each digit telling where the next digit in the sequence occurs. This is done by giving the number of digits to the right of the digit where the next digit in the sequence occurs. If necessary, counting wraps around from the rightmost digit back to the leftmost. The leftmost digit in the number is the first digit in the sequence, and the sequence must return to this digit after all digits in the number have been used exactly once. No digit will appear more than once in the number. For example, consider the number 81362. To verify that this is a runaround number, we use the steps shown below:

Start with the leftmost digit, 8: 1 3 6 2 Count 8 digits to the right, ending on 6 (note the wraparound): 1 3 2 Count 6 digits to the right, ending on 2: 1 3 Count 2 digits to the right, ending on 1: 3 Count 1 digit to the right, ending on 3: Count 3 digits to the right, ending on 8 (where we began): Input and OutputIn this problem you will be provided with one or more input lines, each with a single integer R having between 2 and 7 digits followed immediately by the end of line. For each such number, determine the smallest runaround number that is equal to or greater than R. There will always be such a number for each of the input numbers. Display the resulting number in the format illustrated below. The last line of the input will contain only the digit 0 in column 1.

Sample Input

12

123

1234

81111

82222

83333

911111

7654321

0

Sample Output

Case 1: 13

Case 2: 147

Case 3: 1263

Case 4: 81236

Case 5: 83491

Case 6: 83491

Case 7: 913425

Case 8: 8124956

//////////////////////////////////////Code//////////////////////////////////

// Runaround Numbers.cpp : Defines the entry point for the console application.

//

#include "stdafx.h"

#include "fstream"

#include "string"

#include "algorithm"

#include "set"

using namespace std;

bool is_available(string str)

{

if(count(str.begin(),str.end(),'0')>0)

return false;

for(basic_string<char>::const_iterator iter = str.begin();

iter != str.end(); iter++)

{

if(count(str.begin(),str.end(),*iter) >1)

return false;

}

return true;

}

bool can_runaround(const string str)

{

int index = 0;

set<int> used_arr;

int t;

do

{

t = index + (str[index] - '0');

t = t % str.length();

if(used_arr.count(index))

return false;

used_arr.insert(index);

index = t;

}

while(index != 0);

used_arr.insert(index);

return used_arr.size() == str.length();

}

int generate_next(string &str)

{

char buff[12];

str.copy(buff,12);

int i;

i = atoi(str.data());

while(!is_available(buff))

{

i++;

itoa(i,buff,10);

}

str =buff;

return 0;

}

int main(int argc, char* argv[])

{

string data;

ifstream fin("in.dat");

ofstream fout("out.txt");

int i = 0;

while(fin>> data && data != "0")

{

while(!(is_available(data) && can_runaround(data)))

{

generate_next(data);

}

i++;

fout << "Case " << i <<": " << data << endl;

}

return 0;

}

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
 
 
© 2005- 王朝網路 版權所有 導航