Xanh đỏ tím vàng 1

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

VÀ

LẬP TRÌNH