Bài Tập: Hội nghị bàn tròn, domino, kiểm tra đường và Mã đi tuần
Bài tập 1: Hội nghị bàn tròn Tổng thư ký Đại hội đồng Liên hợp quốc triệu tập một cuộc họp có N nhà ngoại giao của N tổ chức tham gia. Các đại diện ngoại giao được bố trí ngồi quanh một bàn tròn. Giữa một số tổ chức có ...
Bài tập 1: Hội nghị bàn tròn
Tổng thư ký Đại hội đồng Liên hợp quốc triệu tập một cuộc họp có N nhà ngoại giao của N tổ chức tham gia. Các đại diện ngoại giao được bố trí ngồi quanh một bàn tròn. Giữa một số tổ chức có quan hệ căng thẳng, vì vậy không thể xếp họ ngồi cạnh nhau được. Thông tin về quan hệ giữa các tổ chức được cho dưới dạng cặp số nguyên i, j nếu giữa 2 tổ chức này có quan hệ căng thẳng.
Hãy lập trình giúp Tổng thư ký Liên hợp quốc bố trí chỗ ngồi quanh bàn họp. Các tổ chức được đánh số từ 1 tới N, 0 < N <= 500.
Dữ liệu vào:
từ file CONF.INP, dòng đầu tiên chứa số nguyên N, các dòng sau, mỗi dòng một cặp số i, j cho biết các đại diện i và j không ngồi cạnh nhau được. Kết thúc là một dòng chứa 2 số 0.
Kết quả:
đưa ra file CONF.OUT. Nếu không có cách bố trí thỏa mãn yêu cầu thì đưa ra thông báo KHONG CO, trong trường hợp ngược lại – đưa ra dãy N số nguyên xác định vị trí ai ngồi cạnh ai quanh bàn tròn.
Ví dụ:
CONF.INP CONF.OUT
11 1 9 7 4 11 5 8 2 10 3 6
1 4
1 7
5 7
10 7
10 8
10 9
3 4
0 0
Bài tập 2: Domino
Cho trước N con cờ domino, hãy viết chương trình cho biết rằng có cách sắp N con cờ đó theo đúng luật domino sao cho các con cờ hình thành vòng tròn hay không, nếu có hãy chỉ ra một cách sắp.
Dữ liệu vào:
file DOMINO.INP
Dòng đầu chứa số N
N dòng tiếp theo, mỗi dòng chứa 2 số từ 0 đến 6 mang giá trị đại diện cho 2 đầu của domino.
Dữ liệu ra:
file DOMINO.OUT
Dòng đầu chứa số 1 hoặc 0 tương ứng với sắp được quân domino thành vòng tròn và không sắp được.
Nếu dòng đầu là 1 (tương ứng với sắp được) thì dòng thứ hai liệt kê ra N chỉ số của N con cờ domino theo thứ tự để sắp thành vòng tròn. Nếu dòng đầu là 0 thì không có dòng thứ hai.
Ví dụ:
DOMINO.INP
4
5 3
5 6
2 3
6 2
DOMINO.OUT
1
1 3 4 2
Bài tập 3: Kiểm tra đường
Một trạm quảng đường giao thông phải chịu trách nhiêm về tình trạng của một mạng lưới giao thông nối giữa các điểm dân cư. Hàng tháng, họ phải cử một đội đi kiểm tra một vòng qua khắp mạng lưới để xem xét tình trạng hiện thời của các đường giao thông nhằm báo sửa chữa kịp thời nếu có nhu cầu. Hãy viết chương trình nhập vào mạng lưới giao thông và giúp trạm quyết định lộ trình của đội kiểm tra sao cho có thể thăm tất cả các con đường mà tổng chiều dài đoạn đường đi qua là nhỏ nhất.
Bài tập 4: Mã đi tuần
Hãy cài đặt chương trình xác định lộ trình của con mã trên bàn cờ 8x8 ô bắt đầu từ ô (i, j) đi qua tất cả các ô của bàn cờ vàmỗi ô chỉ 1 lần duy nhất.
Mở rộng với trường hợp bàn cờ kích thước NxN.
Bài tập 5: Hội nghị bàn tròn
Có 12 người ngồi chung 1 bàn tiệc tròn. Mỗi người có ít nhất 6 người quen. Hãy chỉ ra cách sắp xếp sao cho mỗi người đều ngồi cạnh người mình quen . Tổng quát, hãy sắp N người ngồi chung quanh bàn tròn sao cho mỗi người đều ngồi cạnh người mình quen. Biết mỗi người có ít nhất (N + 1)/2 người quen.
