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, đỏ, tím và vàng, bao gồm x đoạn màu xanh mỗi đoạn dài dx, d đoạn màu đỏ mỗi đoạn dài dd, t đoạn màu tím mỗi đoạn dài dt và v đoạn màu vàng mỗi đoạn dài dv. Các đoạn thẳng cùng màu thì có cùng chiều dài. Hãy chọn mỗi loại một số đ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 tính theo chiều quay của kim đồng hồ là xanh, đỏ, tím, vàng. Các đại lượng trong bài đều là các số nguyên dương.

XDTV1.INP
XDTV1.OUT




15 12
6 21
14 15
10 28

15120
15 4 12 3




xanh



v
à
n
g







đ














tím





















Dữ liệu vào: tệp văn bản XDTV1.INP gồm 4 dòng, mỗi dòng hai số nguyên dương viết cách nhau
Dòng thứ nhất: x    dx
Dòng thứ hai:  d    dd
Dòng thứ ba:   t    dt
Dòng thứ tư:   v    dv
Dữ liệu ra: tệp văn bản XDTV1.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.
Kết quả trên cho biết cần chọn 15 đoạn xanh, 4 đoạn đỏ, 12 đoạn tím và 3 đoạn vàng để ghép thành hình chữ nhật xanh – đỏ -tím -vàng với diện tích max là 15120 = (15*12)*(4*21) = (12*15)*(3*28).

Thuật toán

Phương pháp: Tham.
                Ta gọi một bộ xanh - tím là một cặp (nx,nt) trong đó nx là số ít nhất các đoạn màu xanh đặt liên tiếp nhau trên đường thẳng tạo thành đoạn AB và nt là số ít nhất các đoạn màu tím đặt liên tiếp nhau trên đường thẳng tạo thành đoạn CD sao cho AB = CD. Ta có ngay nx*dx = nt*dt. Dễ dàng tìm được nx = Bcnn(dx,dt)/dx và nt = Bcnn(dx,dt)/dt, trong đó Bcnn(a,b) là hàm tính bội chung nhỏ nhất của hai số tự nhiên a và b. Tương tự ta tính cho bộ đỏ - vàng.  Tiếp đến ta tính xem tối đa có thể lấy được bao nhiêu bộ xanh - tím và bộ đỏ - vàng. Dễ thấy Số bộ xanh - tím = min(x div nx, t div nt).  Tương tự ta tính cho bộ đỏ - vàng. 
            Độ phức tạp: O(1).                                         
(*  Pascal  *)
(******************************************
             Xanh Do Tim Vang 1
******************************************)
program xdtv1;
uses crt;
const
 fn = 'xdtv1.inp'; gn = 'xdtv1.out'; bl = #32;
var
 n: longint;
 f,g: text;
 x,d,t,v: longint; { so doan X D T V }
 dx,dd,dt,dv: longint; { cheu dai moi doan }
 nx,nt,nd,nv: longint; { so doan X D T V can chon }
procedure Doc;
begin
 assign(f,fn); reset(f);
 readln(f,x,dx); readln(f,d,dd); readln(f,t,dt); readln(f,v,dv);
 close(f);
end;
function Ucln(a,b: longint): longint;
  var r: longint;
begin
 while (b <> 0) do
   begin r := a mod b; a := b; b := r; end;
 Ucln := a;
end;
(*------------------------------------
      Bcnn(a,b) = (a * b)/Ucln(a,b)
-------------------------------------*)
function Bcnn(a,b: longint): longint;
begin Bcnn := a * (b div Ucln(a,b)); end;
function Min(a,b: longint): longint; tự viết
procedure XuLi;
 var b, nxt, ndv: longint;
begin
 b := Bcnn(dx,dt);
 nx := b div dx; { so doan xanh trong 1 bo xanh – tim }
 nt := b div dt; { so doan tim trong 1 bo xanh – tim }
 nxt := Min(x div nx, t div nt); { so bo xanh – tim }
 nx := nxt * nx; { so doan xanh can chon }
 nt := nxt * nt; { so doan tim can chon }
 b := Bcnn(dd,dv);
 nd := b div dd; { so doan do trong 1 bo do – vang }
 nv := b div dv; { so doan vang trong 1 bo do – vang }
 ndv := Min(d div nd, v div nv);{ so bo do vang }
 nd := ndv * nd; { so doan do can chon }
 nv := ndv * nv; { so doan vang can chon }
end;
procedure Ghi;
begin
  assign(g,gn);  rewrite(g);
  writeln(g,nx*dx*nd*dd);{ dien tich }
  writeln(g,nx,bl,nd,bl,nt,bl,nv); { so doan moi loai }
  close(g);
end;
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