Các thuật toán (Phần 2)

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
Giới hạn thời gian: 1 giây
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
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) ("vÎV)
iii)Giá trị luồng = 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ụ:
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
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ụ:
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
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
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
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
+..*.
*+.+.
.*+..
.+*..
154. CO VÒNGTHEM
Cho N số nguyên A1, A2, ..., AN. Các số được bố trí theo thứ tự theo chiều kim đồng hồ trên một vòng tròn. Cho hai phép biến đổi:
R(i) - Phép co phải: Thay Ai bằng Ai - Ai+1 và xoá Ai+1
L(i) - Phép co trái: Thay Ai bằng Ai - Ai-1 và xoá Ai-1
Lưu ý: Ai-1 và Ai + 1 ở trên được hiểu là các phần tử đứng liền trước, liền sau Ai trong vòng tròn theo chiều kim đồng hồ (1 £ i £ N). VD R(N) là phép thay hai số AN và A1 bằng AN - A1
Sau mỗi bước co, các phần tử được đánh số lại theo chiều kim đồng hồ bắt đầu từ phần tử có chỉ số nhỏ nhất còn lại được đánh số 1. Sau N - 1 lần co trên, vòng tròn chỉ còn một số nguyên R. Hãy xác định có tồn tại cách sử dụng thứ tự hai phép co trên để từ vòng tròn ban đầu chỉ còn lại số R hay không. Nếu có thì chỉ ra một cách biến đổi.
Dữ liệu vào đặt trong file văn bản PRESS.INP
Dòng đầu: 2 số nguyên N, R theo đúng thứ tự cách nhau 1 dấu trống ( 1 £ N £ 100), (-10000 £ R £ 10000).
Dòng thứ i trong số N dòng tiếp theo: chứa số nguyên Ai ( -120 £ Ai £ 120).
Kết quả ra đặt trong file văn bản PRESS.OUT
Chứa thông báo NO SOLUTION nếu vô nghiệm, trong trường hợp có nghiệm thì mỗi dòng xác định một bước biến đổi: Đầu dònglà một trong hai ký tự {L, R} tiếp đó là dấu trống, sau đó đến vị trí i mà tại bước đó ta thực hiện phép co phải R(i) hay co trái L(i).
Ví dụ:
PRESS.INP
PRESS.OUT
5 6
1
6
8
12
5
R 4
L 2
R 3
R 1
1
6
8
12
5
1
6
8
7
5
8
7
8
2
6
155.CẦU TÀUTHEM
Một cảng biển có M cầu tàu. Tại một thời điểm, mỗi cầu tàu chỉ có thể tiếp nhận không quá 1 tàu. Theo kế hoạch, trong khoảng từ thời điểm P tới hết thời điểm Q giờ (0 £ P< Q £ 72) có N tàu sẽ cập bến. Tàu thứ i có lịch trình đậu ở cảng bắt đầu từ đầu thời điểm Ai đến hết thời điểm Bi. Tàu đã vào cầu tàu nào thì sẽ đậu ở đó trong suốt thời gian nằm cảng.
Hãy lập chương trình kiểm tra xem cần ít nhất bao nhiêu cầu cảng trống để có thể phục vụ các tàu theo đúng lịch của mình. Nếu số cầu tàu không đủ thì có thể đề xuất thay đổi thời điểm Ai của một số tàu (giữ nguyên thời gian cần đậu và thời điểm rời cảng không muộn hơn Q) để đảm bảo phục vụ hết các tàu. Tuy vậy, đối với các tàu này cần phải trả thêm phụ phí bao gồm 2 phần, phần cố định và phần tỷ lệ với lượng thời gian chênh lệch giữa hai thời điểm đầu cũ và mới. Phần cố định là rất lớn so với phần tỷ lệ thời gian.
Dữ liệu vào đặt trong file văn bản SEAPORT.INP
Dòng đầu: ghi 4 số nguyên P, Q, M, N (0 < N £ 100)
N dòng sau: Mỗi dòng ghi 2 số nguyên Ai, Bi
Các số trên 1 dòng ghi cách nhau 1 dấu trống.
Kết quả: Ghi ra file văn bản SEAPORT.OUT
Dòng đầu tiên: Số cầu tàu tối thiểu cần có để phục vụ các tàu theo đúng lịch trình.
Dòng thứ 2 ghi số 0 nếu không cần điều chỉnh lịch, chứa số -1 nếu không thể điều chỉnh lịch để có thể phục vụ tất cả các tàu và chứa số K > 0, nếu cần và có thể điều chỉnh được các lịch trong đó K là số tàu cần điều chỉnh lịch.
K dòng tiếp theo: mỗi dòng 3 số nguyên i, Ai, và Ai mới ứng với một tàu cần điều chỉnh lịch. Các số trên 1 dòng cách nhau ít nhất 1 dấu cách.
Ví dụ:
SEAPORT.INP
SEAPORT.OUT
0 12 3 5
8 12
5 9
2 6
4 8
1 7
4
1
2 5 7