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

Solution

暴力出奇迹

先搞一个函数把这个数强拆了,然后直接判断即可

Code

/*
PROB: runround
LANG: C++
ID: yizhuor1
*/
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair

using namespace std;

typedef long long LL;
typedef pair<int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }

template <typename T> inline T read(){
    T sum = 0;
    int fl = 1,ch = getchar();
    for(; !isdigit(ch); ch = getchar()) if(ch == '-') fl = -1;
    for(; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
    return sum * fl;
}

const int maxn = 200 + 5;

int m;
int len;
int a[maxn],b[maxn],vis[maxn];

inline int calc(int x){
    int cnt = 0;
    while(x > 0){
        cnt++;
        b[cnt] = x % 10;
        x /= 10;
    }
    for(int i = 1; i <= cnt; i++){
        a[i] = b[cnt - i + 1];
    }
    return cnt;
}

inline bool check(){
    int it = 1;
    memset(vis,0,sizeof(vis));
    for(int i = 1; i <= len; i++){
        if(vis[a[it]] || !a[it]) return false;
        vis[a[it]]++;
        it = (it + a[it]) % len;
        if(!it) it = len;
    }
    if(it != 1) return false;
    return true;
}

inline void Solve (){
    while(1){
        m++;
        len = calc(m);
        if(check()){
            printf("%d\n",m);
            return;
        }
    }
}

inline void Input (){
    m = read<int>();
}

int main(){
//  freopen("runround.in","r",stdin);
//  freopen("runround.out","w",stdout);
    Input();
    Solve();
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注