USACO 2.2 - 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

출처: http://train.usaco.org/

Runaround Number 이란 숫자가 81362일 경우 왼쪽 첫 번째 숫자부터 시작해서 선택된 숫자만큼 우측으로 이동을 해서 다음 숫자를 선택한 후 해당 과정을 다시 반복하여 모든 숫자를 한 번씩만 선택할 수 있는 숫자이다. 숫자에는 0이 들어가서는 안되고 중복된 숫자도 있어서는 안된다. 숫자 M이 주어질 경우 M 보다 큰 가장 작은 Runaround Number 을 구하는 문제.

특별한 방법이 생각나지 않아 naive 하게 풀어봤습니다.

my solving

c++

#include <fstream>
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
typedef long long ll;
 
int touchInfo;
int digit;
 
bool isAllTouched()
{
    return touchInfo == (1 << digit) - 1;
}
 
bool touch(int index)
{
    if (touchInfo & (1 << index))
        return false;
    touchInfo |= (1 << index);
    return true;
}
 
int getIndex(int resource, int order)
{
    string str = to_string(resource);
    int numLetter = str.size();
    if (order > numLetter)
        order %= numLetter;
    if (order == 0)
        order = numLetter;
    return order;
}
 
void setDigit(int number)
{
    string str = to_string(number);
    digit = str.size();
}
 
int getRunaroundNumber(int start)
{
    for (int i = start; ; i++)
    {
        setDigit(i);
        string str = to_string(i);
        
        bool ok = true;
        for (int i = 0; i < str.size(); i++)
        {
            if (str[i] == '0')
            {
                ok = false;
                break;
            }
            for (int j = i + 1; j < str.size(); j++)
            {
                if (str[i] == str[j])
                {
                    ok = false;
                    break;
                }
            }
            if (ok == false)
                break;
        }
        if (ok == false)
            continue;
 
        int index = 1;
        touchInfo = 0;
        while (true)
        {
            int idx = str[index - 1] - '0';
            idx = getIndex(i, idx + index);
            if (touch(idx - 1) == false)
                break;
            if (isAllTouched())
                return i;
            index = idx;
        }
    }
    return -1;
}
 
 
 
int main()
{
    ifstream fin("runround.in");
    ofstream fout("runround.out");
 
    int minNum;
    fin >> minNum;
    minNum++;
 
    fout << getRunaroundNumber(minNum) << endl;
 
    fin.close();
    fout.close();
    return 0;
}