2016 June

QBMARKET – SPOJ

June 15, 2016 by Aida Nana Leave a Comment

Đề 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..m_i). 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 m_i 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=j₁ ta tính L[j₁+x], j tăng lên j₁+x ta tính L[j₁+x+y] ta có

L[j₁+x+y]=L[j₁+x+y]+L[j₁+x] mà khi đó L[j₁+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[j₁+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.

Chủ đề: Quy hoạch động, SPOJ Mức độ: QHĐ

LINEGAME – SPOJ

June 15, 2016 by Aida Nana Leave a Comment

Đề 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(n²), 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 10⁶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=10⁶ 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 m1max 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.

Chủ đề: Quy hoạch động Mức độ: QHĐ

PARIGAME – SPOJ

June 15, 2016 by Aida Nana Leave a Comment

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

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(n²) tốt hơn rất nhiều nếu tính trực tiếp sẽ có độ phức tạp O(n³)

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.

Chủ đề: Quy hoạch động Mức độ: hsgqg, normal

MMOD29 – SPOJ

June 15, 2016 by Aida Nana 2 Comments

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

Chủ đề: SPOJ

PTRANG – SPOJ

June 14, 2016 by Aida Nana Leave a Comment

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

Chủ đề: Quy hoạch động

FP – SPOJ

June 14, 2016 by Aida Nana Leave a Comment

Đề 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]length(y) then exit(x);
    if lengtH(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.

Chủ đề: Quy hoạch động Mức độ: QHĐ

WEATHER – SPOJ

June 12, 2016 by Aida Nana Leave a Comment

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

Thuật toán:

Bài này sử dụng thuật toán duyệt đồ thị DFS. Bạn có thể đọc code để hiểu rõ hơn.

Code:

{$inline on}
var
               n, m        :     longint;
               a           :     array[0..100, 0..100] of boolean;
               trace       :     array[0..100] of boolean;
               count       :     longint;

procedure      enter;
   var i, j, u, v: longint;
   begin
      readln(n);
      for i:= 1 to n do
         for j:= 1 to n do a[i, j]:= false;
      readln(m);

      for i:= 1 to m do
         begin
            readln(u, v);
            a[u, v]:= true;
            a[v, u]:= true;
         end;
   end;

procedure      dfs(u: longint);
   var i: longint;
   begin
      inc(count);
      trace[u]:= true;

      for i:= 1 to n do
         if a[u, i] and (not trace[i]) then dfs(i);
   end;

procedure      solve;
   var i, j, res, k: longint;
   begin
      res:= 0;

      for i:= 1 to n do
         for j:= i + 1 to n do
            if a[i, j] then
               begin
                  a[i, j]:= false;
                  a[j, i]:= false;

                  for k:= 1 to n do trace[k]:= false;
                  count:= 0;
                  dfs(1);

                  res:= res + count*(n - count);

                  a[i, j]:= true;
                  a[j, i]:= true;
               end;
      writeln(res);
   end;

begin
   enter;
   solve;
end.

Chủ đề: DFS Mức độ: do thi

REFORM – SPOJ

BESTSPOT – SPOJ

V8SCORE – SPOJ

QBMARKET – SPOJ

LINEGAME – SPOJ

PARIGAME – SPOJ

MMOD29 – SPOJ

PTRANG – SPOJ

FP – SPOJ

WEATHER – SPOJ

Recent Posts

Recent Comments

Archives

Categories

Meta