AOJ 1180: 繰り返す10進数 / Recurring Decimals

solution

$a_i$をsetとかに貯めながらやるだけ。 計算量は$O(l \cdot 10^l)$で抑えられるので間に合う。

implementation

to_string / from_string みたいなのを関数に切り出すと楽。

#include <algorithm>
#include <cstdio>
#include <map>
#define repeat(i, n) for (int i = 0; (i) < int(n); ++(i))
#define whole(f, x, ...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x)
using namespace std;

string to_string(int a, int l) {
    string s;
    repeat (i, l) {
        s += a % 10 + '0';
        a /= 10;
    }
    whole(reverse, s);
    return s;
}
int from_string(string const & s) {
    int a = 0;
    for (char c : s) {
        a *= 10;
        a += c - '0';
    }
    return a;
}
string updated(string const & s) {
    string down = s;
    whole(sort, down);
    string up = down;
    whole(reverse, up);
    int l = s.length();
    return to_string(from_string(up) - from_string(down), l);
}
int main() {
    while (true) {
        int a, l; scanf("%d%d", &a, &l);
        if (a == 0 and l == 0) break;
        int i = 0;
        string s = to_string(a, l);
        map<string, int> used;
        while (not used.count(s)) {
            used[s] = i;
            ++ i;
            s = updated(s);
        }
        printf("%d %d %d\n", used[s], from_string(s), i - used[s]);
    }
    return 0;
}