Công bố kết quả giờ cuối
Đề bài
Mô tả
Phần thú vị nhất của một kỳ thi ICPC là gì? Chắc chắn đó là Last Hour Resolver (công bố kết quả giờ cuối)! Trong lễ trao giải, mọi người dõi theo màn hình để xem bảng xếp hạng được mở băng. Ai cũng nín thở chờ kết quả và hò reo thật lớn mỗi khi một đội giải được một bài!
Lưu ý:
- Bài toán này lấy cảm hứng từ thể thức ICPC. Tuy nhiên, nó đã được sửa đổi và đơn giản hóa để phù hợp với một bài toán thuật toán. Vì vậy, các luật được nêu trong bài khác với luật chính thức của ICPC.
- Không cần, và cũng không có lợi gì khi biết luật chính thức của ICPC để giải bài này.
- Bạn chỉ nên giải bài dựa trên những gì được nêu rõ trong đề bài.
Năm nay, kỳ thi Lập trình ICPC Quốc gia Việt Nam thu hút đội, được đánh số từ đến . Bộ đề gồm bài, được đặt tên bằng chữ cái tiếng Anh in hoa đầu tiên: bài là A, bài là B, và cứ thế.
Một kỳ thi ICPC kéo dài giờ. Trong giờ đầu, bảng xếp hạng được công khai và mọi thí sinh đều xem được kết quả của các đối thủ. Tuy nhiên, bảng xếp hạng bị đóng băng trong giờ cuối cùng, nên không đội nào biết được kết quả của các đội khác.
Kết quả của mỗi đội được đánh giá bằng số bài giải được và một giá trị gọi là điểm phạt. Khi một đội giải được một bài, điểm phạt của đội tăng thêm một giá trị, được xác định bởi thời điểm đội nộp bài đúng đầu tiên cho bài đó và số lần nộp sai trước lần nộp này. Lưu ý rằng các bài chưa giải được không ảnh hưởng đến điểm phạt của đội.
Các đội được xếp hạng từ đến theo các quy tắc sau:
- Đội giải được nhiều bài hơn xếp trên.
- Trong các đội có cùng số bài giải được, đội có điểm phạt nhỏ hơn xếp trên.
- Trong các đội có cùng số bài giải được và cùng điểm phạt, đội có chỉ số nhỏ hơn xếp trên.
Có thể thấy không có hai đội nào có cùng thứ hạng.
Bảng xếp hạng đóng băng là một ma trận , trong đó ô ở hàng , cột thể hiện trạng thái của đội ở bài , có một trong các dạng sau:
- : Đội đã giải được bài này trước giờ cuối, và điểm phạt của đội tăng thêm .
- -: Đội chưa giải được bài này trước giờ cuối, và không nộp bài nào trong giờ cuối.
- ? : Đội chưa giải được bài này trước giờ cuối, và đã nộp bài trong giờ cuối. Kết quả chưa được công khai, và có hai khả năng:
- Ô trở thành + : Có ít nhất một lần nộp đúng. Đội được thêm một bài giải được và điểm phạt tăng thêm .
- Ô trở thành -: Mọi lần nộp đều sai. Đội không được thêm bài giải được và điểm phạt giữ nguyên.
Kỳ thi đã kết thúc và giờ là phần tuyệt vời nhất: Last Hour Resolver! Không may, chương trình công bố kết quả có lỗi: thay vì hiển thị chính xác kết quả các lần nộp trong giờ cuối, nó công bố ngẫu nhiên! Cụ thể, mỗi ô dạng ? biến thành + hoặc - với xác suất bằng nhau. Rõ ràng, điều này khiến bảng xếp hạng cực kỳ khó đoán!
Vì kết quả khá ngẫu nhiên, tất cả các đội đều muốn biết thứ hạng kỳ vọng của mình. Sau giờ lập trình họ đã quá mệt, nên nhờ bạn giúp. Cho bảng xếp hạng đóng băng, hãy tính thứ hạng kỳ vọng của tất cả các đội.
Dữ liệu vào
Dòng đầu tiên chứa hai số nguyên và (; ): số đội và số bài.
Trong dòng tiếp theo, dòng thứ chứa xâu , trong đó là trạng thái của đội ở bài , có một trong các dạng "+ ", "-" hoặc "? ". là một số nguyên trong đoạn .
Dữ liệu ra
In ra dòng, dòng thứ chứa một phân số tối giản dạng biểu diễn thứ hạng kỳ vọng của đội thứ . Phân số là tối giản nếu và nguyên tố cùng nhau và . Có thể chứng minh rằng thứ hạng kỳ vọng luôn là một số hữu tỉ.
Ràng buộc
- ; .
- Mỗi ô có dạng "+ ", "-" hoặc "? " với .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 3 3 + 2 + 3 ? 4 - ? 1 + 3 ? 2 - - |
5/4 2/1 11/4 |
Có ô dạng ? nên có kịch bản đồng khả năng. Đội 1 có xác suất xếp hạng và xếp hạng , thứ hạng kỳ vọng . Đội 2 có xác suất xếp hạng , xếp hạng , xếp hạng , thứ hạng kỳ vọng . Đội 3 có xác suất xếp hạng và xếp hạng , thứ hạng kỳ vọng . |
| 3 1 ? 1 ? 1 ? 1 |
3/2 2/1 5/2 |
Khi hai đội cùng số bài giải được và cùng điểm phạt, đội có chỉ số nhỏ hơn xếp trên. |
Bình luận