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
没什么好说的神搜一下即可，注意题意；
/*
ID:nealgav1
PROG:runround
LANG:C++
*/
#include
#include
using namespace std;
const int mm=1234;
bool vis[mm];
int len,_num;
int num;
bool flag;
void dfs(char[],int,int);
bool charge(int shu)
{ len=0;
memset(vis,0,sizeof(vis));
char s[33];
while(shu)
{
//cout>num;
// coutUSER: Neal Gavin Gavin [nealgav1]
TASK: runround
LANG: C++
Compiling...
Compile: OK
Executing...
Test 1: TEST OK [0.000 secs, 3336 KB]
Test 2: TEST OK [0.011 secs, 3336 KB]
Test 3: TEST OK [0.011 secs, 3336 KB]
Test 4: TEST OK [0.011 secs, 3336 KB]
Test 5: TEST OK [0.076 secs, 3336 KB]
Test 6: TEST OK [0.054 secs, 3336 KB]
Test 7: TEST OK [0.108 secs, 3336 KB]
All tests OK.Your program (‘runround’) produced all correct answers! This is your
submission #2 for this problem. Congratulations!
Here are the test data inputs:
------- test 1 ----
99
------- test 2 ----
111110
------- test 3 ----
134259
------- test 4 ----
348761
------- test 5 ----
1000000
------- test 6 ----
5000000
------- test 7 ----
9000000Keep up the good work!
Thanks for your submission!
Runaround NumbersRuss Cox
The trick to this problem is noticing that since runaround numbers must have unique digits, they must be at most 9 digits long. There are only 9! = 362880 nine-digit numbers with unique digits, so there are fewer than 9*362880 numbers with up to 9 unique digits. Further, they are easy to generate, so we generate all of them in increasing order, test to see if they are runaround, and then take the first one bigger than our input.
#include
#include
#include
#include
int m;
FILE *fout;
/* check if s is a runaround number; mark where we've been by writing 'X' */
int
isrunaround(char *s)
{
int oi, i, j, len;
char t[10];
strcpy(t, s);
len = strlen(t);
i=0;
while(t[i] != 'X') {
oi = i;
i = (i + t[i]-'0') % len;
t[oi] = 'X';
}
/* if the string is all X's and we ended at 0, it's a runaround */
if(i != 0)
return 0;
for(j=0; j m && isrunaround(s)) {
fprintf(fout, "%sn", s);
exit(0);
}
return;
}
for(i=1; iAnother look
Diego Exactas from Argentina has a better solution that runs extremely quickly.
This is my solution, with doesn’t generate all solutions, but just looks for the next one.
#include
#include
#include
#include
#define INPUT_FILE "runround.in"
#define OUTPUT_FILE "runround.out"
using namespace std;
void NextNumber(std::vector& number, int Digits) {
number[Digits - 1]++;
for (int i = Digits - 1; i >= 0; i--) {
if (number[i] == 10) {
number[i] = 1;
if (i == 0) {
number.insert (number.begin(),1);
return;
} else
number[i - 1]++;
}
}
return;
}
bool CheckElement(std::vector::iterator first,
std::vector::iterator last, int val) {
while (first & number) {
std::vector old = number;
for (int i = 1; i & number) {
std::vector used(10,false);
for (int i = 0, pos = 0, val = number[0]; i 服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
机房租用，北京机房租用，IDC机房托管， http://www.fwqtg.net
采集Java程序JVM信息 创建 Spring Boot Application 应用程序 进行 https://start.spring.io 使用版本 Spring Boot v2.7.11和JDK 17，并创建一个具有以下依赖项的简单JAVA应用程序。 …
