Xanh đỏ tím vàng 2

Cho 4 loại đoạn thẳng sơn các màu xanh dài dx, đỏ dài dd, tím dài dt và vàng dài dv. Các đoạn thẳng cùng màu thì có cùng chiều dài và số lượng không hạn chế. Hãy chọn ra không quá N đoạn thẳng rồi  xếp nối nhau theo chu vi để thu được một hình chữ nhật có diện tích lớn nhất với các cạnh lần lượt mang các màu theo chiều quay của kim đồng hồ là xanh, đỏ, tím, vàng. Dữ liệu trong bài đều là các số nguyên dương.

XDTV2.INP	XDTV2.OUT	Dữ liệu vào: tệp văn bản XDTV2.INP Dòng thứ nhất: số N > 0. Dòng thứ hai:  bốn số dx  dd  dt  dv Dữ liệu ra: tệp văn bản XDTV2.OUT Dòng đầu tiên: Diện tích của hình chữ nhật xanh - đỏ - tím - vàng. Dòng thứ hai: 4 số cho biết số lượng đoạn thẳng cần chọn theo mỗi loại màu để ghép được hình chữ nhật diện tích max.
35 3 2 2 5	480 8 10 12 4

Kết quả trên cho biết cần chọn 8 đoạn xanh, 10 đoạn đỏ, 12 đoạn tím và 4 đoạn vàng để ghép thành hình chữ nhật có diện tích max là 480.

Thuật toán

Phương pháp: Tham.

Tương tự như bài Xanh đỏ tím vàng 1, trước hết ta tính các bộ xanh - tím (nx,nt) và bộ đỏ - vàng (nd, nv). Tiếp đến ta tính xem khi lấy i bộ xanh – tím để kết hợp với j bộ đỏ - vàng thì thu được hình chữ nhật có diện tích max là bao nhiêu. Lưu ý rằng i bộ xanh - tím sẽ gồm i(nx+nt) đoạn thẳng. Số đoạn thẳng còn lại khi đó sẽ là N – i(nx+nt). Số này sẽ tạo ra được j = (N – i(nx+nt)) / (nd+nv)  bộ đỏ - vàng.

            Độ phức tạp: O(n).

(*  Pascal  *)

(******************************************

             Xanh Do Tim Vang 2

******************************************)

program xdtv2;

uses crt;

const

 fn = 'xdtv2.inp';  gn = 'xdtv2.out';  bl = #32;

var

 n: longint;

 f,g: text;

 x,d,t,v: longint;

 dx,dd,dt,dv: longint;

 nx,nt,nd,nv: longint;

 smax,bmax: longint;

procedure Doc: Tự viết;

function Ucln(a,b: longint): Tự viết;

function Bcnn(a,b: longint): Tự viết;

function Min(a,b: longint): Tự viết;

(*---------------------------------------------------------

  1 bo xanh - tim = (sx,st) = (so doan xanh, so doan tim)

  sx = bcnn(dx,dt) div dx

  st = bcnn(dx,dt) div dt

  bxt = sx + st

  --------------------------------------------------------*)

procedure XuLi;

 var b: longint;

     bxt, bdv: longint;

     s: longint;

     sx,st, sd, sv: longint;

begin

 b := bcnn(dx,dt);

 sx := b div dx;

 st := b div dt;

 bxt := sx + st;

 b := Bcnn(dd,dv);

 sd := b div dd;

 sv := b div dv;

 bdv := sd + sv;

 smax := 0; bmax := 0;

 for b := 1 to ((n - bdv) div bxt) do

   begin

     s := (b*sx*dx)*(((n – b*bxt) div bdv)*sd*dd);

     if (s > smax) then

       begin  bmax := b; smax := s;  end;

    end;

  nx := bmax * sx; nt := bmax * st;

  b  := smax div (nx*dx); { Chieu dai canh Do ( = Vang) }

  nd := b div dd; nv := b div dv;

end;

procedure Ghi: Tự viết;

BEGIN

 Doc; XuLi; Ghi;

END.

Nguồn:

SÁNG TẠO

TRONG THUẬT TOÁN

VÀ

LẬP TRÌNH