Cờ tam tài

Olimpic quốc tế

A
					C
	B
Cờ tam tài 4 ´ 6 N = 2

Một số quốc gia như Ba Lan, Bỉ, Pháp… có quốc kỳ tạo từ ba giải màu thường được gọi là cờ tam tài. Ba bạn trẻ A, B và C chơi trò ghép hình để tạo thành một lá cờ tam tài với ba giải màu dọc lần lượt tính từ trái qua phải là xanh (X), trắng (T) và đỏ (D).  Mặt bàn để ghép cờ có kích thước 2N ´ 3N ô vuông đơn vị được kẻ sẵn thành lưới ô vuông với mã số các hàng tính từ trên xuống dưới là 1, 2,…, 2N và mã số các cột tính từ trái qua phải là 1, 2,…, 3N. Đầu tiên bạn A chọn một ô trên cột 1 có tọa độ là (Ax, Ay = 1), bạn B chọn một ô trên dòng cuối cùng có tọa độ là (Bx=2N, By), bạn C chọn một ô trên cột cuối cùng có tọa độ là (Cx, Cy = 3N). Sau đó lần lượt theo thứ tự quay vòng A, B, C ba bạn chọn các mảnh ghép đơn vị 1´ 1 với màu phù hợp để đặt vào các ô trong bàn cờ. Lần đầu tiên mỗi bạn đặt một mảnh ghép vào ô đã chọn. Những lần tiếp theo, đến lượt mình,  mỗi bạn đặt một số mảnh ghép kề với mảnh ghép do chính bạn ấy đã đặt tại lần trước. Dĩ nhiên, mỗi ô trên bàn chỉ được đặt đúng 1 mảnh ghép. Bạn nào không thể ghép được thì bạn đó ngừng chơi, những người còn lại sẽ tiếp tục chơi đến khi hoàn thành lá cờ. Biết các giá trị N, Ax, By và Cx. Hãy cho biết mỗi bạn đã ghép được bao nhiêu mảnh mỗi màu.

Với thí dụ như trong hình, N = 2, Ax = 2, By = 2, Cx  = 3 ta tính được kết quả như trong bảng. Ý nghĩa của các ô trên bàn ghép cờ cho biết bạn nào trong lần đi thứ mấy của mình, ghép mảnh màu gì. Thí dụ, A5:T cho biết bạn A, trong lần đi thứ 5 ghép mảnh màu trắng. Ô xuất phát của mỗi bạn kí hiệu là 0.

Œ



Ž





‘



A1:X

A2:X

A3:T

A4:T

C3:D

C2:D

Xanh

Trắng

Đỏ

‚

A0:X

A1:X

A2:T

A3:T

C2:D

C1:D

A

5

4

0

ƒ

A1:X

B1:X

B2:T

C2:T

C1:D

C0:D

B

3

3

0

„

B1:X

B0:X

B1:T

B2:T

C2:D

C1:D

C

0

1

8

Cờ tam tài, N = 2, A(2,1), B(4,2), C(3,6) X: Xanh, T: Trắng, D: Đỏ.

Kết quả

Thuật toán

Bài này khá dễ giải. Nếu bạn khéo tổ chức dữ liệu thì chương trình sẽ rất gọn. Trước hết ta cần xác định rằng mỗi ô (i,j) trên bàn cờ sẽ  do bạn nào ghép: A, B hay C ? Ta định nghĩa khoảng cách giữa hai ô (i,j) và (x,y) trên bàn cờ là số ô ít nhất nằm trên đường đi từ ô này đến ô kia qua các ô kề cạnh nhau. Khoảng cách này chính là tổng chiều dài hai cạnh kề nhau của hình chữ nhật nhận hai ô đã cho làm hai đỉnh đối diện, do đó được tính theo công thức

d  = abs(i-x) + abs(j-y) +1

 Giá trị d có ý nghĩa gì ? Nếu ta qui định đánh số các lần đi cho mỗi đấu thủ là 0, 1, 2, … thì d-1 cho biết lần đi thứ mấy của mỗi bạn. Vì trật tự tính lần đi của các bạn là A à B à C nên ta cần xác định giá trị min trong ba khảng cách d_A, d_B và d_C. Tuy nhiên chúng ta sẽ khôn ngoan một chút, cụ thể là ta sẽ tính d theo công thức hụt 1

d  = abs(i-x) + abs(j-y)

và viết hàm min3 nhận vào là ba giá trị d_A, d_B và d_C và cho ra là tên của người được ghép mảnh tại ô đang xét.

function Min3(a,b,c: integer): char;

  var k: char;

begin

  k := 'A';

  if a > b then begin k := 'B'; a := b end;

  if a > c then k := 'C';

  Min3 := k;

end;

Sau khi xác định được chủ của mảnh ghép tại ô (i,j) ta dễ dàng tính được màu của mảnh ghép tại ô đó. Vì lá cờ có ba màu và ta tạm qui ước các giải màu tính từ trái qua phải là 0, 1 và 2 nên màu cần chọn để đặt tại ô (i,j) khi đó sẽ là (j-1) div N.

Ta khai báo mảng kq dùng để tích lũy kết quả như sau:

kq: array['A'..'C',0..2] of integer;

Khi đó c[v,i] sẽ cho biết bạn v đã ghép bao nhiêu quân màu i, v = 'A', 'B', 'C'; i = 0 (màu Xanh), 1 (màu Trắng), 2 (màu Đỏ).

Các biến chung của chương trình sẽ là:  

var

n: integer; { Ban co co kich thuoc 2n´3n }

Ax,Ay,Bx,By,Cx,Cy: integer; { Toa do xuat phat cua A, B, C }

kq: array['A'..'C',0..2] of integer; { Chua ket qua }

Thủ tục XuLi sẽ duyệt lần lượt mỗi ô (i , j) trên bàn cờ, xác định chủ nhân của ô này và số màu của mảnh cần ghép để tích lũy cho chủ nhân đó.

procedure XuLi;

 var i,j: integer;

begin

fillchar(kq,sizeof(kq),0);

for I := 1 to 2*N do

 for j := 1 to 3*N do

  inc(c[Min3(abs(i-Ax)+abs(j-Ay),abs(i-Bx)+abs(j-By),

              abs(i-Cx)+abs(j-Cy)),(j-1) div N]);

end;

Độ phức tạp

Ta phải duyệt mọi ô trên bàn cờ vậy độ phức tạp tính toán cỡ N².

Bài sau đây tương tự như bài trên nhưng khó hơn về các thủ tục mã hóa.

 

Nguồn:

SÁNG TẠO

TRONG THUẬT TOÁN

VÀ

LẬP TRÌNH