Bài toán tìm số cách sắp xếp trận đấu

Một giải thi đấu bóng đá gồm ~n~ đội thi đấu vòng tròn một lượt. Các đội bóng được đánh số thứ tự từ ~1~ đến ~n~. Theo thể lệ giải đấu, nếu trận đấu diễn ra với kết quả hòa, hai đội sẽ thi đấu luân lưu cho đến khi phân định thắng thua (nghĩa là các trận đấu đều được phân định thắng thua).

Hỏi có tồn tại một cách sắp xếp các đội theo thứ tự sao cho trong thứ tự đó, mỗi đội đều thắng trận đấu với đội liền sau mình? Trong trường hợp tồn tại, hãy xác định một cách sắp xếp như vậy.

Input

• Dòng đầu tiên chứa số nguyên ~n~ ~(1 \leq n \leq 1000)~ --- số đội bóng tham dự giải đấu.
• Dòng thứ ~i~ trong số ~n~ dòng tiếp theo chứa ~j~ kí tự '0' hoặc '1', kí tự thứ ~j~ thế hiện giá trị ~a_{ij}~:
  • ~a_{ii}~ = 0 với mọi ~i~.
  • ~a_{ij}~ = 1 nếu và chỉ nếu đội ~i~ thắng đội ~j~. Dữ liệu vào luôn thỏa mãn ~a_{ij}~ +~a_{ji}~ = 1 với ~i~ khác ~j~.

Chú ý: Có ~30\%~ số test có ~n \leq 9~.

Output

In ra ~-1~ nếu không tồn tại cách sắp xếp thỏa mãn yêu cầu. Trong trường hợp tồn tại, in ra ~n~ số nguyên là chỉ số của các đội bóng trong cách sắp xếp tìm được.

Cho dù biết tỷ số tất cả trận đấu có M và T tham gia, nhưng ta hoàn toàn không thể biết kết quả so kè của hai đội này.

Đề bài:

Trong một giải bóng đá tứ hùng, đội bóng M, Y, T, S thi đấu vòng tròn một lượt. Đội thắng được 3 điểm, đội thua được 0 điểm, nếu hai đội hòa nhau thì mỗi đội được 1 điểm.

Kết thúc giải, đội M không ít điểm hơn đội T, hiệu số bàn thắng - bàn thua của đội T là 4-1. Hiệu số bàn thắng - bàn thua của đội M là 1- 4.

Hỏi các trận đấu mà đội M chơi có tỷ số nào? Các trận đấu mà đội T chơi có tỷ số nào?

Tôi xin đưa ra đáp án:

Thoạt nhìn thì thông tin mà ta có quá ít để có thể xác định được tỷ số các trận đấu bởi có quá nhiều khả năng xảy ra. Nhưng nếu phân tích kỹ thì ta thấy đội T có hiệu số bàn thắng thua là 4-1 nên có ít nhất một trận thắng và nhiều nhất một trận thua. Suy ra điểm số của T ít nhất là 4.

Trong khi đó, đội M có hiệu số bàn thắng thua là 1-4 nên có nhiều nhất một trận thắng và ít nhất một trận thua. Suy ra điểm số của T nhiều nhất là 4. Từ đó, cộng thêm điều kiện đội M không ít điểm hơn đội T, ta suy ra đội M và đội T cùng được 4 điểm, tức là mỗi đội thắng một trận, hòa một trận và thua một trận.

Đội T có hiệu số bàn thắng bại là 4-1 nên trận thua phải thua với tỷ số 0-1, hòa tỷ số 0-0 và thắng với tỷ số 4-0. Tương tự đội M thắng 1-0, hòa 0-0 và thua 0-4.

Cuối cùng, điều thú vị là cho dù biết tỷ số tất cả trận đấu có M và T tham gia, nhưng ta hoàn toàn không thể biết kết quả trận đấu giữa M và T bởi mọi kết quả đều có thể xảy ra: M thắng T 1-0, hòa 0-0 hay thua 0-4!

Đã gửi 11-10-2021 - 22:46

quochuy50618

Binh nhất

• Thành viên mới
• 21 Bài viết

ĐỀ: Chứng minh rằng với mọi số nguyên dương n, n ≥ 2, có thể sắp xếp lịch thi đấu một vòng tròn một lượt cho n đội bóng trong:

1. n−1 vòng nếu n chẵn;

2. n vòng nếu n lẻ.

Biết rằng một vòng là tập hợp các trận đấu mà mỗi đội đấu với nhau đúng một trận nếu n chẵn, và có đúng một đội không thi đấu nếu n lẻ. Hai vòng đấu khác nhau khi không có bất kì hai trận đấu nào của mỗi vòng có cùng hai đội chơi. Lịch thi đấu vòng tròn một lượt là lịch thi đấu mà hai đội bất kì đấu với nhau đúng một trận.

• DOTOANNANG yêu thích

Đã gửi 12-10-2021 - 09:12

DOTOANNANG

Đại úy

• ĐHV Toán Cao cấp
• 1608 Bài viết

Em xem thêm ở đây_ https://en.wikipedia...obin_tournament, anh lấy ví dụ với trường hợp là chẵn $n= 10$ trước:

Còn cách xoay tua khác là:

Cái format đây còn là một trong những giải thuật điều phối CPU căn cứ vào danh sách Ready List (ở đây là các CLb).