TÌM BIỂU THỨC (MS0030)CHO XÂU SỐ N= ‘123456789’ VÀ SỐ NGUYÊN MYÊU CẦU

Bài 1: Tìm biểu thức (MS0030)Cho xâu số N= ‘123456789’ và số nguyên MYêu cầu: Hãy tìm cách chèn vào N các dấu cộng hoặc trừ để thu được biểu thức có giá trị bằng M(nếu có thể)Dữ liệu vào: Đọc từ file văn bản BTHUC.INP có nội dung duy nhất là số nguyên MDữ liệu ra: Ghi vào file văn bản BTHUC.OUT. Ghi tất cả các biểu thức thu được nếu có, nếu khôngthu được biểu thức nào có giá trị bằng M thì ghi là “KHONG CO”Ví dụ:BTHUC.INP BTHUC.OUT500 1-234-56+7891-2+345+67+89-12+34+567-891000 KHONG CO*Bài 2: Làm đường đi (MS0031)Trong một tỉnh nọ có N xã được sắp xếp từ 1 đến N. Người ta muốn làm một con đường đi từ xã 1 đếnxã N, giả sử đường đi từ xã 1 đến xã N có thể xây dựng qua một số xã trung gian được đánh số từ 2đến N-1. Người ta lập được bảng chi phí làm đường nối bất kì 2 xã (Nếu giữa hai xã này có thể xâydựng được đường) trong đó chi phí làm đường đi từ xã i đến xã j (nếu có thể) là A

ij

. Ví dụ dưới đây làbảng chi phí làm các đoạn đường nối giữa hai xã bất kì trong một tỉnh có N=5 xã2 3 4 51 10 20 100 _2 0 30 _ _3 30 0 25 604 _ 25 0 5Trong bảng trên chi phí làm đường nối từ xã 1 đến xã 2 là 10, từ xã 1 đến xã 3 là 20, từ xã 1 đến xã 4là 100…. Dấu “-” trong bảng có nghĩa là giữa hai xã i và j không thể xây dựng con đường nàoYêu cầu: hãy lập trình tìm chi phí nhỏ nhất và hành trình của con đường đi từ xã 1 đến xã N. Lưu ýhành trình khồn bắt buộc phải đi qua tất cả các xã.Dữ liệu vào: Đọc từ file văn bản DUONGDI.INP có nội dung:+ Dòng đầu tiên ghi số N+ Trong N-1 dòng tiếp theo mỗi dòng ghi N-1 phần tử là các số A

ij

hoặc dấu “-” thể hiện chi phí làmđoạn đường nối giữa hai xã i và j hoặc không thể xây dựng đường nối từ hai xã này(1≤i≤N-1;2≤j≤N) các số và dấu “-” cách nhau ít nhất là một kí tự trắng(2≤N≤100; 0≤A

ij

≤32767)Dữ liệu ra: Ghi vào file văn bản DUONGDI.OUT gồm+ Dòng thứ nhất ghi số K là chi phí nhỏ nhất để xây dựng con đường từ xã 1 đến xã N+ Dòng thứ hai ghi hành trình của đường đi từ xã 1 đến xã N có chi phí nhỏ nhấtDUONGDI.INP DUONGDI.OUT5051 3 4 510 20 100 _0 30 _ _30 0 25 60_ 25 0 5*Bài 3: Nối mạng (MS0032)Cho N máy tính được đánh số từ 1 đến N. Chi phí nối mạng giữa máy i và máy j là C

ij

. Ban đầu đã cósẵn K cặp máy đã nối mạngYêu cầu: Tìm cách nối thêm dây cáp sao cho các máy tính trong mạng là liên thông và chi phí là nhỏnhất (chú ý có thể sử dụng lại hệ thống mạng cũ)Dữ liệu vào: Đọc từ file văn bản NOIMANG.INP có nội dung+ Dòng đầu gồm 2 số N và K+ K dòng tiếp theo mỗi dòng là 3 số i, j, C

ij

là thông tin về cặp máy đã nối trước đó+ Các dòng còn lại mỗi dòng là 3 số i, j, C

ij

là thông tin về cặp máy có thể nói với nhau trong mạngTrên cùng một dòng các số cách nhau một dấu cáchGiới hạn: 2≤N≤100Dữ liệu ra: Ghi vào file văn bản NOIMANG.OUT gồm+ Dòng 1 là chi phí nhỏ nhất (không kể phần sử dụng lại mạng cũ)

+ Từ dòng 2 trở đi mỗi dòng là một cặp cạnh được nối

NOIMANG.INP NOIMANG.OUT NOIMANG.INP NOIMANG.OUT218 0376 22 12 31 3 171 2 51 3 73 12 3 181 2 334 64 51 4 102 4 203 5 65 36 43 6 47 53 4 164 6 88 63 5 44 5 95 7 26 7 75 6 146 8 5TRƯỜNG THPT CHUYÊN HUỲNH MẪN ĐẠT – KIÊN GIANG