MỤC LỤC
A.
Phần mở đầu 1
I.
Lý do chọn đề tài
II.
Mục đích của đề tài 1
III.
Nhiệm vụ và phương pháp nghiên cứu
1
VI.
Điểm mới trong kết quả nghiên cứu
1
B.
Nội dung
2
I.
Khái niệm
2
II.
Các thao tác thường dùng đối với Heap Max
2
1.
Khai báo................................................................................................................. 2
2.
UpHeap..................................................................................................................3
3.
DownHeap.............................................................................................................3
4.
Push........................................................................................................................ 5
5.
Pop......................................................................................................................... 5
6.
Dijkstra Heap.........................................................................................................5
III.
C.
1
Một số bài tập ứng dụng
7
1.
Bài tập 1: Thả xốp..................................................................................................7
2.
Bài tập 2: PILOT....................................................................................................9
3.
Bài tập 3: Tiểu thuyết trinh thám..........................................................................12
4.
Bài tập 4: BASE3.................................................................................................16
Phần kết luận20
0
A. PHẦN MỞ ĐẦU
I. LÝ DO CHỌN ĐỀ TÀI
Công tác bồi dưỡng học sinh giỏi (HSG) là một công tác mũi nhọn trong việc nâng
cao chất lượng giáo dục, tạo nguồn lực, bồi dưỡng nhân tài cho nhà trường nói riêng, cho
địa phương nói chung. Bồi dưỡng HSG là một công việc khó khăn và lâu dài, đòi hỏi
nhiều công sức của thầy và trò.
Trong quá trình bồi dưỡng HSG môn Tin học ở bậc THPT thì cấu trúc dữ liệu heap là
cấu trúc dữ liệu đặc biệt quan trọng. Từ lí do trên, tôi xin trình bày sáng kiến kinh nghiệm
“CHUYÊN ĐỀ BỒI DƯỠNG HSG : CẤU TRÚC DỮ LIỆU HEAP VÀ ỨNG DỤNG”,
để học sinh dễ dàng tiếp thu kiến thức mới.
Do lần đầu tiên thực hiện làm sáng kiến kinh nghiệm, nên không tránh khỏi những
thiếu sót. Mong quý thầy cô góp ý để lần sau làm tốt hơn.
II. MỤC ĐÍCH CỦA ĐỀ TÀI
Heap là một trong những cấu trúc dữ liệu đặc biệt quan trọng, nó giúp ta có thể giải
được nhiều bài toán trong thời gian cho phép. Độ phức tạp thông thường khi làm việc với
Heap là O(logN). Khi được học chuyên đề này học sinh sẽ lập trình thành thạo với các bài
toán ứng dụng của heap.
III. NHIỆM VỤ VÀ PHƯƠNG PHÁP NGHIÊN CỨU
Viết sáng kiến kinh nghiệm thường xuyên liên tục cũng là nhiệm vụ chính trị của mỗi
giáo viên, nhưng cần phải lựa chọn phương pháp nghiên cứu đúng đắn và phù hợp với nhà
trường trung học phổ thông. Sáng kiến kinh nghiệm đang trình bày của tôi dựa theo các
luận cứ khoa học hướng đối tượng, cụ thể: thuyết trình, quan sát, điều tra cơ bản, phân tích
kết quả thực nghiệm sư phạm,v.v… phù hợp với bài học và môn học thuộc lĩnh vực cấu
trúc dữ liệu.
IV. ĐIỂM MỚI TRONG KẾT QUẢ NGHIÊN CỨU
Giúp học sinh hiểu rõ về cấu trúc dữ liệu heap và sử dụng thành thạo trong lập trình.
Ngoài ra, tôi mạnh dạn trình bày sáng kiến kinh nghiệm này còn để phục vụ cho những
năm dạy tiếp theo.
1
B. PHẦN NỘI DUNG
Cấu trúc dữ liệu HEAP
I.
Khái niệm
Heap là một trong những cấu trúc dữ liệu đặc biệt quan trọng, nó giúp ta có thể giải
được nhiều bài toán trong thời gian cho phép. Độ phức tạp thông thường khi làm việc với
Heap là O(logN).
Heap thực chất là một cây cân bằng thỏa mãn các điều kiện sau:
Một nút có không quá 2 nút con.
Với Heap Max thì nút gốc là nút lớn nhất, mọi nút con đều không lớn hơn nút cha
của nó. Với Heap Min thì ngược lại.
Mặc dù được mô tả như cây nhưng Heap có thể được biểu diễn bằng mảng. Nút con
của nút i là 2*i và 2*i+1. Do Heap là cây cân bằng nên độ cao của 1 nút luôn <= logN.
Ứng dụng chủ yếu của Heap là tìm Min, Max trong 1 tập hợp động (có thể thay đổi,
thêm, bớt các phần tử) nhưng như vậy đã là quá đủ.
(Mô hình biểu diễn Heap bằng cây nhị phân và bằng mảng)
II.
Các thao tác thường dùng đối với Heap Max
1. Khai báo
Ở ví dụ này, Heap sẽ là mảng một chiều kiểu LongInt, nHeap là số phần tử của mảng.
2
Const
maxn = 100000;
Var
nHeap : LongInt;
Heap : array[0..maxn] of LongInt;
2. UpHeap
Nếu 1 nút lớn hơn nút cha của nó thì di chuyển nó lên trên:
Procedure UpHeap(i : LongInt);
Begin
if (i = 1) or (Heap[i] < Heap[i div 2]) then exit; // Nếu i là nút gốc hoặc
nhỏ hơn nút cha thì không làm việc
swap(Heap[i] , Heap[i div 2]); // Đổi chỗ 2 phần tử trong Heap;
UpHeap(i div 2); // Tiếp tục di chuyển lên trên
end;
3. DownHeap
Nếu 1 nút nhỏ hơn nút con thì đẩy nó xuống dưới:
3
Procedure DownHeap(i : LongInt);
Var
j : LongInt;
Begin
j := i*2;
if j > nHeap then exit; // Nếu i không có nút con thì không làm việc
if (j < nHeap) and (Heap[j] < Heap[j+1]) then Inc(j); // Nếu i có 2 nút con thì
chọn nút ưu tiên hơn
if Heap[i] < Heap[j] then // Nếu nút cha nhỏ hơn nút con
begin
swap(Heap[i] , Heap[j]); // Đổi chỗ 2 phần tử trong Heap
DownHeap(j); // Tiếp tục di chuyển xuống dưới
end;
end;
4
4. Push
Đưa 1 phần tử mới vào Heap: Thêm 1 nút vào cuối Heap và tiến hành UpHeap từ
đây:
Procedure Push(x : LongInt);
Begin
Inc(nHeap); // Tăng số phần tử của Heap
Heap[nHeap] := x; // Thêm x vào Heap
UpHeap(nHeap);
End;
5. Pop
Rút ra 1 phần tử ở vị trí v trong Heap: Gán Heap[v] := Heap[nHeap] rồi tiến hành
chỉnh lại Heap:
Function Pop(v : LongInt) : LongInt;
Begin
Pop := Heap[v]; // Lấy phần tử ở vị trí v ra khỏi Heap
Heap[v] := Heap[nHeap]; // Đưa phần tử ở cuối Heap vào vị trí v
Dec(nHeap); // Giảm số phần tử của Heap đi 1
{Chỉnh lại Heap}
UpHeap(v);
DownHeap(v);
End;
Ngoài ra, khi sử dụng thuật toán Dijkstra/Prim kết hợp cấu trúc Heap, bạn còn
có thể sử dụng cách Push và Pop khác thuận lợi hơn so với cách trình bày ở trên:
6. Dijkstra Heap
1/ Update – Dijkstra:
Procedure Update(v : LongInt); // Đỉnh v vừa được sửa nhãn, cần chỉnh lại Heap
var
child , parent : LongInt;
begin
child := pos[v]; // child là vị trí của đỉnh v trong Heap
if child = 0 then // Nếu đỉnh v chưa có trong Heap
5
begin
Inc(nHeap); // Tăng số phần tử của Heap
child := nHeap; // Đưa v vào cuối Heap
end;
parent := child div 2; // parent là nút cha của child
while (parent > 0) and (d[Heap[parent]] > d[v]) do // Nếu đỉnh ở nút parent
kém ưu tiên hơn v thì bị “kéo xuống” nút child
begin
Heap[child] := Heap[parent]; // Đẩy đỉnh được lưu trong nút cha xuống nút con
pos[Heap[child]] := child; // Ghi nhận lại vị trí mới của đỉnh đó
child := parent; // Tiếp tục di chuyển lên
parent := child div 2;
end;
Heap[child] := v; // Thao tác “kéo xuống” ở trên sẽ tạo ra 1 ô trống ở nút child để đặt v vào
pos[v] := child; // Ghi nhận vị trí mới của đỉnh v trong Heap
end;
2/ Pop – Dijkstra:
Function Pop : LongInt; // Lấy từ Heap đỉnh có nhãn tự do nhỏ nhất
var
r , v , c : LongInt;
begin
Pop := Heap[1]; // Nút gốc là nút có nhãn tự do nhỏ nhất
v := Heap[nHeap]; // v là đỉnh ở nút lá cuối Heap, sẽ được đảo lên đầu và vun đống
Dec(nHeap); // Giảm số phần tử của Heap
r := 1; // Bắt đầu từ nút gốc
while r*2 <= nHeap do // Chừng nào r chưa phải là lá
begin
c := r*2; // c là nút con của r
if (c < nHeap) and (d[Heap[c]] > d[Heap[c+1]]) then Inc(c); //
Trong 2 nút con chọn nút con chứa đỉnh ưu tiên hơn
if d[Heap[c]] >= d[v] then break; // Nếu v ưu tiên hơn thì không làm việc nữa
Heap[r] := Heap[c]; // Chuyển đỉnh lưu ở nút con lên nút cha
pos[Heap[r]] := r; // Cập nhật lại vị trí mới trong Heap của đỉnh đó
r := c; // Tiếp tục di chuyển xuống dưới
end;
Heap[r] := v; // Đỉnh v được đặt vào vị trí r để đảm bảo cấu trúc Heap
pos[v] := r; // Ghi nhận vị trí mới của đỉnh v trong Heap
end;
6
III.
Một số bài tập ứng dụng
1. Bài tập 1: Thả xốp
Có N hạt xốp, hạt thứ i có khối lượng
, được thả lần lượt xuống một ống nước đặc
biệt được thiết kế sao cho tại mỗi thời điểm chỉ có một hạt xốp nhẹ nhất nổi lên trên bề
mặt. Trước mỗi lần thả, hạt xốp đang nổi trên bề mặt sẽ bị ngấm nước và tăng gấp đôi
khối lượng. Hỏi sau khi thả hạt xốp cuối cùng vào ống thì khối lượng xốp tăng so với tổng
khối lượng ban đầu là bao nhiêu ?
Dữ liệu: Vào từ file văn bản SPONGE.INP
Dòng 1: Số nguyên dương N
Dòng 2: N số nguyên dương
Kết quả: Ghi ra file văn bản SPONGE.OUT
Ghi 1 số duy nhất là đáp án của bài toán
Ví dụ:
SPONGE.INP
3
SPONGE.OUT
3
2 1 3
Thuật toán :
Dễ thấy đây là một danh sách động (giá trị phần tử thay đổi), vì vậy ta xây dựng một
heapmin để lấy ra hạt xốp nhỏ nhất, tăng gấp đôi khối lượng rồi cập nhật lại heapmin.
Const
tfi='sponge.inp';
tfo='sponge.out';
Type
arr1=array[0..100001] of longint;
Var
fi,fo
: text;
w,heap,head,ke,d,c,dd,cost
:
n,nheap,delta
: longint;
arr1;
{==================================}
Procedure nhap;
Var
i : longint;
Begin
Assign(fi,tfi);Reset(fi);
read(fi,n);
For i := 1 to n do
read(fi,w[i]);
cost := w;
Close(fi);
7
End;
{==================================}
Procedure doicho(var x,y : longint);
var
tmp : longint;
Begin
tmp := x;
x
:= y;
y
:= tmp;
End;
{==================================}
Procedure upheap(i : longint);
Var
j : longint;
Begin
While (i <> 1) and (heap[i] < heap[i div 2]) do
Begin
doicho(heap[i],heap[i div 2]);
i := i div 2;
End;
End;
{=============================}
Procedure downheap(i : longint);
Var
j : longint;
Begin
While (2*i <= nheap) do
Begin
j := 2*i;
If (heap[j] > heap[j+1]) and (j heap[j] then
Begin
doicho(heap[i],heap[j]);
i :=j;
End
else exit;
End;
End;
{=============================}
Procedure push(x : longint);
Begin
inc(nheap);
heap[nheap] := x;
upheap(nheap);
End;
{=============================}
Procedure xuly;
Var
i1 : longint;
Begin
For i1 := 1 to n-1 do
Begin
push(w[i1]);
delta := delta + heap[1];
heap[1] := heap[1]*2;
downheap(1);
End;
End;
8
BEGIN
Assign(fo,tfo);Rewrite(fo);
nhap;
xuly;
write(fo,delta);
Close(fo);
END.
2. Bài tập 2: PILOT
HT AIRLINE là một hãng hàng không danh tiếng ở Việt Nam, tuy nhiên, để tồn tại
trong cơn bão suy thoái kinh tế, Ban giám đốc quyết định giảm chi phi tiền lương cho phi
công càng nhiều càng tốt.
HT airline có tất cả N phi công (N là số chẵn), các phi công được đánh số từ 1 đến N
(Phi công 1 là phi công trẻ nhất, phi công i là phi công có tuổi cao thứ i,… phi công n là
phi công cao tuổi nhất). HT airline cần chính xác
N
phi hành đoàn, mỗi phi hành đoàn
2
gồm 2 phi công (một lái chính và một lái phụ), lái chính phải nhiều tuổi hơn lái phụ.
Hợp đồng mà công ty kí với các phi công có 2 điều khoản rõ ràng: tiền lương khi là lái
chính và tiền lương khi là lái phụ. Rõ ràng, đối với 1 phi công, tiền lương lái chính bao giờ
cũng cao hơn tiền lương khi lái phụ. Tuy nhiên, với một phi hành đoàn, có thể tiền lương
của lái chính lại thấp hơn lái phụ.
Để giảm chi phí trả tiền lương, HT phải xác định một cách phân chia tối ưu
N
phi
2
hành đoàn.
Bạn hãy giúp HT viết chương trình xác định số tiền tối thiểu để trả lương cho N phi
công.
Dữ liệu : Vào từ file văn bản PILOT.INP
Dòng 1 : Số nguyên dương N, là số phi công ở HT airline.
N dòng tiếp theo, dòng thứ i là thông tin về phi công i : gồm hai số a và c viết cách
nhau 1 dấu cách trống, tương ứng là tiền lương khi lái chính và tiền lương khi lái
phụ.
Kết quả: Dữ liệu ra ghi vào file PILOT.OUT
Một số nguyên duy nhất là tiền lương tối thiểu phải trả cho N phi công.
Hạn chế :
2 N 10000; N là số chẵn.
9
1 a < c 100.000
Ví dụ :
PILOT.INP
PILOT.OUT
PILOT.INP
6
32000
33000
10000
7000 6
9000
3000 5000
3000
6000
4000 4000
1000
5000
1000 9000
7000
9000
3000 11000
5000
8000
6000
7000
3000
8000
6000
PILOT.OUT
Time limits / test: 1s
Thuật toán:
Ta có nhận xét sau: Theo thứ tự i nhập vào từ 1 đến N, thì cứ i lẻ thì phải có 1 lái phụ. Vì
vậy, ta xây dựng một heap max, lần lượt cho
vào heap, khi i lẻ thì ta lấy trong
heap ra một nút, đây chính là lái phụ.
CONST
tfi
tfo
max
=
=
=
'pilot.inp';
'pilot.out';
100000;
TYPE
Arr1 = array[1..max] of longint;
VAR
fi,fo
:
text;
n,nh,sum,kq
:
longint;
a,b,h
:
Arr1;
{*-----------------------------------------------------------------*}
procedure nhap;
var
i
:
longint;
begin
assign(fi,tfi);reset(fi);
read(fi,n);
For i := 1 to n do
read(fi,a[i],b[i]);
close(fi);
end;
{*-----------------------------------------------------------------*}
procedure doicho(var x,y : longint);
var
tg
:
longint;
10
begin
tg := x;
x := y;
y := tg;
end;
{*-----------------------------------------------------------------*}
procedure upheap(i : longint);
begin
if (i = 1) or (h[i] < h[i div 2]) then exit;
if h[i div 2] < h[i] then
begin
doicho(h[i div 2],h[i]);
upheap(i div 2);
end;
end;
{*-----------------------------------------------------------------*}
procedure downheap(i : longint);
var
j
:
longint;
begin
j := 2 *i;
if j > nh then exit;
if (j < nh) and (h[j] < h[j+1]) then inc(j);
if h[i] < h[j] then
begin
doicho(h[i],h[j]);
downheap(j);
end;
end;
{*-----------------------------------------------------------------*}
procedure push(x : longint);
begin
inc(nh);
h[nh] := x;
upheap(nh);
end;
{*-----------------------------------------------------------------*}
function pop : longint;
begin
pop := h[1];
h[1] := h[nh];
dec(nh);
downheap(1);
end;
{*-----------------------------------------------------------------*}
procedure xuli;
var
i
:
longint;
begin
sum := 0;nh := 0;kq := 0;
For i := 1 to n do
begin
sum := sum + a[i];
push(a[i] - b[i]);
if i mod 2 = 1 then kq := kq + pop;
end;
end;
11
{*-----------------------------------------------------------------*}
procedure inkq;
begin
assign(fo,tfo);rewrite(fo);
write(fo,sum-kq);
close(fo);
end;
{*-----------------------------------------------------------------*}
BEGIN
nhap;
xuli;
inkq;
END.
3. Bài tập 3: Tiểu thuyết trinh thám
Ivan Đneprôp viết truyện tiểu thuyết trinh thám. Truyện của anh ta không có gì đặc
sắc: không có các tình huống ly kỳ đặc biệt, cũng không có các chi tiết hài hước tế nhị.
Thậm chí một hiệu sách đã bán các sáng tác của Ivan theo cân! Nhưng độc giả lại thích
truyện của Ivan. Nó dễ hiểu và giúp người ta thư giản sau một ngày lao động mệt nhọc.
Thực ra, bí mật sự thành công của Ivan là ở chổ không phải chính anh nghĩ ra các tình
huống mà là người em trai Alexei. Ivan có nhiệm vụ viết nó thành các bestsellers. Dĩ
nhiên hai anh em chia nhau hợp lý số tiền kiếm được. Điều đáng tiếc là khả năng sáng tạo
các tình huống ly kỳ của Alexei lại phụ thuộc vào chu kỳ sinh học của anh. Hai anh em
phân tích bảng chu kỳ sinh học của Alexei và thấy rằng trong thời gian tới Alexei sẽ nghĩ
được n chủ đề mới, chủ đề thứ i sẽ được nghĩ ra ở ngày ri. Trong cùng một ngày có thể
Alexei nghĩ ra tới vài câu chuyện.
Với mỗi chủ đề, Ivan thời lượng cần thiết để hoàn thành tác phẩm và tính được rằng
chủ đề thứ i cần có pi ngày để viết. Ivan có trí nhớ cực tốt, vì vậy anh có thể tạm bỏ dở
một truyện, chuyển sang viết truyện khác sau đó quay lại hoàn thành nốt các truyện dở
dang.
Dĩ nhiên, hai anh em muốn sách được viết càng nhanh càng tốt, tức là phải cực tiểu
hóa thời gian trung bình từ thời điểm hiện tại tới thời điểm lúc tiểu thuyết hoàn thành. Vì
số sách là cố định, nên điều này tương đương với việc cực tiểu hóa tổng thời gian viết tất
cả các cuốn sách. Điều này có nghĩa là nếu cuốn sách thứ i được hoàn thành vào ngày ci
thì
c phải được cực tiểu hóa. Ví dụ, ở ngày thứ nhất Alexei nghĩ ra một cốt chuyện mà
i
Ivan cần viết trong 5 ngày, Ivan bắt tay viết ngay. Ngày thứ 2 Alexei nghĩ thêm một cót
chuyện mới cần viết trong một ngày. Ivan chuyển sang viết chuyện mới, ngày thứ 3: chuện
12
thứ hai hoàn thành và Ivan quay lại viết tiếp chuyện thứ nhất, mất thêm 4 ngày nữa, đến
ngày thứ 7 chuyện thứ nhất hoàn thành. Tổng các thời điểm hoàn thành là 3+7 = 10.
Yêu cầu: Cho n, ri và pi. Hãy xác định tổng thời gian ngắn nhất hoàn thành tất cả các
truyện.
Dữ liệu: Vào từ file văn bản PULP.INP:
Dòng 1: Chứa số nguyên n (1 ≤ n ≤ 100.000),
Mỗi dòng trong n dòng sau chứa 2 số nguyên ri và pi.
Kết quả: Ghi ra file PULP.OUT
Một số nguyên – tổng thời gian ngắn nhất tìm được.
Ví dụ:
PULP.INP
2
PULP.OUT
10
1 5
2 1
Thuật toán:
1. Sort tăng theo R[i]
2. Ví dụ với các thời điểm
, dễ dàng ta thấy
3. Với mỗi khoảng thời gian t = R[i] – R[i-1], ta ưu tiên giải quyết công việc cần ít thời
gian nhất, giả sử là công việc P (Thấy ngay là sử dụng Heap để lấy công việc có thời
gian nhỏ nhất)
a. Nếu thời gian thực hiện công việc P < t thì thực hiện hết công việc P, thời
gian còn lại thực hiện tiếp các công việc có thời gian nhỏ tiếp theo.
b. Nếu thời gian thực hiện công việc P > t thì chúng ta thực hiện công việc P
trong khoảng thời gian t, thời gian còn lại là t[P] – t ta lưu lại trong Heap để
tính tiếp.
4. Sau khi xét đến thời điểm N, lúc này ta sẽ phải làm tất cả các công việc còn lại tuần
tự từ nhỏ đến lớn, hay là lấy tất cả các phần tử trong Heap ra là xong.
CONST
tfi
tfo
max
=
=
=
'pulp.inp';
'pulp.out';
100000;
TYPE
Arr1 = array[1..max] of longint;
VAR
fi,fo
:
text;
n,nh,sum,res :
longint;
r,p,h
:
Arr1;
{*------------------------------------------------------------*}
13
procedure nhap;
var
i
:
longint;
begin
assign(fi,tfi);reset(fi);
read(fi,n);
For i := 1 to n do
read(fi,r[i],p[i]);
close(fi);
end;
{*------------------------------------------------------------*}
procedure doicho(var x,y : longint);
var
tg
:
longint;
begin
tg := x;
x := y;
y := tg;
end;
{*------------------------------------------------------------*}
procedure upheap(i : longint);
begin
if (i = 1) or (h[i] > h[i div 2]) then exit;
if h[i div 2] > h[i] then
begin
doicho(h[i div 2],h[i]);
upheap(i div 2);
end;
end;
{*------------------------------------------------------------*}
procedure downheap(i : longint);
var
j
:
longint;
begin
j := 2 * i;
if j > nh then exit;
if (j < nh) and (h[j] > h[j+1]) then inc(j);
if h[i] > h[j] then
begin
doicho(h[i],h[j]);
downheap(j);
end;
end;
{*------------------------------------------------------------*}
procedure push(x : longint);
begin
inc(nh);
h[nh] := x;
upheap(nh);
end;
{*------------------------------------------------------------*}
function pop
:
longint;
begin
pop := h[1];
h[1] := h[nh];
dec(nh);
downheap(1);
end;
14
{*------------------------------------------------------------*}
procedure xuli;
var
i,t,x
:
longint;
begin
nh := 0;
push(p[1]);
sum := r[1];
res := 0;
For i := 2 to n do
begin
t := r[i] - r[i-1];
while (nh > 0) and (t > 0) do
begin
x := pop;
if (x <= t) then
begin
t := t - x;
sum := sum + x;
res := res + sum;
end
else
begin
push(x-t);
t := 0;
end;
end;
push(p[i]);sum := r[i];
end;
while nh > 0 do
begin
x := pop;
sum := sum + x;
res := res + sum;
end;
end;
{*------------------------------------------------------------*}
procedure sort(x,y:longint);
var
i,j,key1,key2
:
longint;
begin
i := x;
j := y;
key1 := r[x+random(y-x+1)];
key2 := p[x+random(y-x+1)];
repeat
while (r[i] < key1) or ((r[i] = key1) and (p[i] < key2)) do
inc(i);
while (r[j] > key1) or ((r[j] = key1) and (p[j] > key2)) do
dec(j);
if i <= j then
begin
doicho(r[i],r[j]);
doicho(p[i],p[j]);
inc(i);
dec(j);
end;
15
until i > j ;
if x < j then sort(x,j);
if y > i then sort(i,y);
end;
{*------------------------------------------------------------*}
procedure inkq;
begin
assign(fo,tfo);rewrite(fo);
write(fo,res);
close(fo);
end;
{*------------------------------------------------------------*}
BEGIN
randomize;
nhap;
sort(1,n);
xuli;
inkq;
END.
4. Bài tập 4: BASE3
Cho 3 số ở hệ cơ số 3 (viết bởi 3 số 0, 1, 2). Hãy tìm một chữ số N ở hệ cơ số 3 sao cho N
có một số lẻ chữ số và số 1 nằm ở chính giữa số N. Số N phải thu được từ việc liên kết 3
số cho trước, mỗi số trong 3 số có thể được sử dụng 0 hoặc nhiều lần:
Yêu cầu:
Xác định số lượng nhỏ nhất các chữ số của N thỏa mãn tính chất đầu bài
Dữ liệu: BASE3.INP
Gồm 3 dòng, mỗi dòng là một số ở hệ cơ số 3.
Kết quả: BASE3.OUT
Số lượng chữ số nhỏ nhất của N. Nếu không tồn tại N thì ghi số 0.
Hạn chế
Số chữ số của một số trong 3 số đầu bài cho trong khoảng từ 1 đến 16.000.
Ví dụ:
BASE3.INP
001
BASE3.OUT
13
020
2020
Giải thích
N = 2020001001001 .
Time limit/test: 0.4
L
1
R
16
Ký tự 1 ở giữa của xâu kết quả phải thuộc 1 trong 3 xâu:
Giả sử ký tự 1 của kết quả nằm ở vị trí I của xâu
, ta sẽ xây dựng xâu kết quả
bằng cách thêm từng xâu vào trái hoặc phải (phần L là trái, ký tự 1 ở giữa, phần R là phải)
Ta sẽ xây dựng xâu đến khi
thì dừng lại (yêu cầu đề bài)
Dễ thấy, ta chỉ quan tâm tới
ghi nhận kết quả. Tức là nếu
tồn tại cách xây dựng L’, R’ mà
thỏa mãn
cũng sử dụng cách xây dựng đó được
với các cặp
với
, chỉ cần lưu 1 cặp có
Quy hoạch động
= cách xếp có
Nếu mỗi lần ta luôn nắp xâu
(do
vào nửa ngắn hơn thì luôn đảm bảo
). Với trạng thái
thái
về trạng thái
với
, ta cập nhật cho trạng
+ độ dài xâu nắp thêm vào. Bài toán trở thành Dijkstra Heap
. Các trạng thái cơ sở có thể là các ký tự 1 của 1 trong 3 xâu ban đầu.
Đáp án bài toán là
{$H+}
uses math ;
const
tfi
=
tfo
=
Nmax
=
vc
=
type
arr1
=
var
fi,fo
:
n,m,nh,ss,xi,yi
'Base3.inp';
'Base3.out';
16001;
1000000000000000000 ;
array[0..Nmax] of longint ;
text;
:
longint;
17
s
:
array[1..3] of string ;
len
:
array[1..3] of longint ;
d
:
array[-Nmax..Nmax,0..1] of int64 ;
pos
:
array[-Nmax..Nmax,0..1] of longint;
h,h2
:
array[0..4*Nmax] of longint;
procedure Nhap;
var
i,j :longint;
begin
ss := 0;
for i := 1 to 3 do
begin
readln(fi,s[i]);
len[i] := length(s[i]);
ss := max(ss,len[i]) ;
end;
end;
procedure Upheap(i:longint) ;
var
x,y:longint ;
begin
x := h[i] ;
y := h2[i];
while (i > 1) and (d[x,y] < d[h[i div 2],h2[i div 2]]) do
begin
h[i] := h[i div 2] ;
h2[i] := h2[i div 2];
pos[h[i],h2[i]] := i ;
i := i div 2;
end ;
h[i] := x;
h2[i] := y;
pos[x,y] := i;
end;
procedure downheap(i:longint);
var
j,x,y:longint;
begin
x := h[i];
y := h2[i];
while i * 2 <= nh do
begin
j := i * 2 ;
if (j < nh) and (d[h[j],h2[j]] >d[h[j+1],h2[j+1]]) then
inc(j);
if d[x,y] <= d[h[j],h2[j]] then break ;
h[i] := h[j];
h2[i] := h2[j];
pos[h[i],h2[i]] := i;
i := j;
end ;
h[i] := x;
h2[i] := y;
pos[x,y] := i ;
end;
procedure Push(i,j:longint);
begin
if pos[i,j] = 0 then
18
begin
inc(nh) ;
h[nh] := i;
h2[nh] := j;
pos[i,j] := nh;
Upheap(nh) ;
end else Upheap(pos[i,j]) ;
end ;
procedure Pop;
begin
xi := h[1];
yi := h2[1];
h[1] := h[nh];
h2[1] := h2[nh];
pos[h[1],h2[1]] := 1;
dec(nh);
downheap(1) ;
end;
procedure Update ;
var
i,j,k:longint;
begin
for i := 1 to 3 do
begin
if s[i][1] = '0' then k := 0 else k := 1;
j := xi + len[i];
if (j <= ss) and (d[j,k] > d[xi,yi] + len[i]) then
begin
d[j,k] := d[xi,yi] + len[i] ;
push(j,k) ;
end;
j := xi - len[i] ;
if (j >= -ss) and (d[j,yi] > d[xi,yi] + len[i]) then
begin
d[j,yi] := d[xi,yi] + len[i];
push(j,yi) ;
end ;
end;
end ;
procedure init;
var
i,j,k,u: longint;
begin
for i := -ss to ss do
for j := 0 to 1 do
d[i,j] := vc ;
for i := 1 to 3 do
for j := 1 to len[i] do if s[i][j] = '1' then
begin
if s[i][1] = '0' then k := 0 else k := 1;
u := (j - 1) - (len[i] - j) ;
d[u,k] := len[i] ;
push(u,k) ;
end;
end;
procedure xuly;
var
i,j,k: longint;
19
- Xem thêm -
.DOC 
21 
407 
108 
