Ôn tập chuẩn bị cho kỳ thi Tỉnh bảng A

[damnguyenhuu]

Mở đầu là thuật toán QUAY LUI

Trước hết, mình sẽ trích lại lý thuyết cho thuật toán này (trích trong "Bài giảng chuyên đề" của LÊ MINH HOÀNG)

Thuật toán quay lui dùng để giải bài toán liệt kê các cấu hình. Mỗi cấu hình được xây dựng bằng cách xây dựng từng phần tử, mỗi phần tử được chọn bằng cách thử tất cả các khả năng.
Giả thiết cấu hình cần liệt kê có dạng (x1, x2, ..., xN). Khi đó thuật toán quay lui thực hiện qua các bước sau:
1) Xét tất cả các giá trị x1 có thể nhận, thử cho x1 nhận lần lượt các giá trị đó. Với mỗi giá trị thử gán cho x1 ta sẽ:
2) Xét tất cả các giá trị x2 có thể nhận, lại thử cho x2 nhận lần lượt các giá trị đó. Với mỗi giá trị thử gán cho x2 lại xét tiếp các khả năng chọn x3... cứ tiếp tục như vậy đến bước:
N) Xét tất cả các giá trị xN có thể nhận, thử cho xN nhận lần lượt các giá trị đó, thông báo cấu hình tìm được (x1, x2, ..., xN).

Trên phương diện quy nạp, có thể nói rằng thuật toán quay lui liệt kê các cấu hình N phần tử dạng (x1, x2, ..., xN) bằng cách thử cho x1 nhận lần lượt các giá trị có thể. Với mỗi giá trị thử gán cho x1 lại liệt kê tiếp cấu hình (N - 1) phần tử (x2, x3, ..., xN).

Mô hình của thuật toán quay lui có thể mô tả như sau:


{Thủ tục này thử cho xi nhận lần lượt các giá trị mà nó có thể nhận}
Procedure Try(i: Integer);
Begin
For (mọi giá trị V có thể gán cho xi) Do
Begin
<Thử cho xi := V>;
If (xi là phần tử cuối cùng trong cấu hình) Then
<Thông báo cấu hình tìm được>
Else
Begin
<Ghi nhận việc cho xi nhận giá trị V (nếu cần)>;
Try(i + 1); {Gọi đệ quy để chọn tiếp x(i+1)}
<Nếu cần, bỏ ghi nhận việc thử xi := V, để thử giá trị khác>;
End;
End;
End;

Thuật toán quay lui sẽ bắt đầu bằng lời gọi Try(1)
Ta có thể trình bày quá trình tìm kiếm lời giải của thuật toán quay lui bằng cây sau:


Try(1)
/ \
Try(2) Try(2)
/ \ / \
Try(3) Try(3) Try(3) Try(3)
/ \ / \ / \ / \
(--) (--) (--) (--) (--) (--) (--) (--)

Cây tìm kiếm quay lui

[quangtq]

1. ?? Bảng A là của tiểu học mà.
2. Mỗi quay lui thôi à.
Cho thêm cái sinh, nhánh cận, QhĐ vào chứ.

[chick chick]

mới là mở đầu mà lol lol

[damnguyenhuu]

1. ?? Bảng A là của tiểu học mà.
Bảng A Tỉnh không phải là của Tiểu học bạn à! Các chỗ khác thì anh không biết chứ Khánh Hòa thì vào khoảng đầu tháng 11 sẽ thi. Bảng A là bảng dành cho các trường đã có thành tích cao, trường chuyên và được Sở Giáo Dục cho phép dự thi. Bảng A khó hơn so với bảng B.

[bld]

em thấy post sách lên có lẽ hợp hơn đấy anh :
a part of programming data in my computer :
http://www.mediafire.com/?sharekey=9548039fa4c713a40de4fc1039a016742606a0b0 9eb8df445be6ba49b5870170

[hang_vt]

post bài tập lên ik a :)

[quangtq]

post bài tập lên ik a :)
Chuẩn. Em nghĩ giống chị H thế này hay hơn

[damnguyenhuu]

Chuẩn. Em nghĩ giống chị H thế này hay hơn

Đúng rồi. Nhưng mún làm bài tập thì phải có một chút lý thuyết nữa chứ. Có nhiều thành viên khác nữa mà. Đâu chỉ chúng ta. :)

[mini_bestboy]

Mình đồng ý với bạn damnguyenhuu, nên phổ biến lý thuyết trước rồi sau đó là vài bài tập thực hành, sau khi đủ lý thuyết hết thì làm những bài tổng hợp, vậy hay hơn :D .
@Damnguyenhuu: Mình cũng sắp thi Tỉnh mà chả biết bảng A hay bảng B là gì cả, chậc chậc ! Mà các tỉnh có thi cùng lúc nhau ko vậy ? Sao mình nghe đâu bên mình thi tháng 10 mà ? Ép nick mình nha ^^ mini_bestboy@yahoo.com

[chick chick]

cú đưa hết lí thuyết lên đi, rồi mới đến bài tập
người VN ta thích bài tập, càng bài khó lại càng thích, nhưng chưa chắc các bạn đã nắm chắc hết lí thuyết đâu.

[damnguyenhuu]

I - Liệt kê các dãy nhị phân độ dài N.

Biểu diễn dãy nhị phân độ dài N dưới dạng (x1, x2, ..., xN). Ta sẽ liệt kê các dãy này bằng cách thử dùng các giá trị {0, 1} gán cho xi. Với mỗi giá trị thử gán cho xi lại thử các giá trị có thể gán cho x(i+1). Chương trình liệt kê bằng thuật toán quay lui có thể viết như sau:


Program BinaryStrings;
Const
max = 30;
Var
x: Array[1..max] of Integer;
n: Integer;
{In cấu hình tìm được, do thủ tục tìm đệ quy Try gọi khi tìm ra một cấu hình}
Procedure PrintRusult;
Var i: Integer;
Begin
For i:= 1 To n Do Write(x);
Writeln;
End;
{Thử các cách chọn x}
Procedure Try(i: Integer);
Var j: Integer;
Begin
For j:= 0 To 1 Do {Xét các giá trị có thể gán cho xi}
Begin
x[i]:= j; {Thử đặt xi}
If i = n Then PrintResult {Nếu i = n thì in kết quả}
Else Try(i+1); {Nếu i chưa phải là phần tử cuối thì tìm tiếp x(i+1)}
End;
End;
Begin
Assign(Input, 'BSTR.INP');
Reset(Input);
Assign(Output, 'BSTR.OUT');
Rewrite(Output);
Readln(n);
Try(1);
Close(Input);
Close(Output);
End.


[i]Ví dụ: Khi n = 3, cây tìm kiếm quay lui như sau:


-----------Try(1)-----------
x1:=0 | | x1:=1
| |
------Try(2)------ ------Try(2)------
x2:=0 | x2:=1 | |x2:=0 |x2:=1
| | | |
---Try(3)--- ---Try(3)--- ---Try(3)--- ---Try(3)---
| | | | | | | |
| (001) | (011) | (101) | (111)
| | | |
(000) (010) (100) (110)


[=========> Bổ sung bài viết <=========]

II - Liệt kê các tập con K phần tử.

Để liệt kê các tập con k phần tử của tập S = {1, 2, ..., n} ta có thể đưa về liệt kê các cấu hình (x(1), x(2), ..., x(k)) ở đây các x(i) thuộc S và x(1) < x(2) < ... < x(k). Ta có nhận xét:
+ x(k) <= n.
+ x(k - 1) <= x(k) - 1 <= n - 1
+ ...
+ x(i) <= n - k + i
+ ...
+ x(1) <= n - k + 1.

Từ đó suy ra x(i-1) + 1 <= x(i) <= n - k + i (1 <= i <= k) ở đây ta giả thiết có thêm một số x(0) = 0 khi xét i = 1. Như vậy ta sẽ xét tất cả các cách chọn x(1) từ 1 (= x(0) + 1) đến n - k + 1, với mỗi giá trị đó, xét tiếp tất cả các cách chọn x(2) từ x(1) + 1 đến n - k + 2, ... cứ như vậy khi chọn được đến x(k) thì ta có một cấu hình cần liệt kê. Chuơng trình liệt kê bằng thuật toán quay lui như sau:


Program Combinations;
Const max = 30;
Var x: Array[0..max] of Integer;
n, k: Integer;
{In ra tập con {x1, x2, ..., xk)}
Procedure PrintResult;
Var i: Integer;
Begin
Write('{');
For i:= 1 To k - 1 Do Write(x[i], ', ');
Writeln(x[k], '}');
End;
{Thử các cách chọn giá trị cho x[i]}
Procedure Try(i: Integer);
Var j: Integer;
Begin
For j:= x[i-1] + 1 To n - k + i Do
Begin
x[i]:= j;
If i = k Then PrintResult
Else Try(i+1);
End;
End;
Begin
Assign(In, 'SUBSET.INP'); Reset(In);
Assign(Out, 'SUBSET.OUT'); Rewrite(Out);
Readln(n, k);
x[0]:= 0;
Try(1);
Close(In);
Close(Out);
End.


Nếu để ý chuơng trình trên và chương trình liệt kê dãy nhị phân độ dài n, ta thấy về cơ bản chúng chỉ khác nhau ở thủ tục Try(i) - chọn thử các giá trị cho x(i), ở chương trình liệt kê dãy nhị phân ta thử chọn các giá trị 0 hoặc 1 còn ở chương trình liệt kê các tập con k phần tử ta thử chọn x(i) là một trong các giá trị nguyên từ x(i-1) + 1 đến n - k + i. Qua đó ta có thể thấy tính phổ dụng của thuật toán quay lui: mô hình cài đặt có thể thích hợp cho nhiều bài toán, khác với phương pháp sinh tuần tự, với mỗi bài toán lại phải có một thuật toán sinh kế tiếp riêng làm cho việc cài đặt mỗi bài một khác, bên cạnh đó, không phải thuật toán sinh kế tiếp nào cũng dễ cài đặt.

[=========> Bổ sung bài viết <=========]

III - Liệt kê các chỉnh hợp không lặp chập K.

Để liệt kê các chỉnh hợp không lặp chập K của tập S = {1, 2, ..., N} ta có thể đưa về liệt kê các cấu hình (x1, x2, ..., xK) ở đây các xi thuộc S và khác nhau đôi một.

Như vậy thủ tục Try(i) - xét tất cả các khả năng chọn xi - sẽ thử hết các giá trị từ 1 đến n, mà các giá trị này chưa bị các phần tử đứng trước chọn. Muốn xem các giá trị nào chưa được chọn ta sử dụng kỹ thuật dùng mảng đánh dấu:
+ Khởi tạo một mảng c1, c2, ..., cN mang kiểu logic. Ở đây ci cho biết giá trị i có còn tự do hay đã bị chọn rồi. Ban đầu khởi tạo tất cả các phần tử mảng c là TRUE có nghĩa là các phần tử từ 1 đến N đều tự do.
+ Tại bước chọn các giá trị có thể của xi ta chỉ xét những giá trị j có cj = TRUE có nghĩa là chỉ chọn những giá trị tự do.
+ Trước khi gọi đệ quy tìm x(i+1): ta đặt giá trị j vừa gán cho xi là đã bị chọn có nghĩa là đặt cj:= FALSE để các thủ tục Try(i+1), Try(i+2), ... gọi sau này không chọn phải giá trị j đó nữa.
+ Sau khi gọi đệ quy tìm x(i+1): có nghĩa là sắp tới ta sẽ thử gán một giá trị khác cho xi thì ta sẽ đặt giá trị j vừa thử đó thành tự do (cj:= TRUE), bởi khi xi đã nhận một giá trị khác rồi thì các phần tử đứng sau: x(i+1), x(i+2), ... hoàn toàn có thể nhận lại giá trị j đó. Điều này hoàn toàn hợp lý trong phép xây dựng chỉnh hợp không lặp: x1 có n cách chọn, x2 có n - 1 cách chọn, ...Lưu ý rằng khi thủ tục Try(i) có i = k thì ta không cần phải đánh dấu gì cả vì tiếp theo chỉ có in kết quả chứ không cần phải chọn thêm phần tử nào nữa.

Input: File văn bản ARRANGES.INP chứa 2 số nguyên dương n, k (1 <= k <= n <= 20) cách nhau ít nhất một dấu cách.

Output: File văn bản ARRANGES.OUT ghi các chỉnh hợp không lặp chập K của tập {1, 2, ..., n}


ARRANGES.INP ARRANGES.OUT
3 2 1 2
1 3
2 1
2 3
3 1
3 2




Program ARRANGES;
Const max = 20;
Var x: Array[1..max] Of Integer;
c: Array[1..max] Of Integer;
n, k: Integer;
{Thủ tục in cấu hình tìm được}
Procedure PrintResult;
Var i: Integer;
Begin
For i:= 1 To K Do Write(x[i],' ');
Writeln;
End;
{Thử các cách chọn xi}
Procedure Try(i: Integer);
Var j: Integer;
Begin
For j:= 1 To N Do
If c[j] Then {Chỉ xét những giá trị j còn tự do}
Begin
x[i]:= j;
If i = k Then PrintResult {Nếu đã chọn được đến xK thì chỉ in}
Else
Begin
x[j]:= False; {Đánh dấu j đã bị chọn}
Try(i+1); {Chỉ xét những gt tự do gán cho x(i+1)}
c[j]:= True; {Bỏ đánh dấu j lại là tự do}
End;
End;
End;
Begin
Assign(Input, 'ARRANGES.INP'); Reset(Input);
Assign(Output, 'ARRANGES.OUT'); Rewrite(Output);
Readln(n, k);
Fillchar(c, SizeOf(c), True); {Tất cả đều chưa bị chọn}
Try(1); {Thủ các cách chọn gt của x1}
Close(Input);
Close(Output);
End.

Nhận xét: khi k = n thì đây là chuơng trình liệt kê hoán vị.

[quangtq]

Em ko biết nói thế này có hơi quá không nhưng nếu thế này thì bld post link sách lên là được rồi. Tại đều trong quyển của LMH mà.

[damnguyenhuu]

Đúng rồi! Ý anh là muốn em vừa xem đề nếu quên thì xem lại lý thuyết cho nhanh khỏi phải mở pdf lên. :D
Vậy giờ anh post bài tập cho mấy em làm ha!

[=========> Bổ sung bài viết <=========]

Bài 1: Hoán vị

Các hoán vị của N chữ cái hoa tiếng anh A..Z được sắp tăng theo trật tự từ điển và được viết liền nhau để tạo thành một dãy kí tự duy nhất. Xác định kí tự thứ M trong dãy, gọi là kí tự C.
Dữ liệu vào: Cho trong file văn bản mang tên HV.INP, gồm 1 dòng chứa 2 số nguyên N và M. Các số trên cùng dòng cách nhau bởi dấu cách. 1 <= N <= 10, 1 <= M <= N*N!
Dữ liệu ra: Vào file văn bản mang tên HV.OUT, gồm 1 dòng cho biết kí tự thứ M trong dãy.
Ví dụ:


HV.INP HV.OUT
4 15 D

Trong ví dụ trên, do N = 4 nên ta có dãy:
ABCDABDCACBDACDBAD...
và do đó kí tự thứ 15 trong dãy sẽ là: D.

(Đề thi Olympic 30-4-2002)

[mini_bestboy]

Bài hoán vị :
Lấy M div N = k,chính là hoán vị thứ k, rồi lấy M mod N = i, là ký tự thứ i của hoán vị thứ k. Dùng quay lui để tìm nữa là xong. Đúng ko anh :)

[quangtq]

1. Đơn giản nhất là liệt kê :D
2. Nghĩ thế này ko biết có sai ko
Số lần kí tự A đứng đầu là (n-1)!.
Ta xét: Nếu vị trí của kí tự M > N(n-1)! thì nó ko ở trong đoạn có kí tự A ở đầu.
Tương tự xét tiếp, ta biết được kí tự nào bắt đầu đoạn đó.
Xác định vị trí kí tự M trong dãy có kí tự đầu giống nhau. Giả sử là A
Nếu (M-1) chia hết cho N, thì M là kí tự A.
Nếu (M-1) ko chia hết cho N, sắp xếp lại dãy, dồn các kí tự A lên đầu, vtM = vtM+(N-1)!. Xét dãy đằng sau, gồm toàn các kí tự ko phải A.
Lặp lại các bước như trên với dãy toàn B..N. Ta được kq.
Ý tưởng. Chưa thử code :D

[damnguyenhuu]

Ý tưởng cho một bài toán thì nhiều lắm! :)
Nên nếu có code thì post lên cho anh em xem lun để được học hỏi! Nhá!
Chúc cả nhà thành công!

[hang_vt]

const fi='hv.inp';
fo='hv.out';

var f:text;
a:array[1.. 10] of char=('a','b','c','d','e','f','g','h','i','j');
dd:array[1..36288000] of boolean;
x,s:array[1..36288000] of char;
n,m,k:longint;

procedure inp;
begin
assign(f,fi);
reset(f);
readln(f,n,m);
fillchar(dd,sizeof(dd),true);
close(f);
end;

procedure pri1;
var i:longint;
begin
for i:=1 to n do
begin
inc(k);
s[k]:=x[i];
if k=m then
begin
writeln(f,s[m]);
close(f);
halt;
end;
end;
end;

procedure try(i:byte);
var j,h:byte;
begin
for j:=1 to n do
if dd[j] then
begin
x[i]:=a[j];
dd[j]:=false;
if i=n then pri1
else try(i+1);
dd[j]:=true;
end;
end;

procedure pri;
begin
assign(f,fo);
rewrite(f);
try(1);
close(f);
end;

begin
inp;
pri;
end.

[damnguyenhuu]

Cho tọa độ (trong hệ trục tọa độ vuông góc) của n hòn đảo là N1(x1; y1), X2(x2; y2), ..., Nn(xn; yn) và giả thiết rằng tất cả thùng chứa của canô chỉ đủ chứa một lượng xăng để đi quảng đường dài không quá M km cho trước. Trên mỗi đảo đều có sẵn xăng dự trữ để canô có thể nạp đầy các thùng chứa. Hãy tìm mọi đường đi có thể có của canô xuất phát từ đảo N1(x1; y1) đến Nj(xj; yj) và chỉ ra một đường đi tối ưu (có số lần ghé vào đảo để lấy xăng là ít nhất).
Dữ liệu vào: cho trong file DIDAO.INP gồm:
+ Dòng đầu ghi số nguyên duơng N là số đảo (2 <= N <= 100).
+ Dòng thứ 2 ghi 2N số nguyên cách nhau ít nhất 1 khoảng trắng là tọa độ các đảo trong hệ trục Oxy: x1 y1 x2 y2 ... xn yn.
+ Dòng thứ 3 ghi 2 số i, j chỉ đảo xuất phát và đảo đích phải đến.
+ Dòng thứ 4 ghi số M là một số nguyên duơng cho biết quãng đường dài nhất mà Canô có thể đi được với thời lượng xăng đã lấy sau mỗi lần tiép nhiên liệu.
Kết quả: In ra file DIDAO.OUT liệt kê mọi đường đi có thể có từ đảo i đến đảo j và chỉ ra một đường đi tối ưu (có số lần ghé vào đảo để lấy xăng là ít nhất).


DIDAO.INP
7
-5 -4 -3 2 0 4 2 3 4 2 5 -1 7 -3
2 5
6

DIDAO.OUT
2 --> 3 --> 4 --> 5
2 --> 3 --> 4 --> 6 --> 5
2 --> 3 --> 5
2 --> 4 --> 3 --> 5
2 --> 4 --> 5
2 --> 4 --> 6 --> 5
2 --> 4 --> 6 --> 7 --> 5
Tong so duong di: 7
Duong di toi uu:
2 --> 3 --> 5

[quangtq]

1. Liệt kê thì quay lui là hợp lí.
2. Ý tưởng:
Tính được độ dài nối giữa 2 đỉnh bất kì. Tìm đường đi ngắn nhất từ i đến j.
Đó chính là đường đi cần tìm. Chắc thế :D

[damnguyenhuu]

(Chia quà)
Có N món quà được đánh số từ 1 đến N (N <= 20). Trong đó món quà thứ i có giá trị là a[i] (1 <= a[i] <= 10000). Cần chia N món quà trên cho 3 người.
Gọi T1, T2, T3 lần lượt là Tổng giá trị các món quà của mỗi người.
Gọi TongMax, TongMin lần lượt là giá trị lớn nhất và nhỏ nhất của T1, T2, T3.
Yêu cầu: Hãy tìm cách chia N món quà trên cho 3 người sao cho chênh lệch TongMax và TongMin là nhỏ nhất.
Dữ liệu vào: Cho trong file văn bản CHIAQUA.INP gồm 2 dòng:
+ Dòng đầu chứa số nguyên N.
+ Dòng thứ hai có N số nguyên a[i], các số cách nhau ít nhất một dấu cách.
Dữ liệu ra: Cho ra file văn bản CHIAQUA.OUT gồm các dòng:
+ Dòng đầu chứa số nguyên cho biết độ chênh lệch nhỏ nhất tìm được.
+ 3 dòng tiếp theo, mỗi dòng cho biết thứ tự các món quà mà người thứ 1, 2, 3 nhận được.
Ví dụ:


CHIAQUA.INP CHIAQUA.OUT
5 3
3 5 10 2 4 1 5
2 4
3

CHIAQUA.INP CHIAQUA.OUT
15 0
3 5 10 2 4 1 7 18 6 8 9 11 1 2 3 4 5 6 7 11
12 13 14 8 12 13
9 10 14 15

[quangtq]

Quy hoạch động. Sửa 1 chút bài chia kẹo cho 2 người là ra 3 người ngay.

[hang_vt]

bài đi đảo :)


const fi='didao.inp';
fo='didao.out';

type td=record
x,y:integer;
end;

var f:text;
a:array[1..100] of td;
l,kq:array[1..100] of integer;
dd:array[1..100] of boolean;
k,h,m,n,max,c:integer;

procedure inp;
var i:integer;
begin
assign(f,fi);
reset(f);
readln(f,n);
for i:=1 to n do
read(f,a[i].x,a[i].y);
readln(f,k,h);
readln(f,m);
fillchar(dd,sizeof(dd),true);
close(f);
end;

function kc(x1,y1,x2,y2:integer):real;
begin
kc:=sqrt(sqr(x2-x1)+sqr(y2-y1));
end;

procedure pri1(g:integer);
var j:integer;
begin
if l[g]=h then
begin
inc(c);
if g<max then
begin
max:=g;
for j:=1 to g do
kq[j]:=l[j];
end;
for j:=1 to g do
write(f,l[j],' ');
writeln(f);
end;
end;

procedure try(i:byte);
var j:byte;
begin
for j:=1 to n do
if not (kc(a[l[i-1]].x,a[l[i-1]].y,a[j].x,a[j].y)>m) and (dd[j]) then
begin
l[i]:=j;
dd[j]:=false;
pri1(i);
try(i+1);
dd[j]:=true;
end;
end;

procedure pri;
var i:integer;
begin
assign(f,fo);
rewrite(f);
l[1]:=k;
dd[2]:=false;
max:=maxint;
try(2);
writeln(f,'Tong duong di :',c);
writeln(f,'Duong di toi uu :');
for i:=1 to max do
write(f,kq[i],' ');
close(f);
end;

begin
inp;
pri;
end.

[damnguyenhuu]

(Khinh khí cầu)
Một chiếc khinh khí cầu hoạt động theo 3 phương thức sau:
(1) Tăng vận tốc từ V[i-1] lên V[i], độ cao không đổi (V[0] < V[1] < ... < V[v]).
(2) Tăng độ cao từ H[j] lên H[j+1], vận tốc không đổi (H[0] < H[1] < ... < H[H]).
(3) Cùng lúc tăng độ cao và vận tốc: H[j] lên H[j+1], V[i-1] lên V[i] (0 < i <= V; 0 <= i <= H).

Nhiên liệu để khinh khí cầu hoạt động theo phương thức trên tùy thuộc vào độ cao và vận tốc hiện tịa của khinh khí cầu.

Yêu cầu: từ trạng thái ban đầu ở độ cao H[0], vận tốc V[0] hãy tìm phương án (dãy thứ tự các phương thức) để đưa khinh khí cầu đến độ cao H[H] với vận tốc V[V] sao cho sử dụng ít nhiên liệu nhất. (0 <= H <= 100; 0 <= V <= 100). Nếu có nhiều phương án cần liệt kê đầy đủ.

Dữ liệu: Cho trong file KHICAU.INP có cấu trúc:
+ Dòng đầu ghi 2 số H, V.
+ Trong H + 1 dòng tiếp: dòng thứ j (0 <= j <= H) ghi V số nguyên: a1, a2, ..., aV. Số ai (0 < i <= V) là nhiên liệu cần thiết để đưa khinh khí cầu đang ở độ cao H[j] ở vận tốc V[i-1] theo phương thức (1) đạt đến vận tốc V[i].
+ Trong V+1 dòng tiếp: dòng thứ j (0 <= i <= V) ghi H số nguyên: b1, b2, ..., bH. Số bj (0 < j <= H) là nhiên liệu cần thiết để đưa khinh khí cầu đang ở vận tốc V[i], độ cao H[j-1] lên độ cao H[j] theo phương thức (2).
+ Trong H dòng tiếp: dòng thứ j (0 < j <= H) ghi V số nguyên: c1, c2, ..., cV. Số ci (0 < i <= V) là nhiên liệu cần thiết để đưa khinh khí cầu đang ở độ cao H[j-1], vận tốc V[i-1] theo phương thức (3) đạt đến vận tốc V[i] và độ cao H[j].

Kết quả: Ghi ra file KHICAU.OUT.
+ Dòng đầu: ghi tổng nhiên liệu cần thiết.
+ Các dòng tiếp, mỗi dòng ghi 1 phương án: là 1 dãy thứ tự các phương thức thực hiện.
+ Dòng cuối cho biết số phương án.

Ví dụ:


KHICAU.INP KHICAU.OUT
4 5 82
13 18 10 15 17 2 2 3 1 1 3 1
15 12 10 11 16 2 2 3 3 1 1 1
16 18 13 15 12 2
10 12 10 14 13
13 12 10 10 9
10 8 13 15
12 16 14 14
16 14 12 13
13 12 13 12
18 13 16 11
19 9 10 10
20 18 16 25 21
25 24 18 19 14
17 20 18 21 19
20 18 17 16 15

[hang_vt]

bài chia quà


const fi='chiaqua.inp';
fo='chiaqua.out';

var f:text;
n:byte;
mx:integer;
a,kq,x:array[1..20] of byte;

procedure inp;
var i:byte;
begin
assign(f,fi);
reset(f);
readln(f,n);
for i:=1 to n do
read(f,a[i]);
close(f);
end;

function min(a,b,c:byte):byte;
var m:byte;
begin
m:=a;
if b<m then m:=b;
if c<m then m:=c;
min:=m;
end;

function max(a,b,c:byte):byte;
var m:byte;
begin
m:=a;
if b>m then m:=b;
if c>m then m:=c;
max:=m;
end;

procedure try(i,t1,t2,t3:byte);
var j,h:byte;
begin
for j:=1 to 3 do
begin
x[i]:=j;
case j of
1:t1:=t1+a[i];
2:t2:=t2+a[i];
3:t3:=t3+a[i];
end;
if i=n then
begin
h:=max(t1,t2,t3)-min(t1,t2,t3);
if h<mx then
begin
kq:=x;
mx:=h;
end
end
else try(i+1,t1,t2,t3);
case j of
1:t1:=t1-a[i];
2:t2:=t2-a[i];
3:t3:=t3-a[i];
end;
end;
end;

procedure pri;
var i:byte;
begin
assign(f,fo);
rewrite(f);
writeln(f,mx);
for i:=1 to n do
if kq[i]=1 then write(f,i,' ');
writeln(f);
for i:=1 to n do
if kq[i]=2 then write(f,i,' ');
writeln(f);
for i:=1 to n do
if kq[i]=3 then write(f,i,' ');
writeln(f);
close(f);
end;

begin
inp;
mx:=maxint;
try(1,0,0,0);
pri;
end.



@ Q : CT QHĐ ?
n~ bài n nhỏ nên nghĩ đến quay lui , đừng lạm dụng QHĐ quá :)

[m2mpro]

Bài Chia Quà :

Mỗi món quà có 3 cách chia : chia cho người 1, người 2 hoặc người 3.

=> Tất cả sẽ có 3x3x3x3x..x3 ( n số ) = 3^n trường hợp.

Tối đa có 3^20 trường hợp, xấp xỉ 3 tỉ th, quay lui ko biết bao giờ xong nhỉ :)

[hang_vt]

éc :( , đọc lại đề cái

[quangtq]

Đúng rồi mà chị, 3^20 chạy lâu lắm.
Vét ko được đâu.
QHĐ cho lành.

[m2mpro]

Đúng rồi mà chị, 3^20 chạy lâu lắm.
Vét ko được đâu.
QHĐ cho lành.

Quang này, nói thì nói cho rõ, QHĐ là QHĐ thế nào ? Đừng có gặp cái gì cũng QHĐ nhé.

[quangtq]

À thì giống bài chia kẹo cho 2 người ý.
Gọi M là tổng giá trị các gói kẹo.
Tìm số T:
T<=M div 3;
T lớn nhất có thể.
Việc tìm này là bài "Chia kẹo" cơ bản trong sách :D
P/S: Em có lúc nào cũng nói về QHD đâu, e gà QHĐ, cái nào cơ bản mới làm được thôi

[bld]

QHD kiểu này có ổn ko nhỉ ? >.<

[hang_vt]

@ bld : e cứ thử code ik . Bài này c chỉ bik làm quay lui thôi :))