LUCKYNUM – spoj

Đề bài:

• http://vn.spoj.com/problems/LUCKYNUM/

Thuật toán:

• Duyệt BFS.
• F[i,j] là phần dư của 88..866..6 (i số 8, j số 6) cho X.

Code:

• C++ (xem)

#include 
#define fi first
#define se second
#define mp make_pair

using namespace std;

const int MAXN = 203;
const int MAXQ = MAXN * MAXN;
int i, j, t, X, f[MAXN][MAXN];
queue< pair > q;

int mu (int n) {
    int tmp = 1;
    for (int i = 1; i <= n; i++) tmp = (tmp * 10) % X;
    return tmp;
}

void print(int x, int y) {
    for (int i = 1; i <= x; i++) cout << 8;
    for (int i = 1; i <= y; i++) cout << 6;
    cout << endl;
}

void bfs() {
    while (!q.empty()) q.pop();
    q.push( make_pair(0,0) );
    pair x;
    while (q.size()) {
        x = q.front();
        q.pop();
        if (x.fi+x.se >= MAXN) {cout << -1 << endl; return;}
        if (f[x.fi][x.se+1] == 0) q.push(mp(x.fi,x.se+1));
        if (f[x.fi+1][x.se] == 0) q.push(mp(x.fi+1,x.se));
        f[x.fi+1][x.se] = (f[x.fi][x.se] + mu(x.fi+x.se) * 8) % X;
        f[x.fi][x.se+1] = (f[x.fi][x.se] * 10 + 6) % X;
        if (f[x.fi][x.se+1] == 0) {print(x.fi,x.se+1); return;}
        if (f[x.fi+1][x.se] == 0) {print(x.fi+1,x.se); return;}
    }
}

void process() {
    cin >> X;
    memset(f,0,sizeof(f));
    bfs();
}

int main() {
    cin >> t;
    for (int i = 1; i <= t; i++) {
        process();
    }
    return 0;
}

• Pascal (xem)

const   fi='';
        fo='';
        maxn=201;
type    point=record
                x,y:integer;
                end;
var     q:array[1..maxn*maxn+1] of point;
        f:array[0..maxn,0..maxn] of longint;
        t,n:integer;
        d,c:longint;
procedure xuat(x,y:integer);
var     i:integer;
begin
    for i:=1 to x do write('8');
    for i:=1 to y do write('6');
    writeln;
end;
procedure push(x,y:integer);
begin
    inc(c);
    q[c].x:= x;
    q[c].y := y;
end;
function mu(a:integer):longint;
var     i:integer;
        tam:longint;
begin
    tam:=1;
    for i:=1 to a do tam:=(tam*10) mod n;
    exit(tam);
end;
procedure xuly;
var
        x,y:integer;
begin

    d:=1;c:=1;
    q[1].x:=0;q[1].y:=0;

    while d<=c do
        begin
            x:=q[d].x; y:=q[d].y;
            inc(d);
            if (x+y>0) and (f[x,y]=0) then begin xuat(x,y); exit; end;

            if (y+1+x<=200) and (f[x,y+1]=-1) then
                begin
                    f[x,y+1]:= (f[x,y]*10 +6) mod n ;
                    push(x,y+1);
                end;

            if (x+1+y<=200) and (f[x+1,y]=-1)  then
                begin
                    f[x+1,y]:=(8*mu(x+y) mod n + f[x,y] ) mod n ;
                    push(x+1,y);
                end;

            if x+y>200 then begin writeln(-1); exit; end;
        end;
        writeln(-1);
end;
procedure init;
var     i,j:integer;
begin
    for i:=0 to 200 do
        for j:=0 to 200 do f[i,j]:=-1;

        f[0,0]:=0;
end;
procedure main;
var     i:integer;
begin
    assign(input,fi);reset(input);
    assign(output,fo);rewrite(output);

    readln(t);
    for i:=1 to t do
        begin

            readln(n);
            init;
            xuly;

        end;

    close(input);close(output);
end;
begin
    main;
end.