MTRGAME - Matrix Game
Giới hạn- Thời gian: 0.555s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Hai người P1 và P2 đang chơi một trò chơi. Trò chơi được thực hiện trên một ma trận số nguyên M, với kích thước m x n.
Tại một lượt đi, P1 chọn một số i nằm trong khoảng từ 0 đến m-1 trong khi P2 chọn một số j nằm trong khoảng từ 0 đến n-1. Điều thú vị là cả hai đều không biết số mà người kia đã chọn ...
Sau khi hoàn thành việc chọn số, họ thông báo số của mình cho người kia biết. M[i][j] là một phần tử của ma trận được quyết định bởi các chỉ số mà 2 người chơi đã chọn. Nếu M[i][j] là một số âm, P1 trả P2 một lượng tiền bằng trị tuyệt đối của M[i][j]. Tuy nhiên, nếu M[i][j] là một số dương, thì P2 phải trả P1 một lượng bằng M[i][j].
Cho ma trận M và biết rằng cả hai người chơi đều tuyệt đối thông minh, hay tính số tiền trung bình mà P2 trả P1 cho một lượt chơi trong trò chơi.
Lưu ý: P1 chơi để kiếm được nhiều tiền nhất, trong khi P2 cố gắng để phải trả ít tiền nhất.
Input
Dòng đầu chứa T, số lượng test.
Trong mỗi test, dòng đầu chứa 2 số nguyên m và n, thể hiện kích thước của ma trận. Tiếp theo là m dòng, mỗi dòng chứa n số nguyên thể hiện các phần tử của ma trận.
Output
Chứa T dòng, mỗi dòng chứa một số thực với chính xác 3 chữ số thập phân, thể hiện số tiền trung bình mà P1 nhận được trong 1 lượt chơi.
Example
Input: 3 1 1 -1 2 2 1 2 3 4 2 2 1 4 4 3 Output: -1.000 3.000 3.250
Constraints
Input Set 1: m <= 2, n <= 10, abs(values) <= 150000, số lượng test <= 120.
Input Set 2: m <= 2, n <= 5000, abs(values) <= 150000, số lượng test <= 20.
Input Set 3: m <= 2, n <= 100000, abs(values) <= 150000, số lượng test <= 10.
Input Set 4: m <= 3, n <= 5000, abs(values) <= 150000, số lượng test <= 15.
- Người up: racer
- Nguồn bài: Code Craft 09