Xanh đỏ

Cho x đoạn thẳng màu xanh có chiều dài bằng nhau là dx đơn vị và d đoạn màu đỏ có chiều dài bằng nhau là dd đơn vị. Hãy chọn nx đoạn xanh và nd đoạn đỏ đặt trên chu vi của hình chữ nhật tạo thành một đường viền đan màu (các màu xen kẽ nhau) và diện tích của hình là lớn nhất.

Input: Bốn số x, dx, d  và dd, x ³ 2, d ³ 2.

Output: Hiển thị trên màn hình

- nx: Số đoạn xanh được chọn,

- nd: Số đoạn đỏ được chọn,

- s: Diện tích max.

* Thí dụ 1 input: (x, dx, d, dd) = (5, 2, 7, 2) output: (nx, nd,  s) = (5, 5, 24) * Thí dụ 2 input: (x, dx, d, dd) = (6, 2, 7, 3) output: (nx, nd,  s) = (6, 6, 56) * Thí dụ 3 input: (x, dx, d, dd) = (6, 2, 7, 2) output: (nx, nd, s) = (6, 6, 36) * Thí dụ 4 input: (x, dx, d, dd) = (7, 2, 7, 3) output: (nx, nd, s) = (6, 6, 56)

Hình chữ nhật có cạnh đan màu xanh - đỏ và đạt diện tích max

x = 11, dx = 1,   d = 10, dd = 2.   nx = 10, nd = 10, s = 7 ´ 8 =  56.

Thuật toán

Dễ thấy là để thu được hình có đường viền đan màu thì cần chọn số đoạn xanh nx và số đoạn đỏ nd như nhau, tức là chọn nx = nd = min(x, d). Khi đó chu vi của hình sẽ gồm t = nx + nd = 2nx = 2nd đoạn, và do đó t là một số chẵn. Do t chẵn nên (t mod 4) sẽ bằng 0 hoặc 2.

Kí hiệu a là số đoạn (tính cả xanh và đỏ) cần đặt trên một chiều rộng, b là số đoạn (tính cả xanh và đỏ) cần đặt  trên một chiều dài của hình. Xét hai trường hợp dx = dd và dx ≠ dd.

1. Trường hợp thứ nhất: dx = dd.  Ta có, a  = b = t div 4. Nếu (t mod 4 = 2). Ta thêm vào chu vi một cặp xanh đỏ nữa. Vậy ta cần chọn:

- nx = min(x,d) đoạn xanh,

- nd = nx đoạn đỏ,

- Diện tích max: s = a * b * dx * dx với

   a = t div 4  là số đoạn đặt trên 1 chiều rộng,

   b = a + ((t mod 4) div 2) là số đoạn đặt trên 1 chiều dài.

2. Trường hợp thứ hai: dx ≠ dd.  Ta thấy, để đảm bảo tính đan màu thì a và b phải có cùng tính chẵn lẻ. Từ đó thấy rằng khi (t mod 4 = 2) ta phải bỏ qua số dư, vì nếu thêm cho chiều dài b 1 đoạn nữa thì tính chẵn lẻ của a và b sẽ khác nhau. Để ý rằng khi a và b cùng chẵn thì hình nhận được sẽ vuông và mỗi cạnh chứa đúng z = a div 2 đoạn xanh và z đoạn đỏ. Khi đó diện tích có thể tính theo công thức: s = sqr(z * (dx + dd)). Nếu a và b cùng lẻ thì số lượng đoạn xanh và số lượng đoạn đỏ trong một cạnh sẽ hơn kém nhau 1 đơn vị. Nếu cạnh này nhiều xanh hơn đỏ thì cạnh kề với cạnh đó sẽ nhiều đỏ hơn xanh. Khi đó diện tích sẽ được tính theo công thức

s = (z * dx + (z+1) *dd) * (z * dd + (z+1) * dx)  = (z * dx + z * dd + dd) * (z * dd + z * dx + dx)

   = (z * (dx + dd) + dd) * (z * (dx + dd) + dx)  = (k + dd) * (k + dx)

với z = a div 2,  k = (a div 2)*(dx + dd).

Kết quả là cần chọn:

nx = min(x,d). Chu vi 2*nx phải là bội của 4, tức là nx phải chẵn. Nếu nx  lẻ thì  đặt lại nx := nx - 1.

nd = nx;

 tổng cộng  t = nx + nd đoạn, trong đó

                   Số đoạn đặt trên 1 chiều rộng: a = t div 4,

                   Số đoạn đặt trên 1 chiều dài: b = a,

-      Diện tích max: (k+dd) * (k+dx), k = (a div 2)*(dx+dd).

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

(* Pascal *)

  program XanhDo;

  uses crt;

  const bl = #32;

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

  procedure XD(x,dx,d,dd: longint);

   var a,b,nx,nd,k,t,s: longint;

  begin

    if (dx = dd) then

      begin

        nx := Min(x,d); nd := nx; t := nx + nd;

        a := t div 4;

        b := a + ((t mod 4) div 2); s := a * b * dx * dx

      end

     else { dx <> dd }

      begin

        nx := Min(x,d);

        if (nx mod 2 > 0) then nx := nx - 1;

        nd := nx; t := nx + nd; a := t div 4; b := a;

        k := (a div 2) * (dx + dd);

        if (Odd(a)) then s := (k + dx) * (k + dd)

        else s = k*k;

      end;

     writeln(nx,bl,nd,bl,s);

  end;

  BEGIN

   XD(7, 2, 7, 3);

  END.

Nguồn:

SÁNG TẠO

TRONG THUẬT TOÁN

VÀ

LẬP TRÌNH