GoogleCodeJam 2012 - Qualification Round / Problem C

Problem C. Recycled Numbers
さて、Preblem C。ここまでは余裕だったが、これはどうだろう。

問題文曰く、

Do you ever become frustrated with television because you keep seeing the same things, recycled over and over again? Well I personally don't care about television, but I do sometimes feel that way about numbers.

だそうだが、個人的には筆者の方が変態だと思う。

C++のSTLからsetを使う。Pair型の<演算子も定義する。(n, m)でnの方が優先。
recycleはnのstartから後ろを前に持ってきた数字を返す。
あとはひたすら全通り試していく。
ひたすらsetにinsertしても重複しないから便利。
でもって表示はsize()メソッドで表示すればfor文カウントもせずに終了できる。

コード全文は以下。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <set>

#define IN_RANGE(x, A, B)    ((A <= x)&&(x <= B))

typedef struct _pair{
    unsigned int n;
    unsigned int m;
} Pair;

bool operator<(const Pair& a, const Pair& b) {
    if(a.n == b.n) return a.m < b.m;
    else return a.n < b.n;
}

unsigned int NUMBER_OF_DIGITS;

int recycle(const unsigned int n, const unsigned int start) {
    unsigned int div_base = pow(10, start), temp = n % div_base;
    return (n / div_base) + (temp * pow(10, NUMBER_OF_DIGITS - start));
}

int main(int argc, char** argv) {
    unsigned int T, A, B, i, n, k, m;
    
    //FILE *fp = fopen("input.txt", "r");
    //FILE *fp = fopen("C-small-attempt0.in", "r");
    FILE *fp = fopen("C-large.in", "r");
    fscanf(fp, "%d", &T);
    
    for(i=0; i<T; ++i) {
        fscanf(fp, "%d %d", &A, &B);
        NUMBER_OF_DIGITS = log10(A)+1;
        if(NUMBER_OF_DIGITS == 1) {
            printf("Case #%d: %d\n", i+1, 0);
            continue;
        }
        
        std::set<Pair> pairs;
        
        for(n=A; n<=B; ++n) {
            for(k=1; k<NUMBER_OF_DIGITS; ++k) {
                m = recycle(n, k);
                if(n == m) continue;
                Pair new_pair = ((n < m) ? (Pair){n, m} : (Pair){m, n});
                if(IN_RANGE(m, A, B))
                    pairs.insert(new_pair);
            }
        }
        
        printf("Case #%d: %d\n", i+1, pairs.size());
    }
    
    fclose(fp);
    
    return EXIT_SUCCESS;
}

意外と楽だったかな。