Yêu Lập Trình

Đề bài:

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

Thuật toán:

• Chuyển n về hệ nhị phân
• Các bạn có thể tham khảo code sau

Code:

• (xem code)

#include
using namespace std;
int main()
{
    long long  a[10000005], n,dem=0,k;
    cin>>n>>k;
    while(n>0)
    {
               a[dem] = n%2;
               n = n/2;
               dem++;
    }
    for(long long  i=dem-1; i>=0;i--)
    cout<

Đề bài:

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

Thuật toán:

• Dùng mảng f[i] đánh dấu giá trị lớn nhất <= i trong dãy A.
• Vậy nên các cặp 3 số là a[i], a[j], f[m-a[i]-a[j]].
• Chú ý đề bài cho dãy A đôi một khác nhau nhé.

Code:

• C++ (xem)

#include 

using namespace std;

const int oo = 500001;
const int MAXN = 10001;
int i, j, n, m, a[MAXN], tmp, res, f[oo];

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    sort(a+1,a+n+1);
    tmp = 0;
    for (int i = a[1]; i <= m; i++) {
        if ((tmp < n) && (i >= a[tmp+1])) tmp++;
        f[i] = a[tmp];
    }
    for (int i = 1; i<= n-2; i++) {
        for (int j = i+1; j <= n-1; j++) {
            tmp = m - a[i] - a[j];
            if (tmp < 1) continue;
            tmp = f[tmp];
            if (tmp <= a[j]) continue;
            res = max(res, a[i] + a[j] + tmp);
        }
    }
    cout << res;
    return 0;
}

• Pascal (xem)

CONST fin='';
     fout='';
VAR res, i, j, n, m, x, min: longint;
    a, ok: array[1..1000000] of longint;
    f: text;
BEGIN
  Assign(f,fin);
  Reset(f);
  Readln(f,n,m);
  min:=maxlongint-1;
  For i:=1 to n do
    Begin
      Read(f,a[i]);
      ok[a[i]]:=a[i];
      If a[i]0 then
          Begin
            If (ok[x]<>a[i]) and (ok[x]<>a[j]) and (ok[i]<>0) then
              If a[i]+a[j]+ok[x]>res then res:=a[i]+a[j]+ok[x];
          End;
      End;
  Assign(f,fout);
  Rewrite(f);
  Writeln(f,res);
  Close(f);
END.

Đề 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.