Vua Tên Miền chuyên cung cấp tên miền đẹp, giá rẻ! Hãy liên hệ kỹ thuật: 0914205579 - Kinh doanh: 0912191357 để được tư vấn, hướng dẫn miễn phí, Cảm ơn quý khách đã ủng hộ trong thời gian qua!
kinh doanh, bán hàng, tư vấn, bảo hiểm Những cá nhân, tổ chức, đại lý,muốn bán, hợp đồng bảo hiểm
Monday, December 16, 2013



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
LẬP TRÌNH


0 comments:

Post a Comment

domain, domain name, premium domain name for sales

Popular Posts