150 bài toán tin - Đại học sư phạm Hà Nội

ỏi các thầy sẽ sắp xếp lịch thi đấu cho các học sinh như thế nào 
để theo dự đoán, đoàn Việt Nam sẽ thu được số điểm nhiều nhất có thể. 
Dữ liệu: Nhập từ thiết bị nhập chuNn (input) 
• Dòng 1: Chứa hai số n, k (1 ≤ n ≤ 100; 1 ≤ k ≤ 1000) 
• Dòng 2: Chứa n2+n số, số thứ p là rp. 
• Các dòng tiếp, mỗi dòng chứa ba số nguyên dương i,j,p cho biết một điều dự đoán của các thầy: 
học sinh thứ i có thể làm được bài toán dạng j và đạt được số điểm là p(=c[i, j]). (1≤p≤100). 
Kết quả: Ghi ra thiết bị xuất chuNn (output) 
• Dòng 1: Ghi điểm đồng đội mà theo dự đoán đoàn Việt Nam có thể đạt 
• Tiếp theo là n2 + n dòng, dòng thứ i ghi số hiệu học sinh Việt Nam được giao làm bài thứ i. 
Chú thích : Chương trình chạy = FreePascal ! Time limit không quá 10 giây ! Không 
giới hạn bộ nhớ ! Thích dùng bao nhiêu thì dùng ! 
Ví dụ: 
input output 
3 4 
1 2 4 4 3 3 1 4 2 3 2 2 
1 1 2 
1 2 3 
1 4 6 
2 3 4 
2 1 3 
2 4 7 
3 2 1 
3 1 4 
4 1 2 
4 3 9 
4 2 8 
 65 
3 
4 
2 
1 
2 
4 
3 
2 
1 
4 
1 
3 
 157 
I hope and expect that you will have much success in IOI 2002 
 158 
146. CÂY KHUNG NHỎ NHẤT 
Cho đơn đồ thị vô hướng liên thông G = (V, E) gồm n đỉnh và m cạnh, các đỉnh được đánh số từ 1 
tới n và các cạnh được đánh số từ 1 tới m. Hãy tìm cây khung nhỏ nhất của đồ thị G. 
Dữ liệu: Vào từ file văn bản MST.INP 
• Dòng 1: Chứa hai số n, m (1 ≤ n ≤ 10000; 1 ≤ m ≤ 15000) 
• m dòng tiếp theo, dòng thứ i có dạng ba số nguyên u, v, c. Trong đó (u, v) là chỉ số hai đỉnh đầu 
mút của cạnh thứ i và c trọng số của cạnh đó (1 ≤ u, v ≤ n; 0 ≤ c ≤ 10000). 
Kết quả: Ghi ra file văn bản MST.OUT 
• Dòng 1: Ghi trọng số cây khung nhỏ nhất 
• n - 1 dòng tiếp theo, mỗi dòng ghi chỉ số một cạnh được chọn vào cây khung nhỏ nhất 
Ví dụ: 
MST.INP MST.OUT 
6 9 
1 2 1 
1 3 1 
2 4 1 
2 3 2 
2 5 1 
3 5 1 
3 6 1 
4 5 2 
5 6 2 
 5 
3 
7 
5 
2 
1 
Giới hạn thời gian: 1 giây 
 159 
147. MẠNG MÁY TÍNH 
Bản đồ mặt bằng của phòng máy tính là một hình chữ nhật nằm trong hệ trục toạ độ Decattes vuông 
góc có các đỉnh là A(0, 0), B(m, 0), C(m, n) và D(0, n). Tại các điểm toạ độ nguyên nằm trong hình 
chữ nhật ABCD có một máy tính (như vậy có tất cả (m + 1).(n+1) máy tính) . Một dây cáp mạng là 
một đoạn cáp nối độ dài 1 đơn vị, như vậy mỗi dây cáp mạng chỉ có thể nối được hai máy tính liền 
nhau trên cùng hàng hoặc cùng cột. Ban đầu đã có sẵn một số dây cáp mạng nối giữa một số cặp 
máy tính 
Hai máy u và v có thể truyền tin cho nhau nếu giữa chúng có đường truyền tin 
(u = x1, x2, x3, ..., xk = v) (Giữa máy xi và máy xi+1 có dây cáp mạng nối chúng) 
Hãy nối thêm một số ít nhất các dây cáp mạng sao cho hai máy bất kỳ trong phòng máy có thể 
truyền tin được cho nhau. 
Dữ liệu: Vào từ file văn bản NET.INP 
• Dòng 1: Chứa hai số m, n (1 ≤ m, n ≤ 100); 
• Các dòng tiếp theo, mỗi dòng chứa thông tin về một đoạn cáp đã có sẵn: gồm 4 số x1, y1, x2, y2 
thể hiệu cho cáp mạng nối hai máy ở toạ độ (x1, y1) và (x2, y2). (|x1 - x2| + |y1-y2| = 1). 
Kết quả: Ghi ra file văn bản NET.OUT 
• Dòng 1: Ghi số cáp mạng cần nối thêm (c) 
• c dòng tiếp theo, mỗi dòng ghi 4 số u1, v1, u2, v2 cho biết cần thêm cáp nối giữa hai máy ở toạ 
độ (u1, v1) và (u2, v2) 
Các số trên một dòng của Input/Output file cách nhau ít nhất một dấu cách. 
Ví dụ: 
NET.INP NET.OUT 
2 3 
0 0 0 1 
1 0 2 0 
1 0 1 1 
2 0 2 1 
0 1 1 1 
1 1 2 1 
1 2 2 2 
0 3 1 3 
4 
0 2 1 2 
1 2 1 3 
1 1 1 2 
1 3 2 3 
0 1 2
1
2
3
x
y
Giới hạn thời gian: 1 giây 
 160 
148. DẴY ĐƠN ĐIỆU TĂNG DÀI NHẤT 
Cho dãy số nguyên dương a = (a1, a2, ..., an) (1 ≤ n ≤ 10000; 1 ≤ ai ≤ 10000) 
Hãy tìm dãy chỉ số dài nhất i1, i2, ..., ik thoả mãn: 
• 1 ≤ i1 < i2 < ... < ik ≤ n 
• ai1 < ai2 < ... < aik 
Dữ liệu: Vào từ file văn bản INCSEQ.INP 
• Dòng 1: Chứa số n 
• Dòng 2: Chứa n số a1, a2, ..., an 
Kết quả: Ghi ra file văn bản INCSEQ.OUT 
• Dòng 1: Ghi số k 
• Dòng 2: Ghi k số i1, i2, ..., ik 
Các số trên một dòng của Input/Output file cách nhau ít nhất một dấu cách 
Ví dụ: 
INCSEQ.INP INCSEQ.OUT 
8 
1 2 8 9 5 6 7 9 
 6 
1 2 5 6 7 8 
Giới hạn thời gian: 1 giây 
 161 
149. LUỒNG CỰC ĐẠI TRÊN MẠNG 
Cho một mạng G = (V, E) là đồ thị có hướng với n điểm và m cung, 1 là điểm phát và n là điểm thu. 
Từ 1 chỉ có cung đi ra và từ n chỉ có cung đi vào. Mỗi cung (u, v) của mạng được gán một số 
nguyên dương c(u, v) là khả năng thông qua của cung đó. 
Một luồng cực đại trên mạng là một cách gán cho mỗi cung (u, v) một số nguyên f(u, v) thoả mãn: 
i) f(u, v) ≤ c(u, v) (∀(u, v)∈E) 
ii) ∑∑
∈∈
=
E)w,v(E)v,u(
)w,v(f)v,u(f (∀v∈V) 
iii)Giá trị luồng = ∑∑
∈∈
=
E)n,v(E)u,1(
)n,v(f)u,1(f là lớn nhất có thể. 
Hãy tìm luồng cực đại trên mạng G 
Dữ liệu: Vào từ file văn bản MAXFLOW.INP 
• Dòng 1: Chứa số đỉnh n và số cung m của đồ thị G (2 ≤ n ≤ 100) 
• m dòng tiếp theo, mỗi dòng chứa ba số u, v, c(u, v) thể hiện cho một cung (u, v) và khả năng 
thông qua của cung đó là c(u, v) 
Kết quả: Ghi ra file văn bản MAXFLOW.OUT 
• Dòng 1: Ghi giá trị luồng tìm được 
• Các dòng tiếp theo, mỗi dòng chứa ba số x, y, f(x, y) thể hiện (x, y) là một cung và luồng gán 
cho cung (x, y) là f(x, y) (Những cung nào không có luồng (f(x, y) = 0) không cần phải ghi vào 
Output file). 
Các số trên một dòng của Input / Output file ghi cách nhau ít nhất một dấu cách. 
Ví dụ: 
1
2
3
4
5
6
1
5
5
6
6
6
3
3
MAXFLOW.INP 
6 8 
1 2 5 
1 3 5 
2 4 6 
2 5 3 
3 4 3 
3 5 1 
4 6 6 
5 6 6 
MAXFLOW.OUT 
9 
1 2 5 
1 3 4 
2 4 3 
2 5 2 
3 4 3 
3 5 1 
4 6 6 
5 6 3 
 162 
150. BỘ GHÉP CỰC ĐẠI 
Cho đồ thị hai phía G = (X∪Y, E); Các đỉnh của X ký hiệu là x1, x2, ..., xm, các đỉnh của Y ký hiệu 
là y1, y2, ..., yn. 
Một bộ ghép trên G là một tập các cạnh ∈E đôi một không có đỉnh chung. 
Yêu cầu: Hãy tìm bộ ghép cực đại (có nhiều cạnh nhất) trên G. 
Dữ liệu: Vào từ file văn bản MATCH.INP 
• Dòng 1: Chứa hai số m, n (1 ≤ m, n ≤ 300) 
• Các dòng tiếp, mỗi dòng chứa hai số nguyên dương i, j cho biết thông tin về một cạnh (xi, 
yj)∈E. 
Kết quả: Ghi ra file văn bản MATCH.OUT 
• Dòng 1: Ghi số cạnh trong bộ ghép cực đại tìm được (K). 
• K dòng tiếp theo, mỗi dòng ghi thông tin về một cạnh được chọn vào bộ ghép cực đại: Gồm 2 số 
u, v thể hiện cho cạnh nối (xu, yv). 
Các số trên một dòng của Input / Output file cách nhau ít nhất một dấu cách. 
Ví dụ: 
1
2
3
4
1
2
3
4
5
X Y
MATCH.INP 
4 5 
1 1 
1 4 
2 1 
2 2 
2 4 
3 2 
3 3 
4 2 
4 3 
MATCH.OUT 
4 
1 1 
2 4 
3 3 
4 2 
 163 
151. BỘ GHÉP ĐẦY ĐỦ TRỌNG SỐ CỰC TIỂU 
Cho đồ thị hai phía G = (X∪Y, E); Các đỉnh của X ký hiệu là x1, x2, ..., xn, các đỉnh của Y ký hiệu 
là y1, y2, ..., yn. Mỗi cạnh của G được gán một trọng số không âm. 
Một bộ ghép đầy đủ trên G là một tập n cạnh ∈E đôi một không có đỉnh chung. Trọng số của bộ 
ghép là tổng trọng số các cạnh nằm trong bộ ghép. 
Yêu cầu: Hãy tìm bộ ghép đầy đủ có trọng số cực tiểu của G 
Dữ liệu: Vào từ file văn bản MATCH.INP 
• Dòng 1: Chứa số n (1 ≤ n ≤ 200) 
• Các dòng tiếp theo, mỗi dòng chứa 3 số nguyên i, j, c cho biết có một cạnh (xi, yj) và trọng số 
cạnh đó là c (0 ≤ c ≤ 200). 
Kết quả: Ghi ra file văn bản MATCH.OUT 
• Dòng 1: Ghi trọng số bộ ghép tìm được 
• n dòng tiếp, mỗi dòng ghi hai số (u, v) tượng trưng cho một cạnh (xu, yv) được chọn vào bộ 
ghép. 
Các số trên một dòng của Input / Output file cách nhau ít nhất một dấu cách. 
Ràng buộc: Luôn tồn tại ít nhất một bộ ghép đầy đủ trên G. 
Ví dụ: 
MATCH.INP 
4 
1 1 0 
1 2 0 
2 1 0 
2 4 2 
3 2 1 
3 3 0 
4 3 0 
4 4 9 
MATCH.OUT 
3 
1 1 
2 4 
3 2 
4 3 
 164 
152. TUYỂN NHÂN CÔNG 
Có n công việc cần thực hiện và r loại thợ. Thợ loại i có thể không làm được việc j hoặc làm được 
với chi phí là cij. Một phép phân công là một cách chọn ra n thợ và giao cho mỗi thợ làm đúng một 
việc sao cho có thể thực hiện tất cả n công việc. 
Giả sử đã có sẵn m thợ hãy tìm cách tuyển thêm một số ít nhất thợ để có thể thực hiện phép phân 
công. Nếu có nhiều cách tuyển thoả mãn yêu cầu trên thì chỉ ra cách tuyển có tổng chi phí thực 
hiện các công việc (trên phép phân công tối ưu) là cực tiểu. 
Dữ liệu: Vào từ file văn bản ASSIGN.INP 
• Dòng 1: Chứa ba số m, n, r (1 ≤ m, n, r ≤ 300) 
• Dòng 2: Chứa m số, số thứ k là loại của thợ thứ k trong m thợ đã có 
• Các dòng tiếp theo, mỗi dòng ghi ba số i, j, cịj cho biết loại thợ i có thể làm được việc j với chi 
phí cij (0 ≤ cij ≤ 10000) 
Các số trên một dòng của Input file cách nhau ít nhất một dấu cách 
Kết quả: Ghi ra file văn bản ASSIGN.OUT 
• Dòng 1: Ghi số thợ cần thêm và chi phí phép phân công tối ưu 
• n dòng tiếp theo, dòng thứ i ghi loại thợ được giao thực hiện việc i 
Ràng buộc: Mỗi việc có ít nhất một loại thợ có thể thực hiện 
Ví dụ: 
ASSIGN.INP ASSIGN.OUT ASSIGN.INP ASSIGN.OUT 
10 4 6 
1 3 5 5 5 5 5 5 5 5 
1 1 10 
1 2 10 
1 3 10 
3 1 10 
3 2 10 
3 3 10 
2 2 9 
2 1 8 
4 2 6 
4 3 5 
6 4 0 
2 25 
1 
3 
4 
6 
 1 2 3 
1 
1 1 10 
1 2 30 
3 1 1 
3 2 25 
2 2 40 
1 31 
3 
1 
 165 
153. DÀN ĐÈN 
Cho một bảng vuông kích thước mxn được chia thành lưới ô vuông đơn vị, tại mỗi ô của bảng có 
một trong các ký hiệu: 
• ".": Ô trống 
• "+": Ô có chứa một đèn chưa bật sáng 
• "*": Ô có chứa một đèn đã bật sáng 
Hai đèn đã bật sáng bất kỳ không nằm cùng hàng hoặc cùng cột. 
Yêu cầu: Hãy bật sáng thêm một số nhiều nhất các đèn sao cho: số đèn sáng trên mỗi hàng cũng 
như trên mỗi cột của bảng tối đa là 1. 
Dữ liệu: Vào từ file văn bản GRID.INP 
• Dòng 1: Chứa hai số m, n (1 ≤ m , n ≤ 200) cách nhau ít nhất một dấu cách 
• m dòng tiếp theo, dòng thứ i chứa n ký tự liên tiếp, ký tự thứ j là ký hiệu ô (i, j) của bảng 
Kết quả: Ghi ra file văn bản GRID.OUT 
• Dòng 1: Ghi số đèn có thể bật thêm 
• m dòng tiếp theo, dòng thứ i ghi n ký tự liên tiếp, ký tự thứ j là ký hiệu ô (i, j) của bảng sau khi 
đã bật sáng thêm các đèn 
Ví dụ: 
GRID.INP GRID.OUT 
4 5 
+..*. 
++.+. 
.++.. 
.++.. 
 3 
+..*. 
*+.+. 
.*+.. 
.+*..