Cho tam giác đều ABC, đỉnh A, cạnh dài N đơn vị. Tại các điểm chia
nguyên trên các cạnh ta kẻ các đường thẳng song song chia tam giác thành N2
tam giác đơn vị (TGĐV). Mã số cho các TGĐV theo trật tự từ trên xuống và từ
trái qua phải là 1, 2, …, N2. Ba bạn A, B và C được cấp mỗi bạn một
TGĐV khác nhau làm nơi xuất phát trên các cạnh AB cho bạn A, BC cho bạn B và AC
cho bạn C. Lần lượt theo thứ tự quay
 |
vòng A, B, C viết chữ cái tên mình vào các TGĐV kề cạnh với các tam
giác mà mình đã viết ở lần trước. Biết các giá trị N, và các điểm xuất phát NA,
NB và NC, tính số chữ cái mỗi loại mỗi bạn đã viết.
Tổ chức dữ liệu
Các biến dùng chung:
var n: longint; { Do dai canh tam giac }
f,g: text; { input, output file }
AN, BN, CN: longint; { O xuat phat }
Ad, Av, Bd, Bv, Cd, Cv: longint; { Toa do xuat phat }
Ak,Bk,Ck: longint;
A,B,C: longint; { con dem }
Kq: array [‘A’..’C’] of longint;
trong đó n là chiều dài một cạnh của tam giác đều; AN, BN và
CN là số hiệu của các ô xuất phát tương ứng cho A, B và C.
Thuật toán
Xét các tam giác đơn vị từ đỉnh xuống đến cạnh đáy của bàn
cờ. Ta thấy, trên dòng 1 có 1 TGĐV, dòng 2 có 3, dòng 3 có 5 TGĐV... Tổng quát,
trên dòng i tính từ đỉnh xuống đến đáy sẽ có 2*i -1 TGĐV. Trên mỗi dòng i ta
gán số hiệu cho các TGĐV là 1, 2, ... , 2i-1.
Ta định nghĩa tọa độ của một tam giác đơn vị có số hiệu (tuyệt đối theo
đầu bài) cell là cặp số (d,v) trong đó d là số hiệu dòng chứa TGĐV đó và v là
số hiệu của tam giác đó trên dòng d. Thủ
tục ToaDo
dưới đây tính tọa độ cho một TGĐV theo cell - số hiệu (tuyệt đối) của TGĐV như
cách mã số của đề bài. Thủ tục cho ra hai giá trị, dong - dòng chứa TGĐV cell và viTri - số hiệu của TGĐV trên dòng đó mà ta gọi là số
hiệu tương đối. Thí dụ, ToaDo(15,d,v) cho ta d = 4, v = 6.
procedure ToaDo(cell: longint;var dong, viTri:longint);
begin
dong := 0;
while cell > 0 do
begin
dong := dong + 1;
cell := cell -
(2*dong-1);
end;
viTri := cell +
(2*dong-1);
end;
Hàm KhoangCach dưới đây tính khoảng
cách giữa hai TGĐV theo tọa độ (d1,v1) và (d2,v2), trong đó d1, d2 là số hiệu
dòng, v1 và v2 là số hiệu tương đối của
chúng (trên dòng). Giống như bài trước, khoảng cách trong bài này chính là số
TGĐV ít nhất, kề cạnh nhau trên đường đi từ TGĐV (d1,v1) đến TGĐV (d2,v2). Trước hết ta đổi chỗ hai tọa độ, nếu cần, sao
cho tam giác thứ nhất luôn luôn nằm ở dòng trên so với tam giác thứ hai, tức
là d1 £ d2. Sau đó ta nhận xét
như sau:
Nếu một TGĐV có đỉnh quay lên trên thì
* Số hiệu tương đối của nó là số lẻ, và
* Nó sẽ là đỉnh của một tam giác đều chứa nó và có các cạnh song
song với các cạnh của bàn cờ.
Nếu một TGĐV có đỉnh quay xuống dưới thì
* Số hiệu tương đối của nó là số chẵn, và
* TGĐV kề cạnh với nó trên cùng dòng sẽ có đỉnh quay lên trên.
Ta gọi các TGĐV có đỉnh quay lên trên là tam giác lẻ để phân biệt với các TGĐV chẵn - có đỉnh quay xuống dưới.
Nếu TGĐV thứ nhất (d1,v1) là tam giác lẻ ta xét tam giác lớn
hơn tạo bởi các TGĐV nhận tam giác lẻ này làm đỉnh và có cạnh đáy trên dòng d2.
Ta tính hai đỉnh trên đáy của tam giác này trên dòng d2 là C1 và C2 theo công
thức
d := 2*(d2 - d1);
c1 := v1;
c2 := v1 + d;
Tiếp đến ta xét vị trí v2 trên cạnh đáy có thể nằm giữa C1
và C2 hoặc nằm ngoài đoan [C1, C2] đồng thời xét v2 là tam giác chẵn hay lẻ.
function KCLe(d1,v1,d2,v2: longint):longint;
var c1,c2,d: longint;
begin
{ v1 <= v2 }
d := 2*(d2 - d1);
c1 := v1;
c2 := v1 + d;
if (c1 <= v2) and (v2
<= c2) then
begin
if odd(v2) then KCLe
:= d
else KCLe := d - 1;
exit;
end;
KCLe := d +
Min(abs(v2-c1),abs(v2-c2));
end;
Nếu TGĐV thứ nhất (d1,v1) là tam giác chẵn thì ta lùi lại
một dòng dể xét TGĐV lẻ có chung đáy với TGDV thứ nhất rồi tính toán như trên
và giảm kết quả 1 đơn vị.
function KhoangCach(d1,v1,d2,v2: longint):longint;
var t: longint;
begin
if d1 > d2 then
begin
t := v1; v1 := v2; v2 := t;
t := d1; d1 := d2; d2 := t;
end;
{ v1 <= v2 }
if odd(v1) then KhoangCach :=
KCLe(d1,v1,d2,v2)
else KhoangCach :=
KCLe(d1-1,v1-1,d2,v2) - 1;
end;
procedure XuLi;
var d,v,j: longint;
Ad, Av, Bd, Bv, Cd,
Cv: longint;
begin
fillchar(kq,sizeof(kq),0);
ToaDo(NA, Ad, Av);
ToaDo(NB, Bd, Bv);
ToaDo(NC, Cd, Cv);
for d := 1 to N do
for v := 1 to 2*d - 1
do
inc(kq[Min3(KhoangCach(Ad,Av,d,v),
KhoangCach(Bd,Bv,d,v),
KhoangCach(Cd,Cv,d,v))]);
end;
Độ phức tạp
Ta phải duyệt mọi TGĐV trên bàn cờ, vậy độ phức tạp tính
toán cỡ N2.
Nguồn:
SÁNG TẠO
TRONG THUẬT TOÁN
VÀ
LẬP TRÌNH
Không có nhận xét nào:
Đăng nhận xét