SỞ GIÁO DỤC VÀ ĐÀO TẠO ĐỒNG NAI
Đơn vị Trường THPT chuyên Lương Thế Vinh
Mã số: ................................
SÁNG KIẾN KINH NGHIỆM
CHỌN CẤU TRÚC DỮ LIỆU CHO BÀI
TOÁN QUY HOẠCH ĐỘNG
Người thực hiện: LÊ QUANG VINH
Lĩnh vực nghiên cứu:
- Quản lý giáo dục
- Phương pháp dạy học bộ môn: TIN HỌC
- Lĩnh vực khác: .......................................................
Có đính kèm: Các sản phẩm không thể hiện trong bản in SKKN
Mô hình Đĩa CD (DVD)
Phim ảnh
Năm học: 2014 - 2015
Hiện vật khác
SƠ LƯỢC LÝ LỊCH KHOA HỌC
––––––––––––––––––
I. THÔNG TIN CHUNG VỀ CÁ NHÂN
1. Họ và tên: LÊ QUANG VINH
2. Ngày tháng năm sinh: 19/12/1985
3. Nam, nữ: Nam
4. Địa chỉ: Phòng V3, KTX trường THPT chuyên Lương Thế Vinh
5. Điện thoại:
(CQ)/
6. Fax:
(NR); ĐTDĐ: 0167 803 8755
E-mail:
[email protected]
7. Chức vụ: Tổ trưởng
8. Nhiệm vụ được giao: giảng dạy
9. Đơn vị công tác: trường THPT chuyên Lương Thế Vinh
II. TRÌNH ĐỘ ĐÀO TẠO
- Học vị (hoặc trình độ chuyên môn, nghiệp vụ) cao nhất: Thạc sĩ
- Năm nhận bằng: 2012
- Chuyên ngành đào tạo: Công nghệ thông tin
III. KINH NGHIỆM KHOA HỌC
- Lĩnh vực chuyên môn có kinh nghiệm: Giảng dạy Tin học
Số năm có kinh nghiệm: 8
- Các sáng kiến kinh nghiệm đã có trong 5 năm gần đây:
o Lý thuyết và bài tập đồ thị - Phần cây khung (năm 2011)
o Website bồi dưỡng năng khiếu tin học (năm 2012)
o Đưa bài tập trên website VNOI vào giảng dạy Tin học chuyên (năm
2013)
o Định hướng ra đề các kì thi học sinh giỏi bộ môn Tin học (năm
2014)
Tên SKKN :
CHỌN CẤU TRÚC DỮ LIỆU CHO BÀI TOÁN QUY HOẠCH ĐỘNG
I. LÝ DO CHỌN ĐỀ TÀI
Trong các kì thi học sinh giỏi cấp tỉnh, cấp quốc gia hiện nay, dạng bài toán
Quy hoạch động ngày càng phổ biến, chiếm đa số trong các bài thi.
Bài toán Quy hoạch động đề cập ở đây là bài toán có thể giải bằng phương pháp Quy
hoạch động. Tư tưởng của phương pháp này là tính kết quả của bài toán chính thông
qua kết quả các bài toán con của nó theo một công thức truy hồi. Việc lưu trữ kết
quả các bài toán con một cách tối ưu là nhiệm vụ chính của phương pháp này. Học
sinh mới làm quen dạng bài này thường gặp khó khăn khi chọn cấu trúc dữ liệu để
lưu trữ.
Sáng kiến kinh nghiệm “Chọn cấu trúc dữ liệu cho bài toán Quy hoạch động”
giới thiệu một số bài tập Quy hoạch động được phân loại theo các cấu trúc dữ liệu
sử dụng. Giúp cho học sinh dễ dàng nhận biết dạng bài và có thêm “kinh nghiệm”
để chọn đúng cấu trúc dữ liệu. Sáng kiến kinh nghiệm này nhằm mục đích:
Bồi dưỡng học sinh các lớp chuyên Tin
Bồi dưỡng các đội tuyển thi học sinh giỏi.
Giới thiệu, trao đổi với giáo viên đồng nghiệp về dạng bài toán Quy hoạch
động và cách tiếp cận theo hướng cấu trúc dữ liệu.
II. CƠ SỞ LÝ LUẬN VÀ THỰC TIỄN
Hiện đã có một số tài liệu trình bày chuyên đề Quy hoạch động như:
Sách giáo khoa chuyên Tin quyển 1 [1, 97 - 107]: trình bày một số ví dụ đặc
trưng và bài tập rèn luyện. Chưa có phân loại theo một tiêu chí nhất định.
Giải thuật và lập trình [2, 155 - 189]: trình bày giống Sách giáo khoa chuyên
Tin quyển 1.
Tài liệu bồi dưỡng năng khiếu Tin học khối THPT [4, 85 – 109]: trình bày
nhiều ví dụ về bài toán Quy hoạch động, có lời giải, chương trình cài đặt cụ
thể. Tuy nhiên, chưa có phân loại bài tập.
Kho bài tập trên website spoj.com [5]: tổng hợp bài tập của tất cả các dạng
bài, thích hợp để học sinh luyện tập. Các bài tập Quy hoạch động trên website
cũng chưa được phân loại.
Trong quá trình giảng dạy các lớp chuyên Tin, tác giả nhận thấy đa số các học sinh
khi mới làm quen với dạng bài này, sau khi tìm ra công thức truy hồi, thường gặp
khó khăn trong việc cài đặt, mà chủ yếu là chọn cấu trúc dữ liệu để lưu trữ các bài
toán con. Cần có một sự phân loại chi tiết hơn các bài toán Quy hoạch động. Tác giả
chọn tiêu chí phân loại theo cấu trúc dữ liệu để giúp học sinh có thêm “kinh nghiệm”
để chọn đúng cấu trúc dữ liệu cho bài toán.
1
III. TỔ CHỨC THỰC HIỆN CÁC GIẢI PHÁP
1. Tổ chức thực hiện
1) Tìm hiểu nội dung chương trình tin học chuyên sâu, nội dung chuyên đề Quy
hoạch động trong tài liệu “Chương trình chuyên sâu THPT chuyên – môn Tin học”
do Bộ Giáo Dục và Đào Tạo phát hành năm 2009.
Theo tài liệu này, chuyên đề Quy hoạch động được giảng dạy trong 15 tiết ở
khối 11, sau khi học xong yêu cầu học sinh phải làm được các bài toán quen
thuộc như: - Bài toán dãy con đơn điệu tăng dài nhất; Bài toán xâu con chung
dài nhất; Bài toán biến đổi xâu; Bài toán cái túi; Bài toán lũy thừa một số; Bài
toán nhân các ma trận; Bài toán chia đa giác thành các tam giác; …
Để phù hợp hơn với thực tế giảng dạy ở trường, tác giả chia chuyên đề này
thành 2 phần: phần cơ bản dạy ở khối 10 và phần nâng cao dạy ở khối 11. Các
ví dụ trình bày trong đề tài này chủ yếu dành cho các học sinh lớp 10 mới làm
quen với bài toán Quy hoạch động.
2) Tham khảo các tài liệu, giáo án, dự giờ các tiết dạy về chuyên đề Quy hoạch động
của đồng nghiệp.
Sau khi tham khảo các tài liệu, dự giờ một số tiết dạy của đồng nghiệp. Tác
giả nhận thấy phần lớn đều trình bày vấn đề từ dễ đến khó, từ ví dụ cụ thể đến
bài tập vận dụng. Cách trình bày này có nhiều ưu điểm, học sinh nắm bắt vấn
đề dễ dàng. Các ví dụ trong đề tài này được trình bày theo cách trên, bổ sung
thêm phần phân loại các bài toán.
3) Tham khảo các đề thi học sinh giỏi Tin học cấp tỉnh, cấp quốc gia, Olympic 30.4
...
Như đã trình bày ở trên, các bài toán Quy hoạch động chiếm đa số trong các
bài thi học sinh giỏi. Trong đề tài này có sử dụng một số bài tập Quy hoạch
động trích từ các đề thi.
4) Sưu tầm, xây dựng, phân loại các bài tập theo hướng Cấu trúc dữ liệu sử dụng.
Sau khi nghiên cứu cách giải các bài tập được tham khảo từ các đề thi, tài liệu,
website, tác giả tiến hành phân loại theo tiêu chí cấu trúc dữ liệu sử dụng.
5) Giảng dạy thử nghiệm chuyên đề Quy hoạch động cơ bản cho lớp 10 Tin. Theo
dõi khả năng tiếp thu của học sinh. Lấy ý kiến học sinh về những tích cực và hạn
chế của việc phân loại bài tập.
2
Chuyên đề Quy hoạch động cơ bản được dạy trong 5 (buổi) x 4 (tiết) = 20 (tiết), theo
phân bố như sau
Buổi
1
Tên bài
Nội dung
Làm quen với bài Nguyên lí tối ưu, đặc trưng các bài toán có
toán Quy hoạch động.
thể giải bằng thuật toán QHĐ, đặc trưng
chính của thuật toán QHĐ.
Sự giống và khác nhau căn bản giữa thuật
toán QHĐ và Đệ quy
Cách nhận biết được bài toán cụ thể có thể
giải được bằng QHĐ hay không.
2
Dạng 1: dùng biến Các bài tập dạng 1.
đơn để lưu trữ lời giải
cho bài toán QHĐ.
3
Dạng 2: dùng mảng 1 Các bài tập dạng 2.
chiều để lưu trữ lời
giải cho bài toán
QHĐ
4
Dạng 3: dùng mảng 2 Các bài toán dạng 3.
chiều để lưu trữ lời
giải cho bài toán
QHĐ
5
Ôn tập, kiểm tra
Để kiểm tra cuối chuyên đề.
5) Tổng kết, sửa chữa, hoàn thiện đề tài.
Sau khi giảng dạy chuyên đề Quy hoạch động cơ bản cho lớp 10 Tin, tác giả tiến
hành lấy ý kiến đồng nghiệp, học sinh để rút kinh nghiệm. Tiến hành sửa chữa và
hoàn thiện đề tài.
2. Nội dung của đề tài
Cấu trúc dữ liệu được sử dụng trong bài toán Quy hoạch động rất đa dạng. Từ các
cấu trúc dữ liệu cơ bản có sẵn như: biến, mảng 1 chiều, mảng 2 chiều, … cho đến
các kiểu dữ liệu nâng cao tự xây dựng như: stack, queue, tree, heap, … Vì giới hạn
thời gian, và để học sinh mới làm quen dễ dàng tiếp thu, đề tài chỉ giới hạn các bài
tập sử dụng các cấu trúc dữ liệu cơ bản. Các dạng nâng cao sẽ được tiếp tục bổ sung
trong thời gian tới.
3
2.1.
Dạng 1: Dùng biến đơn
Trong công thức truy hồi để tìm lời giải của bài toán chính, chỉ cần sử dụng một số
ít (hai, ba …) lời giải của bài toán con.
Ví dụ
Bài 1.
FIBO Dãy Fibonacci
Dãy fibonacci là dãy vô hạn các số nguyên dương 1, 1, 2, 3, 5, 8, …
Yêu cầu: Cho n. Hãy số hạng thứ n của dãy
Input: số nguyên dương n (n < 103).
Output: số hạng thứ n của dãy Fibonacci.
Input
Output
6
8
Giải
Gọi Fn là số hạng thứ n của dãy số. Để giải bài toán trên, thông thường ta phải tìm
được một công thức tính được Fn từ số n đầu vào. Các nhà toán học đã mất rất nhiều
thời gian để tìm ra công thức:
(1)
Việc tìm ra được những công thức tường minh như trên là rất khó, đòi hỏi nhiều
công sức, thời gian và phải có trình độ toán học cao cấp. Tuy nhiên, ta có thể lập
công thức tính Fn theo dạng truy hồi như sau:
fi =1 nếu i≤2
fi = fi – 1 + fi-2, nếu i≥3.
Công thức này mô tả quy luật của dãy số là “số sau bằng tổng hai số trước” mà một
học sinh tiểu học bình thường cũng có thể nghĩ ra được. Với công thức này, muốn
tìm số hạng thứ n, ta phải tìm được hai số hạng ngay trước n, muốn tìm hai số hạng
phía trước này, ta lại tiếp tục phải tìm các số hạng phía trước nữa ...
Sau đây là chương trình dùng 2 biến để lưu lại bài toán con fi1 và fi2
Chương trình
const
fin='fibo.inp'; fon='fibo.out';
procedure solve;
var
fi1,fi2,t:QWORD;
n,i:longint;
begin
readln(n);
4
Fi1:=1;//fi-1
fi2:=1;//fi-2
For i:=3 to n do
begin
T:=fi1;
fi1:=fi1+fi2;
fi2:=t;
end;
writeln(fi1);
end;
begin
assign(input,fin);reset(input);
assign(output,fon);rewrite(output);
solve;
close(input);close(output);
end.
Bài 2.
NKTICK Xếp hàng mua vé
Có N người sắp hàng mua vé dự buổi hoà nhạc. Ta đánh số họ từ 1 đến N theo thứ
tự đứng trong hàng. Mỗi người cần mua một vé, song người bán vé được phép bán
cho mỗi người tối đa hai vé. Vì thế, một số người có thể rời hàng và nhờ người đứng
trước mình mua hộ vé. Biết ti là thời gian cần thiết để người i mua xong vé cho mình.
Nếu người i+1 rời khỏi hàng và nhờ người i mua hộ vé thì thời gian để người thứ i
mua được vé cho cả hai người là ri.
5
Yêu cầu: Xác định xem những người nào cần rời khỏi hàng
và nhờ người đứng trước mua hộ vé để tổng thời gian phục
vụ bán vé là nhỏ nhất.
Dữ liệu
Dòng đầu tiên chứa số N (1 ≤ N ≤ 60000).
Dòng thứ 2 ghi N số nguyên dương t1, t2, ..., tN. (1 ≤
ti ≤ 30000)
Dòng thứ ba ghi N-1 số nguyên dương r1, r2, ..., rN-1.
(1 ≤ ri ≤ 30000)
Input
5
Output
18
25784
4 9 10 10
4
24
5784
50 50 50
Kết quả: In ra tổng thời gian phục vụ nhỏ nhất.
Giải
Gọi f[i] là tổng thời gian mua vé nhỏ nhất tính từ người 1..người i
Ta có công thức truy hồi: fi=min(fi-1+ti, fi-2+ri-1)
Chương trình sau dùng hai biến f1, f2 để lưu kết quả bài toán con.
Chương trình
const
fin='nktick.inp';fon='nktick.out';
maxn=60000;
var
n,i:longint;
t,r,f:array[1..maxn] of longint;
f1,f2,tam:longint;
function min(a,b:longint):longint;
var x:longint;
begin
x:=a;
if b
thì fi = 0
ngược lại fi=fi-1+fi-2
7
Ta áp dụng 2 biến fi1 và fi2 để lưu lời giải bài toán con như bài trên.
Bài 4.
LATGACH Lát gạch
Cho một hình chữ nhật kích thước 2xN (1≤N≤100). Hãy đếm số cách lát các viên
gạch nhỏ kích thước 1x2 và 2x1 vào hình trên sao cho không có phần nào của các
viên gạch nhỏ thừa ra ngoài, cũng không có vùng diện tích nào của hình chữ nhật
không được lát.
Input
Gồm nhiều test, dòng đầu ghi số lượng test T (T≤100).
T dòng sau mỗi dòng ghi một số N.
Example
Input
Output
3
1
Output: Ghi ra T dòng là số cách lát tương ứng.
1
2
Time: 1s
2
3
3
Hướng dẫn
Đầu tiên ta xét hình chữ nhật 2x1 thì có 1 cách xếp đó là xếp 1 viên gạch 2x1.
Xét hình chữ nhật 2x2 thì có 2 cách xếp đó là xếp 2 viên 1x2 hoặc 2 viên 2x1.
Xét hình chữ nhật 2xi có các trường hợp sau với f(i) là số cách xếp cho hình chữ
nhật 2xi.
2x(i-1)
2x1
f(i-1) cách xếp
2x(i-2)
1x2
f(i-2) cách xếp
1x2
=> f(i) = f(i-1) + f(i-2) với f(1) = 1 và f(2) = 2
=> f(N) là kết quả của bài toán
Công thức truy hồi trên chính là công thức của dãy Fibonacy.
8
Bài 5.
NKCABLE Nối mạng
Các học sinh khi đến thực tập trong phòng máy tính thường hay chơi trò chơi điện
tử trên mạng. Để ngăn ngừa, người trực phòng máy đã ngắt tất cả các máy tính ra
khỏi mạng và xếp chúng thành một dãy trên một cái bàn dài và gắn chặt máy xuống
mặt bàn rồi đánh số thứ tự các máy từ 1 đến N theo chiều từ trái sang phải. Các học
sinh tinh nghịch không chịu thua, họ đã quyết định tìm cách nối các máy trên bàn
bởi các đoạn dây nối sao cho mỗi máy được nối với ít nhất một máy khác. Để tiến
hành công việc này, họ đã đo khoảng cách giữa hai máy liên tiếp. Bạn hãy giúp các
học sinh này tìm cách nối mạng thoả mãn yêu cầu đặt ra sao cho tổng độ dài cáp nối
phải sử dụng là ít nhất.
Dữ liệu
Dòng đầu tiên chứa số lượng máy N (1 ≤ N ≤ 25000).
Dòng thứ i trong số N-1 dòng tiếp theo chứa các khoảng cách từ máy i đến
máy i+1 (i=1,2,...,N-1). Giả thiết rằng khoảng
cách từ máy 1 đến máy N không vượt quá 106.
Input
Output
Kết quả: Ghi ra độ dài của cáp nối cần sử dụng.
6
7
Giải thích:
2
Máy 1 với máy 2, mất 2 đơn vị (tức là số 2 đầu tiên)
2
Máy 3 với 4, mất 3 đơn vị (tức là số 3 trong input)
3
Máy 5 với 6, mất 2 đơn vị (tức là số 2 cuối cùng)
2
Tổng là 7.
2
Hướng dẫn
Fi là tổng độ dài cáp nối ít nhất để nối i máy đầu tiên. Ta có công thức truy hồi:
Fi =min(fi-1,fi-2)+ai-1
9
2.2.
Dạng 2: dùng mảng
Trong công thức truy hồi để tìm lời giải của bài toán chính, cần sử dụng tất cả lời
giải của bài toán con.
Ví dụ
Bài 1.
LIQ Dãy con tăng dài nhất
Cho dãy a1, a2, .., an có n phần tử. Dãy con của dãy a được tạo thành bằng các xóa
một số phần tử trong dãy a và vẫn giữ nguyên các vị trí còn lại.
Ví dụ cho dãy a: 2 4 6 1 7
Dãy 2 1 7 là một dãy con của a (xóa 4 6)
Dãy 2 4 1 là một dãy con của a (xóa 6 7)
Dãy 4 2 không phải là một dãy con của a.
Yêu cầu: Hãy tìm một dãy con tăng có nhiều phần tử nhất của dãy.
Dữ liệu vào: gồm 2 dòng:
Dòng đầu là số nguyên dương n (n ≤
103)
Dòng sau gồm N số, mỗi số là một số
nguyên ai của dãy (-104 ≤ai ≤ 104, 1≤ i
≤ n)
Input
Output
10
6
5 2 3 4 9 10 5 6 7 3
234567
Dữ liệu ra: gồm 2 dòng
Dòng đầu là số lượng phần tử của dãy con
Dòng sau là các số thuộc dãy con
Giải
Fi là dãy con của dãy a1, a2, …, ai thỏa đề bài (tăng, dài nhất) và kết thúc ở ai. Ví dụ:
i
1
2
3
4
5
6
7
8
9
10
A
5
2
3
4
9
1
5
6
7
3
F
1
1
2
3
4
5
4
5
6
2
Dãy con Fi được xây dựng bằng cách nối thêm phần tử ai vào một trong các dãy con
Fj trước đó (j =1 .. n – 1) và ai ≥ aj. Để dãy con này là dài nhất có thể thì
Fi = max(Fj, j= 1..i-1, aj< ai) + 1
Nhìn vào công thức truy hồi ta thấy để tính được Fi, ta cần lời giải của tất cả các bài
toán con f1, f2, …, fi – 1. Chương trình sau dùng mảng 1 chiều f[] để lưu lời giải của
các bài toán con này.
10
Chương trình
const
fin = 'test.inp'; fon = 'test.out';
maxn=10000;vc=maxlongint;
var
a,f,t:array[0..maxn] of longint;
n:longint;
procedure nhap;
var i:longint;
begin
read(n);
for i:=1 to n do read(a[i]);
end;
procedure xuli;
var i,jmax,j,d:longint;
kq:array[1..maxn] of longint;
begin
a[0]:=-vc;a[n+1]:=vc;
F[0]:=1;
For i:=1 to n+1 do
begin
Jmax:=0;
For j:=1 to i-1 do
If (a[j]f[jmax]) then
jmax:=j;
F[i]:=F[jmax]+1;
T[i]:=jmax;
end;
Writeln(f[n+1]-2);
//truy vet
i:=n+1;d:=0;//luu k?t qu? vao mang kq[]
11
repeat
i:=t[i];
inc(d);
kq[d]:=i;
until t[i]=0;
//do truy vet nguoc nen ta xuat nguoc mang kq[]
for i:=d downto 1 do write(a[kq[i]],' ');
end;
BEGIN
assign(input,fin);reset(input);
assign(output,fon);rewrite(output);
nhap;
xuli;
close(input);close(output);
END.
Bài 2.
NHAHANG Nhà hàng (HSG12_DNAI_2011_V2)
Tập đoàn kinh doanh nhà hàng Phát Đạt xem xét mở một loạt các nhà hàng dọc trên
đường cao tốc Bắc Nam. Có n vị trí dọc trên đường được đề nghị mở nhà hàng. Vị
trí thứ i cách đầu đường cao tốc là ai (km) và dựa vào các yếu tố mật độ dân, điều
kiện cơ sở, … xác định được khả năng dự kiến mở là bi.
Yêu cầu: Hãy xác định các vị trí mở nhà hàng sao cho tổng khả năng dự kiến mở là
tối đa. Nhưng hai nhà hàng được chọn gần nhau nhất hoặc giữa
nhà hàng đầu tiên được chọn và đầu đường cao tốc phải cách
Input Output
ít nhất là P (km)
6 30
3 23
Input
30 8
1
Dòng đầu là hai số n và P (2 ≤ n ≤ 50000)
70 5
3
N dòng tiếp theo, dòng thứ i trong n dòng là hai số ai và
90 6
5
bi (1 ≤ ai ≤107, 1≤ bi ≤105)
Output
Dòng đầu ghi hai số k và T, số lượng các nhà hàng được
mở và tổng khả năng dự kiến
K dòng tiếp theo, mỗi dòng là vị trí nhà hàng được mở
145 3
170 9
195 5
trên đường cao tốc.
Giải
12
Sắp xếp lại các vị trí theo tọa độ tăng dần.
Hàm mục tiêu: Fi = tổng khả năng dự kiến lớn nhất lớn nhất của dãy
Fi = max (Fj, j=1..i - 1: |ai – aj|>P) + bi
Chương trình
const
fin='NHAHANG.inp'; fon='NHAHANG.out';
vc=1000000000000;
nmax = 50000+5;
type Tpt = record
a,b:int64;
end;
var
c:array[-1..nmax] of Tpt;
f,t,kq:array[-1..nmax] of int64;
n,i,p:longint;
procedure xuli;
var
i,j,jmax,z,d:longint;
begin
c[0].a:=0;c[0].b:=0;c[n+1].a:=vc; c[n+1].b:=1;
f[-1]:=-vc;
for i:=1 to n+1 do
begin
jmax:=-1;
for j:=0 to i-1 do
if (c[i].a-c[j].a>=p) then
if (f[j]>f[jmax]) then jmax:=j;
if jmax=-1 then f[i]:=0
else f[i]:=f[jmax]+c[i].b;
t[i]:=jmax;
13
end;
{truy vet}
z:=t[n+1];
d:=0;
repeat
inc(d);
kq[d]:=z;
z:=t[z];
until z=0;
writeln(d,' ',f[n+1]-1);
//for i:=d downto 1 do writeln(kq[i],' ');
end;
begin
assign(input,fin);reset(input);
assign(output,fon);rewrite(output);
read(n,P);
for i:=1 to n do read(c[i].a,c[i].b);
xuli;
close(input);close(output);
end.
Bài tập vận dụng
Bài 3.
ACTIVITY Bố trí phòng họp
Có n cuộc họp đánh số từ 1 đến n đăng ký làm việc tại một phòng
hội thảo. Cuộc họp thứ t cần được bắt đầu ngay sau thời điểm si
và kết thúc tại thời điểm fi: Hỏi có thể bố trí phòng hội thảo phục
vụ được nhiều nhất bao nhiêu cuộc họp, sao cho khoảng thời gian
làm việc của hai cuộc họp bất kỳ là không giao nhau.
Dữ liệu:
Dòng đầu tiên chứa số nguyên dương n 106
Dòng thứ i trong số n dòng tiếp theo chứa hai số nguyên
si, fi 0 si fi 105
Input Output
5
3
79
3
68
5
13
1
06
37
Các số trên một dòng của Input file được ghi cách nhau ít nhất một dấu cách
Kết quả:
Dòng đầu tiên ghi số k là số các cuộc họp được chấp nhận phục vụ
14
k dòng tiếp theo liệt kê số hiệu các cuộc họp được chấp nhận theo thứ tự từ
cuộc họp đầu tiên tới cuộc họp cuối cùng , mỗi dòng ghi số hiệu một cuộc
họp.
Giải thích
Hướng dẫn
Sắp xếp các cuộc họp tăng dần theo thời điểm kết thúc (bi). Thế thì cuộc họp i sẽ bố
trí được sau cuộc họp j nếu và chỉ nếu j= w[i]) and (f[i,j] f[n-1,m] then
begin
write(n,' ');
m:=m-w[n]
end;
dec(n);
until n=0;
end;
begin
assign(input,fin);reset(input);
assign(output,fon);rewrite(output);
nhap;xuli;
close(input);close(output);
end.
Bài 2.
QBSTR Xâu con chung dài nhất
Xâu ký tự X được gọi là xâu con của xâu ký tự Y nếu ta có thể xoá đi một số ký tự
trong xâu Y để được xâu X.
Cho biết hai xâu ký tự A và B ít hơn 255 kí tự, hãy tìm xâu ký tự C có độ dài lớn
nhất và là con của cả A và B.
Input
Dòng 1: chứa xâu A
Dòng 2: chứa xâu B
Output:
Dòng một ghi độ dài xâu C tìm được.
Dòng hai ghi xâu C
Example
Input:
Output:
abc1def2ghi3
10
abcdefghi123
abcdefghi3
Giải
18