Cod sursa(job #115849)

Utilizator goguGogu Marian gogu Data 17 decembrie 2007 02:45:05
Problema Multiplu Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <cstdio>
#include <bitset>
#define MaxN (1<<21)
#define c(i, j) ((i)*b+(j))

using namespace std;

unsigned n, nr, a, b, t[MaxN], cd[MaxN];
bitset<MaxN> ok, cif;

inline void test(unsigned r1, unsigned r2, unsigned T, unsigned c){
     int cod = c(r1, r2);
     if (!ok[cod]){
        t[cod] = T;
        cif[cod] = c;
        ok[cod] = 1;
        cd[nr++] = c(r1, r2);
     }
}

inline void expand(unsigned x, unsigned y){
     unsigned r1=10*x, r2=10*y;
     #define W(p) if (r1>=(a<<p)) r1-=(a<<p); if (r2>=(b<<p)) r2-=(b<<p);
     W(3) W(2) W(1) W(0)
     while (r2>=b) r2-=b;
     test(r1, r2, c(x, y), 0);
     r1++, r2++;
     if (r1>=a) r1-=a;
     if (r2>=b) r2-=b;
     test(r1, r2, c(x, y), 1);
}

inline void refa(unsigned c){
     if (c!=c(1, 1)) refa(t[c]);
     printf("%d", (int)cif[c]);
}

int main()
{
    freopen("multiplu.in", "r", stdin);
    freopen("multiplu.out", "w", stdout);
    scanf("%d %d", &a, &b);
    cd[nr++] = c(1,1);
    ok[c(1,1)]=0;
    cif[c(1,1)]=1;
    unsigned j=0;
    while (!ok[0]){
          unsigned cat = cd[j]/b;
          expand(cat, cd[j] - cat*b);
          j++;
    }
    refa(0);
}