Đại học Forest cung cấp \(N\) môn học và sinh viên phải hoàn thành tất cả để lấy bằng. Các môn chỉ được học lần lượt: phải hoàn thành một môn rồi mới bắt đầu môn khác. Mỗi môn hoặc là cơ bản, có thể học mà không cần kiến thức trước, hoặc là nâng cao, có đúng một môn khác làm tiên quyết.

Sinh viên phải học môn tiên quyết trước môn phụ thuộc, nhưng hai môn không nhất thiết liền nhau. Một môn có thể là tiên quyết của nhiều môn khác. Không có chu trình tiên quyết. Mọi thứ tự gồm đủ \(N\) môn và tuân thủ các quan hệ tiên quyết đều hợp lệ để lấy bằng.

Khi bạn tốt nghiệp, trường kỷ niệm thứ tự môn học bằng cách in bản viết tắt lên mũ tốt nghiệp: đó là chuỗi gồm chữ cái đầu tên từng môn, theo đúng thứ tự bạn đã học. Ví dụ, học Coding rồi Jamming sẽ tạo chuỗi CJ. Việc có một số từ ngầu xuất hiện làm chuỗi con trên mũ được coi là hợp thời.

Xét tất cả các thứ tự học hợp lệ. Với mỗi từ ngầu, hãy tìm tỉ lệ các thứ tự mà từ đó xuất hiện ít nhất một lần làm chuỗi con của chuỗi trên mũ. Cần lưu ý ta lấy tỉ lệ trên các thứ tự môn học, không phải trên các chuỗi mũ khác nhau. Nhiều môn có thể bắt đầu bằng cùng một chữ cái, nên số chuỗi phân biệt có thể ít hơn số thứ tự môn.

Khác thường so với Code Jam, bài này chỉ yêu cầu đáp án xấp xỉ; hãy đặc biệt chú ý định dạng đầu ra.

Cách thi bài này

Bài chỉ có một bộ Small và không có bộ Large. Bạn có thể thử lại input, nhưng sẽ chịu phạt thời gian.

Dữ liệu vào

Dòng đầu chứa số bộ test \(T\). Mỗi bộ test gồm năm dòng theo thứ tự:

1. Số môn học \(N\).
2. \(N\) số nguyên; số thứ \(i\) là chỉ số môn tiên quyết của môn \(i\), hoặc 0 nếu môn \(i\) là môn cơ bản. Các môn được đánh số từ 1 đến \(N\).
3. Một chuỗi gồm \(N\) chữ cái tiếng Anh in hoa, không có khoảng trắng; ký tự thứ \(i\) là chữ cái đầu tên môn \(i\).
4. Số từ ngầu \(M\).
5. \(M\) từ ngầu, mỗi từ chỉ gồm các chữ cái tiếng Anh in hoa.

Dữ liệu ra

Với mỗi bộ test, in Case #x: y1 y2 ... yM, trong đó x là số thứ tự bộ test, bắt đầu từ 1, và \(y_i\) là tỉ lệ các thứ tự môn hợp lệ mà từ ngầu thứ \(i\) xuất hiện làm chuỗi con trên mũ tốt nghiệp.

\(y_i\) được coi là đúng nếu sai số tuyệt đối so với đáp án không quá \(0.03\).

Ràng buộc

Phân nhóm

Test Set 1 (Small, hiển thị)

• \(1\le T\le100\).
• \(1\le N\le100\).
• \(1\le M\le5\).
• Độ dài mỗi từ ngầu từ 1 đến 20.
• Mỗi từ ngầu chỉ gồm chữ cái tiếng Anh in hoa.
• Không có chu trình do các quan hệ tiên quyết tạo thành.

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

2
2
0 1
CJ
4
CJ C D JC
3
0 1 0
BAA
3
AA AAB ABA

Case #1: 1.0 1.0 0.0 0.0
Case #2: 0.67 0.0 0.33

Nguồn

Google Code Jam 2016, Vòng 3, bài Forest University.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.