SOCCER - Lịch thi đấu
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 2.0 giây
Giới hạn bộ nhớ: 128 megabyte
Đăng bởi: yurilover172

Một giải đấu bóng đá có n đội tham dự (n là lũy thừa của 2). Các đội được đánh số từ 0 tới n - 1.

Hình dưới đây mô tả cách thức thi đấu của giải:

Cho biết kết quả trận đấu giữa 2 đội bất kỳ theo dạng mảng w kích thước n x n. w[i, j] = 'Y' nếu đội i thắng đội j, w[i, j] = 'N' nếu đội i thua đội j.

Có tổng cộng n! cách để sắp xếp các đội ở vòng đầu tiên. Mỗi cách sắp xếp sẽ dẫn tới một kết quả khác nhau. Vì vậy, với mỗi đội i, bạn cần xác định xem có bao nhiêu cách sắp xếp để dẫn tới đội i vô địch.

Input:

- Dòng đầu tiên ghi số n.

- n dòng tiếp theo, mỗi dòng gồm n ký tự mô tả mảng w.

Output:

- Gồm n dòng, dòng thứ i ghi số cách sắp xếp để đội i vô địch.

Giới hạn:

- n <= 16.

- Với mọi i, w[i, i] = 'N'.

- Với mọi i, j (i != j), có đúng một trong hai w[i, j] và w[j, i] là 'Y'.

Ví dụ

  • input
    2
    NN
    YN
    output
    0
    2
  • input
    4
    NYNY
    NNYN
    YNNY
    NYNN
    output
    8
    0
    16
    0

Nguồn bài: Topcoder

Back to Top