Chỗ ngồi trong nghị viện
Đề bài
Mô tả
Có nghị sĩ được đánh số từ đến . Các nghị sĩ mang số lẻ thuộc đảng Dân chủ, các nghị sĩ mang số chẵn thuộc đảng Cộng hòa.
Hội trường là một bảng hình chữ nhật gồm hàng, mỗi hàng có ghế. Hai ghế được coi là kề nhau nếu chúng chung một cạnh (tức là ở cùng hàng và cạnh nhau, hoặc ở cùng cột và cạnh nhau).
Nếu hai nghị sĩ cùng đảng ngồi ở hai ghế kề nhau thì họ sẽ mải bàn chuyện nội bộ. Hãy sắp xếp chỗ ngồi cho toàn bộ nghị sĩ sao cho không có hai nghị sĩ cùng đảng nào ngồi ở hai ghế kề nhau. Mỗi nghị sĩ ngồi một ghế, mỗi ghế có nhiều nhất một nghị sĩ, và có thể có ghế bỏ trống.
Dữ liệu vào
Một dòng chứa ba số nguyên , , : số nghị sĩ, số hàng và số ghế mỗi hàng.
Dữ liệu ra
Nếu không tồn tại cách sắp xếp hợp lệ, in ra .
Ngược lại, in ra dòng, mỗi dòng gồm số nguyên. Số thứ trên dòng thứ là chỉ số của nghị sĩ ngồi ở ghế đó, hoặc nếu ghế bỏ trống. Nếu có nhiều đáp án, in ra một đáp án bất kỳ.
Ràng buộc
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 3 2 2 | 1 2 0 3 |
Nghị sĩ 1 và 3 (Dân chủ) không kề nhau; 2 (Cộng hòa) không kề đảng viên cùng đảng. Nhiều đáp án khác cũng hợp lệ. |
| 10 2 2 | -1 | Chỉ có 4 ghế nhưng cần 10 nghị sĩ, không thể xếp hết. |
| 8 4 3 | 1 2 3 4 5 6 7 8 0 0 0 0 |
8 nghị sĩ xếp theo kiểu bàn cờ nên hai ghế kề nhau luôn khác tính chẵn lẻ chỉ số, tức khác đảng. |
Bình luận