Đề thi đầu vào MDC
Vệ tinh
Tập đoàn viễn thông đa quốc gia UltraCom hiện sở hữu một hệ thống truyền tin
gồm N trung tâm truyền nhận dữ liệu (gọi tắt là trung tâm) nằm rải rác khắp địa
cầu (các trung tâm này được đánh số từ 1 đến N) và M vệ tinh (gọi tắt là vệ tinh)
cũng được phân bố đều khắp trên bầu trời quanh địa cầu (các vệ tinh này được
đánh số từ 1 đến M).
Mỗi trung tâm i đều có thể thiết lập kết nối trực tiếp (để khai thác) với mỗi vệ
tinh j với chi phí xác định Cij nào đó.
Hai trung tâm được xem là thông băng với nhau nếu chúng cùng được kết nối với
một vệ tinh hoặc chúng cùng thông băng với một số trung tâm khác. Toàn hệ
thống của UltraCom đương nhiên vốn là thông băng hoàn toàn, tức là bất kỳ hai
trung tâm nào cũng đều thông băng với nhau.
Một sự cố bí ẩn vừa diễn ra trong thời gian gần đây đã khiến một số kết nối bị hư
hỏng hoàn toàn và hệ thống của UltraCom bị rơi vào tình trạng không thông băng
hoàn toàn được, đặt ra nhiệm vụ cấp bách cho UltraCom phải khẩn trương khắc
phục hậu quả này.
Sau sự cố, bộ phận phụ trách kỹ thuật của UltraCom đã tiến hành khảo sát toàn
hệ thống và nhận thấy rằng:
1. Mỗi trung tâm đều vẫn còn đang kết nối bình thường với một số các vệ tinh
đồng thời mỗi vệ tinh đều còn đang được kết nối bởi một số trung tâm nào đó.
2. Một số kết nối vừa bị hỏng sẽ không thuộc diện xem xét khắc phục nữa, do chi
phí quá lớn.
3. Hoàn toàn có phương án khả thi để khắc phục hệ thống thông băng hoàn toàn.
để tiết kiệm chi phí tại thời điểm nhạy cảm của nền kinh tế toàn cầu, ban lãnh đạo
tập đoàn quyết định sẽ chỉ thiết lập lại một số kết nối đã bị hư hỏng sao cho tổng
chi phí khắc phục là nhỏ nhất có thể.
Yêu cầu: Xác lập phương án cụ thể và tổng chi phí nhỏ nhất để UltraCom khắc
phục sự cố
Dữ liệu vào: Cho trong file văn bản REPAIR.INP, gồm:
• Dòng đầu ghi tuần tự 2 số nguyên dương N, M (2 ≤ M, N ≤ 1000)
• Dòng thứ i trong N dòng tiếp theo ghi M số nguyên Ci1, …, CiM (-1 ≤ Cij ≤
10000; i = 1, …, N; j = 1, 2,…, M) với ý nghĩa: Cij là chi phí để kết nối trung tâm i
với vệ tinh j cùng sự lưu ý đặc biệt: Cij = 0 nếu trung tâm i vẫn đang kết nối bình
thường được với vệ tinh j, Cij = -1 nếu bỏ qua việc tái lập sự kết nối giữa trung
tâm i với vệ tinh j (do chi phí quá lớn).
• Tất cảc các số nguyên trên cùng dòng đều cách nhau bởi khoảng trống. Dữ liệu
luôn đảm bảo tính đúng đắn để có lời giải, tức là luôn có phương án để UltraCom
khắc phục sự cố.
Kết quả: Ghi ra file văn bản REPAIR.OUT các thông tin sau:
• Dòng đầu ghi một số nguyên, là tổng chi phí nhỏ nhất tìm được. Thông tin này
chiếm 50% số điểm của test.
• Dòng thứ 2 ghi số nguyên dương K, với K là số kết nối cần khắc phục. Thông tin
này chiếm 25% số điểm của test.
• K dòng tiếp theo, mỗi dòng ghi hai số nguyên c, s (cách nhau bởi khoảng trống)
cho biết cần tái lập kết nối giữa trung tâm c với vệ tinh s. Nếu có nhiều kết quả
(phương án), chỉ cần chỉ ra một trong chúng. Thông tin trên K dòng này chiểm
25% số điểm của test.
VD1:
REPAIR.INP
4 3
0 -1 5
0 4 4
-1 0 -1
1 2 0
REPAIR.OUT
3
2
4 1
4 2
REPAIR.INP
4 4
0 -1 5 3
-1 4 5 -1
-1 0 -1 0
6 7 0 -1
Ràng buộc:
• 60% số test ứng với 60% số điểm của bài ứng với N, M ≤ 200.
• Giới hạn thời gian cho mỗi test: 01 giây.
Hướng dẫn: Sử dụng thuật toán tham lam, xác định tập lớn nhất các trung tâm
đang thông băng (S) , sắp xếp các kết nối theo thứ tự chi phí từ nhỏ đến lớn, sau
đó thực hiện kết nối mới (C) vào tập với điều kiện trung tâm X chưa nằm trong
tập (S).
Cây và Rừng
Một cấu trúc dạng cây được tổ chức trong CSDL quan hệ dưới dạng các dòng của
bảng như sau.
Mã node
Mã node cha
Tên node
1
2
3
4
0
1
1
2
4
Gốc
Node A
Node B
Node C
Node D
5
….
Trong đó, node gốc trong cây sẽ có mã node cha là 0. Có thể có nhiều cây khác
nhau trong rừng. Số dòng tối đa có thể lên đến 1.000.000
Yêu cầu:
1.Đọc từ tệp tin tree.txt các node của cây vào bộ nhớ, tệp tin gồm nhiều dòng, mỗi
dòng là một node chứa 3 trường thông tin: Mã của node, mã node cha, tên của
node.
2. Nhập vào một cặp mã node X và Y, trả lời xem X có phải là node cha (ông, cụ…)
của Y hay không. Hiển thị ra màn hình mối quan hệ của X và Y (ví dụ:
X=>A=>B=>Y)
3. Nhập vào một mã node X, in ra màn hình tất cả các node con, cháu, chắt….của X
(bao gồm mã node, tên node, mỗi cái trên một dòng).
4. Hiện thời gian thực hiện thuật toán cho ý 2 và 3, tính theo ms (milisecond)
3 trang
16120
Free
Bạn đang xem tài liệu "Đề thi đầu vào MDC", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- de_thi_dau_vao_mdc.pdf
