Quay lui sinh hoán vị không có hai số chẵn liền kề
Hệ thống lên lịch thực thi song song của AI Empire Academy cần lập lịch chạy N tác vụ được đánh số từ 1 đến N (1 ≤ N ≤ 9).
Tiến độ của tôi ở bài này
Điểm được lưu vào tài khoản sau khi chấm bài.
Đang tải điểm của bạn…
Kiến thức và chủ đề
Kiến thức tiên quyết: recursion, arrays, loops.
Nội dung đề bài
Mục tiêu kiến thức
- Hiểu sâu bản chất thuật toán Đệ quy Quay lui (Backtracking) và cây tìm kiếm trạng thái.
- Quản lý mảng đánh dấu
used[x]để kiểm soát các phần tử đã được chọn. - Áp dụng kỹ thuật Tỉa nhánh (Branch Pruning) sớm ngay khi điều kiện tính chẵn lẻ bị vi phạm.
- Sinh các cấu hình hoán vị theo đúng thứ tự từ điển (Lexicographical Order).
Mô tả bài toán
Hệ thống lên lịch thực thi song song của AI Empire Academy cần lập lịch chạy N tác vụ được đánh số từ 1 đến N (1 ≤ N ≤ 9).
Mỗi lịch trình là một hoán vị của tập hợp {1, 2, …, N}. Do ràng buộc chống nghẽn đường truyền bộ nhớ giữa các tác vụ chẵn, lịch trình phải thỏa mãn điều kiện an toàn: Không được có hai số chẵn nào đứng liền kề nhau (nghĩa là nếu vị trí i là số chẵn thì vị trí i+1 bắt buộc phải là số lẻ).
Bạn hãy viết chương trình:
- Đếm tổng số lượng lịch trình (hoán vị) thỏa mãn điều kiện trên.
- Liệt kê toàn bộ các hoán vị hợp lệ theo thứ tự từ điển tăng dần, mỗi hoán vị trên một dòng (các số cách nhau bởi đúng 1 dấu cách).
Quy ước nộp bài
- Chỉ cần viết một chương trình đọc
stdinvà in rastdout. Bài này không yêu cầu viết hàm. - Không dùng
coutđể in lời nhắc trước khi đọc dữ liệu. Lời nhắc sẽ lọt vàostdoutvà làm bài sai. - Chỉ in đúng nội dung ở mục Output. Không in thêm nhãn, dòng trống hay ký tự thừa.
- Output được so khớp từng ký tự, phân biệt chữ hoa/thường và dấu câu.
Input
Một dòng duy nhất chứa số nguyên dương N (1 ≤ N ≤ 9).
Output
- Dòng 1: In một số nguyên là tổng số lượng hoán vị thỏa mãn.
- Các dòng tiếp theo: In danh sách các hoán vị hợp lệ theo thứ tự từ điển tăng dần. Nếu không có hoán vị nào thỏa mãn, không in thêm dòng nào.
Ràng buộc
- 1 ≤ N ≤ 9.
- Thời gian chạy: 1000ms.
- Bộ nhớ tối đa: 256MB.
Ví dụ 1
Input
3Output
6
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1Giải thích
Với N = 3, các số là {1, 2, 3}. Chỉ có duy nhất một số chẵn là 2, do đó không bao giờ có hai số chẵn đứng cạnh nhau. Toàn bộ 3! = 6 hoán vị đều thỏa mãn.
Ví dụ 2
Input
4Output
12
1 2 3 4
1 4 3 2
2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
3 2 1 4
3 4 1 2
4 1 2 3
4 1 3 2
4 3 1 2
4 3 2 1Giải thích
Tập hợp {1, 2, 3, 4} có hai số chẵn là 2 và 4. Các cấu hình chứa 2 4 hoặc 4 2 (như 1 2 4 3 hay 2 4 1 3) đều bị loại bỏ. Còn lại đúng 12 cấu hình hợp lệ.
Gợi ý và lời giải chỉ mở sau khi bạn bấm Nộp bài. Giáo viên và quản trị viên mở được ngay.
Góp ý & báo lỗi bài tập
Đề bài chưa rõ, test có vấn đề hay bạn có ý tưởng giúp bài tốt hơn? Gửi cho đội ngũ AI Empire nhé — mỗi góp ý đều được đọc.