Skip to code
Skip to analysis

This is a explanation of this problem from USACO's training website. I have converted it to markdown. Please do not just copy code; you will not learn anything; at least type it out and understand so you can do it yourself in the future!

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:

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

CODE

Java


C++


Pascal



ANALYSIS

Russ 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 <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

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<len; j++)
	if(t[j] != 'X')
	    return 0;

    return 1;
}

/*
 * create an md-digit number in the string s.
 * the used array keeps track of which digits are already taken.
 * s already has nd digits.
 */
void
permutation(char *s, int *used, int nd, int md)
{
    int i;

    if(nd == md) {
	s[nd] = '\0';
	if(atoi(s) > m && isrunaround(s)) {
	    fprintf(fout, "%s\n", s);
	    exit(0);
	}
	return;
    }

    for(i=1; i<=9; i++) {
	if(!used[i]) {
	    s[nd] = i+'0';
	    used[i] = 1;
	    permutation(s, used, nd+1, md);
	    used[i] = 0;
	}
    }
}

Back to top