V8SCORE – SPOJ

Đề bài: http://vn.spoj.com/problems/V8SCORE/

Thuật toán:

  • (đang cập nhập)

Code:

const   fi='';
        fo='';
        oo=20;
var     i,j,tmp2:longint;
        s,k,n,tong,ss,tmp:longint;
        a:array[1..oo,1..oo] of longint;
        c:array[0..200] of boolean;
        trace:array[0..oo] of longint;
        f:text;
        tim:boolean;
procedure nhap;
begin
    assign(f,fi);
    reset(f);
    readln(f,s,k,n);
    for i:=1 to n do
        for j:=1 to k do read(f,a[i,j]);
    close(f);
end;
function max2(x,y:integer):integer;
begin
    if x>y then max2:=x else max2:=y;
end;
procedure init;
begin
    for i:=1 to n do c[a[i,k]]:=true;
end;
procedure thu(x,y,tong:integer);
var     j,ss:integer;
begin
if not(tim) then
 if y<k then
 begin
   if a[x,y]>=trace[y-1] then
   begin
        tmp:=tong+(k-y+1)*a[x,y];
        if tmp<=s then
                begin
                        tong:=tong+a[x,y];
                        trace[y]:=a[x,y];
                        for j:=1 to n do thu(j,y+1,tong);
                end;
   end;
 end else
        begin
        if (c[s-tong]) and (s-tong>=trace[k-1]) then
                begin
                trace[k]:=s-tong;
                tim:=true;
                end;
        end;
end;
procedure xuly;
begin
    trace[0]:=-1;
    for i:=1 to n do
    begin
        if tim then exit else
        begin
                fillchar(trace,sizeof(trace),0);
                thu(i,1,0);
        end;
    end;
end;
procedure inkq;
begin
    assign(f,fo);
    rewrite(f);
    if tim then
    begin
        writeln(f,'YES');
        for i:=1 to k do write(f,trace[i],' ');
    end
        else writeln(f,'NO');
    close(f);
end;
begin
    nhap;
    init;
    xuly;
    inkq;
end.

QBMARKET – SPOJ

Đề bài: http://vn.spoj.com/problems/QBMARKET/

Thuật toán:

Gọi  L[j] là số cách mua hàng khi có j đồng .Như vậy khi ta có khi ta mua các mặt hàng từ (1..i-1) hết j đồng và số cách mua là L[j] thì khi xét đến mặt hàng thứ i với k là số lượng mặt hàng i mà ta sẽ mua thì số cách mua hết j+c[i]*k ( S) đồng sẽ tăng thêm một lượng L[j]. Ta có công thức quy hoạch động :

Nếu j+c[i]*k<=S thì L[j+c[i]*k]:=L[j+c[i]*k]+L[j] (j=S..1,i=1..n,k=1..mi). Khởi tạo L[0]=1, L[1..S]=0.

Tại sao vì j+c[i]*k<=S vì nếu lớn hơn S rồi ta không cần quan tâm vì ta chỉ có tối đa S đồng thôi.

Trong qua trình cài đặt ta thấy nếu ta duyệt nếu ta duyệt j tăng dần từ 1 đến S, k tăng dần từ 1 đến mi thì sẽ xảy ra trường hợp như sau:j=0,L[0]=1,i=1,c[1]=1. Đầu tiên k=1 thì L[0+1*1]=L[0]+L[2]=1, k=2 thì L[0+1*2]=L[0]+L[2]=1.
Tăng  j và i giữ nguyên, j=1.Đầu tiên k=1 thì L[1+1*1]=L[1]+L[1]=2 đến đây ta đã thấy vô lí L[2] với i=1 không thể nào bằng 2 được mà L[2]=1. Trường hợp này là do khi j=j1 ta tính L[j1+x], j tăng lên j1+x ta tính L[j1+x+y] ta có

L[j1+x+y]=L[j1+x+y]+L[j1+x] mà khi đó L[j1+x] không còn là số cách mua hết j1+x đồng từ i-1 mặt hàng (1..i-1) mà là mua i mặt hàng (1..i) vì ta vừa tính L[j1+x] khi mua k mặt hàng i mà c[i]*k=x, tất nhiên k>=1.Nói ngắn gọn bạn phải hiểu L[j] trong công thức trên là số cách mua hết j đồng từ i-1 mặt hàng (1..i-1)

Để khắc phục tình trạng này ta duyệt j giảm từ S về 0 .

Code bên dưới nộp sẽ được 85 điểm do chạy quá thời gian. Nếu bài cho time limit 1s thì sẽ được 100 điểm. Tất nhiên thuật toán trên hoàn toàn đúng.

Code:

Const
        fi='';
        fo='';
        maxn=500;
        maxs=100000;
 
Type
        arr1    =array[1..maxn] of longint;
        arr2    =array[0..maxs] of int64;
 
Var
        n,s     :longint;
        c,m     :arr1;
        L       :arr2;
        f       :text;
 
procedure nhap;
var
        i       :longint;
begin
        assign(f,fi);
        reset(f);
        readln(f,s,n);
        for i:=1 to n do readln(f,c[i],m[i]);
        close(f);
end;
 
procedure solution;
var
        i,j,k   :longint;
begin
        L[0]:=1; {Neu co 0 dong thi coi la co mot cach la khong mua gi ca}
        for j:=1 to s do L[j]:=0; { Khoi tao mang L }
        for i:=1 to n do
                for j:=s downto 0 do
                        if L[j]>0 then
                        	for k:=1 to m[i] do
                                if j+k*c[i]<=s then
                                        L[j+c[i]*k]:=L[j]+L[j+c[i]*k];
end;
 
procedure xuat;
begin
        assign(f,fo);
        rewrite(f);
        write(f,L[s]); {Ket qua nam o L[s]}
        close(f);
end;
 
begin
        nhap;
        solution;
        xuat;
end.

LINEGAME – SPOJ

Đề bài: http://vn.spoj.com/problems/LINEGAME/

Thuật toán:

Đây là một bài quy hoạch động khá hay. Trước hết ta có thể ăn được 60% số Test bằng duyệt, hoặc Quy hoạch động với độ phức tạp O(n2), thậm chí làm Quy hoạch động với độ phức tạp O(n) mà dùng hai mảng một chiều 106 phần tử chúng ta cũng chỉ đạt 60% số test.

Tôi xin trình bày ngắn gọn công thức sau với độ phức tạp O(n).

Gọi F[i,1] là số điểm lớn nhất có thể đạt được khi xét tới ô thứ i và ô cuối cùng mang dấu ‘+’, tương tự F[i,2] là số điểm lớn nhất có thể đạt được khi xét tới ô thứ i và ô cuối cùng mang dấu ‘-’ ta thấy:

F[i,1]=Max(F[i-1,2]+a[i],F[i-1,1]).

F[i,2]=Max(F[i-1,1]-a[i],F[i-1,2]).

Với công thức trên chương trình có thể chạy với n=106 trong 1s là cùng, nhưng đối với Time Limit nhỏ hơn như 0.5s thì rất dễ quá thời gian một cách đáng tiếc.

Ta để ý như sau: Tính F[i,1] và F[i,2] chỉ phụ thuộc vào F[i-1,1] và F[i-1,2] như vậy ta có thể dùng 3 biến m1,m2,m3 với vai trò như sau: m1 lưu F[i-1,1], m2 lưu F[i-1,2], m3 là trung gian và sau khi tính xong F[i,1] và F[i,2] thì m1,m2 lại được ghi đè lên giá trị của m1 và m2 lúc trước. Trong quá trình tính ta luôn cập nhật m1 và m2 với Max.

Trong chương trình chính ta tính luôn m1,m2 song song với đọc mảng a. Nói chung chương trình dưới đây chỉ sử dụng 7 biến kiểu nguyên và 1 biến tệp. Rất tiết kiệm bộ nhớ và CT ngắn gọn.

Độ phức tạp của thuật toán: O(n)
Code:

Const
        fi='';
        fo='';
 
Var
        n,a,i   :longint;
        m1,m2,m3:int64;
        max     :int64;
        f       :text;
Begin
        assign(f,fi);
        reset(f);
        max:=0;m1:=0;m2:=0;
        readln(f,n);
        for i:=1 to n do
                begin
                        read(f,a);{Doc a[i]}
                        m3:=m1;{Giu lai F[i-1,1] de tinh m2}
                        if m1<m2+a then m1:=m2+a;{m1=F[i,1]=Max(F[i-1,2]+a[i],F[i-1,1])}
                        if m2<m3-a then m2:=m3-a;{m2=F[i,2]=Max(F[i-1,1]+a[i],F[i-1,2])}
                        if m1>max then max:=m1;{Cap nhat F[i,1] voi Max}
                        if m2>max then max:=m2;{Cap nhat F[i,2] voi Max}
                end;
        close(f);
        assign(f,fo);
	      rewrite(f);
        write(f,max);
        close(f);
End.

PARIGAME – SPOJ

Đề bài:

Thuật toán:

Gọi L[i,j] là trạng thái thắng (TRUE) hay thua (FALSE) khi bảng trò chơi có kích thước i x j của người đi trước.

Ta thấy:

  • L[i,j]=TRUE tương đương L[i-1,j]=FALSE nếu tổng các số trên hàng i chẵn, hoặc L[i,j-1]=FALSE nếu tổng các số trên cột j chẵn.
  • L[i,j]=FALSE tương đương L[i-1,j]=TRUE hoặc tổng các số trên hàng i lẻ và L[i,j-1]=TRUE hoặc tổng các số trên cột j lẻ.

Tóm lại ta có: L[i,j]= x or y;

x=TRUE nếu tổng các số trên hàng i chẵn và L[i-1,j]=FALSE; x=FALSE trong trường hợp còn lại.

y=TRUE nếu tổng các số trên cột j chẵn và L[i,j-1]=FALSE ; y=FALSE trong trường hợp còn lại.

Vấn đề còn lại là việc tính tổng các số trên hàng i và cột j:

Gọi S[i,j] là tổng các số trên bảng trò chơi kích thước i x j Ta tính S[i,j] tương tự bài BONUS:

S[i,j]:=S[i-1,j]+S[i,j-1]+a[i,j]-S[i-1,j-1];

Gọi h là tổng các số trên hàng i, ta có : h=S[i,j]-S[i-1,j];

Gọi c là tổng các số trên cột j, ta có : c=S[i,j]-S[i,j-1];

Từ việc tính trước mảng S ta đưa bài toán có độ phức tạp O(n2) tốt hơn rất nhiều nếu tính trực tiếp sẽ có độ phức tạp O(n3)

Code:

Const
        tfi='';
        tfo='';
        maxn=500;
 
Type
        arr1    =array[1..maxn,1..maxn] of longint;
        arr2    =array[0..maxn,0..maxn] of qword;
        arr3    =array[0..maxn,0..maxn] of boolean;
 
Var
        n       :longint;
        k       :longint;
        a       :arr1;
        s       :arr2;
        L       :arr3;
        fi,fo   :text;
 
Procedure nhap;
var
        i,j     :longint;
begin
        readln(fi,n);
        for i:=1 to n do
                for j:=1 to n do
                        read(fi,a[i,j]);
end;
 
Procedure Init;
var
        i,j     :longint;
begin
        for i:=0 to n do
                begin
                        s[0,i]:=0;
                        s[i,0]:=0;
                end;
        for i:=1 to n do
                for j:=1 to n do
                        s[i,j]:=s[i-1,j]+s[i,j-1]+a[i,j]-s[i-1,j-1];
        for i:=1 to n do
                begin
                        if s[i,1] mod 2=0 then L[i,1]:=true
                                else L[i,1]:=false;
                        if s[1,i] mod 2=0 then L[1,i]:=true
                                else L[1,i]:=false;
                end;
end;
 
Procedure solution;
var
        i,j     :longint;
        x,y     :boolean;
        h,c     :qword;
begin
        for i:=2 to n do
                for j:=2 to n do
                        begin
                                h:=s[i,j]-s[i-1,j];
                                c:=s[i,j]-s[i,j-1];
                                if (h mod 2=0) and (L[i-1,j]=false) then x:=true
                                        else x:=false;
                                if (c mod 2=0) and (L[i,j-1]=false) then y:=true
                                        else y:=false;
                                L[i,j]:=x or y;
                        end;
end;
 
Procedure xuat;
begin
        if L[n,n]=true then writeln(fo,'YES')
                else writeln(fo,'NO');
end;
 
Procedure Process;
var
        i       :longint;
begin
        assign(fi,tfi);
        reset(fi);
        assign(fo,tfo);
        rewrite(fo);
        readln(fi,k);
        for i:=1 to k do
                begin
                        nhap;
                        Init;
                        solution;
                        xuat;
                end;
        close(fi);
        close(fo);
end;
 
begin
        Process;
end.

MMOD29 – SPOJ

Đề bài: http://vn.spoj.com/problems/MMOD29/

Thuật toán:

  • (đang cập nhập)

Code:

const   fi      ='';
        fo      ='';
 
var     f1, f2       :text;
        x       :longint;
        a, b, c :longint;
function get(a, b:longint):longint;
var     tmp     :longint;
begin
        if b = 0 then exit(1);
        if b mod 2 = 0 then exit(sqr(get(a, b div 2)) mod 29 )
        else exit( (sqr(get(a, b div 2))*a) mod 29 );
end;
 
BEGIN
        assign(f1, fi);
        reset(f1);
        assign(f2, fo);
        rewrite(f2);
        while not eof(f1) do
                begin
                        readln(f1, x);
                        if x = 0 then break;
                        a:=(get(2, 2*x + 1) - 1 ) mod 29;
                        b:=(get(3,   x + 1) - 1 ) mod 29;
                        c:=(get(167, x + 1) - 1 ) mod 29;
                        writeln(f2,(a*b*c*9) mod 29);
                end;
        close(f1);
        close(f2);
END.

PTRANG – SPOJ

Đề bài: http://vn.spoj.com/problems/PTRANG/

Thuật toán:

Đây là một bài DP không mấy phức tạp chỉ cần suy nghĩ chút thôi là bạn có thể giải được.

Gọi L[i] là hệ số phạt nhỏ nhất khi phân trang các từ từ 1 đến i.

Gọi S[i] = w[1] + w[2] + … + w[i]

Cộng thức quy hoạch động các bạn có thể xem code phía dưới để hiểu rõ.

Code:

Const
        fi='';
        fo='';
        maxn=6000;
 
Type
        arr1    =array[0..maxn] of longint;
 
Var
        n,le    :longint;
        w       :arr1;
        s       :arr1;
        l       :arr1;
        f       :text;
 
Procedure Nhap;
var
        i       :longint;
begin
        s[0]:=0;
        assign(f,fi);
        reset(f);
        readln(f,n,le);
        for i:=1 to n do
                begin
                        readln(f,w[i]);
                        s[i]:=w[i]+s[i-1];
                end;
        close(f);
end;
 
function max(a,b:longint):longint;
begin
        if a>b then exit(a);
        exit(b);
end;
 
Procedure solution;
var
        i,j     :longint;
        k       :longint;
        u       :longint;
begin
        l[0]:=0;
        w[0]:=0;
        for i:=1 to n do
                begin
                        l[i]:=maxlongint;
                        for j:=i downto 1 do
                                if s[i]-s[j-1]<=le then
                                        begin
                                                k:=le-(s[i]-s[j-1]);
                                                u:=Max(L[j-1],k);
                                                if l[i]>u then l[i]:=u;
                                        end
                                else break;{neu s[j]+s[j+1]+..+s[i]>le thi khong tim nua}
                end;
end;
 
Procedure xuat;
begin
        assign(f,fo);
        rewrite(f);
        write(f,l[n]);
        close(f);
end;
 
begin
        nhap;
        solution;
        xuat;
end.

FP – SPOJ

Đề bài: http://vn.spoj.com/problems/FP/

Thuật toán:

  • Bài này sử dụng phương pháp quy hoạch động. Các bạn có thể đọc code bên dưới để hiểu rõ hơn.

Code:

uses math;
const
  fi='';
  fo='';
  maxn=100;
  oo=trunc(1e9);
  base=9;
var
  f : array[0..maxn,0..maxn,0..10] of string;
  a : array[1..maxn] of string;
  s : array[1..maxn] of longint;
  i,j,n,t,tt,k : longint;
procedure enter;
  begin
    readln(n,k);
    for i:=1 to n do readln(a[i]);
  end;
procedure swap(var x,y : string);
  var tg : string;
  begin
    tg:=x;x:=y;y:=tg
  end;
procedure sort;
  begin
    for i:=1 to n do
      for j:=i+1 to n do
        if a[i]+a[j]<a[j]+a[i] then
          begin
            swap(a[i],a[j]);
          end;
  end;
function tinh(x : string) : longint;
  var i,j : longint;
  begin
    j:= 0;
    for i:=1 to length(x) do
      j := j + ord(x[i])-48;
    exit(j);
  end;
function calc(x,y : longint) : longint;
  var tg : longint;
  begin
    tg:=(x-y) mod 9;
    if tg<0 then tg:=tg+9;
    exit(tg);
  end;
function max2(x,y : string) : string;
  begin
    if length(x)>length(y) then exit(x);
    if lengtH(x)<length(y) then exit(y);
    if x>y then exit(x) else exit(y);
  end;
procedure process;
  var i,j,jj : longint;
  begin
    sort;
    for i:=1 to n do s[i] := tinh(a[i]);
    for i:=0 to n do
      for j:=0 to n do
        for jj:=0 to 10 do
          f[i,j,jj] := '-1';
    for i:=0 to n do f[i,0,0] := '';
    for i:=1 to n do
      for j:=1 to min(k,i) do
        for jj := 0 to 8 do
          begin
            if f[i-1,j,jj]<>'-1' then f[i,j,jj] := f[i-1,j,jj];
            if f[i-1,j-1,calc(jj,s[i])]<>'-1' then
              if f[i,j,jj]<>'-1' then f[i,j,jj] := max2(f[i,j,jj],f[i-1,j-1,calc(jj,s[i])]+a[i]) else f[i,j,jj] := f[i-1,j-1,calc(jj,s[i])]+a[i];
          end;
  end;
procedure print;
  begin
    if f[n,k,0]='' then writeln(-1) else
    writeln(f[n,k,0]);
  end;
begin
  assigN(input,fi);reset(input);
  assign(output,fo);rewrite(output);
  readln(t); k:=9;
  for tt:=1 to t do
  begin
    enter;
    process;
    print;
  end;
end.