Matrix Game

View as PDF

Submit solution

Points: 1.86 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Problem source:
Code Craft 09
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Hai người ~P_1~ và ~P_2~ đ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 \times n~.

Tại một lượt đi, ~P_1~ chọn một số ~i~ nằm trong khoảng từ ~0~ đến ~m - 1~ trong khi ~P_2~ 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, ~P_1~ trả ~P_2~ 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ì ~P_2~ phải trả ~P_1~ 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à ~P_2~ trả ~P_1~ cho một lượt chơi trong trò chơi.

Lưu ý: ~P_1~ chơi để kiếm được nhiều tiền nhất, trong khi ~P_2~ 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à ~P_1~ nhận được trong ~1~ lượt chơi.

Giới hạn

Input Set ~1~: ~m \le 2~, ~n \le 10~, ~|M_{i, j}| \le 150000~, số lượng test ~\le 120~.

Input Set ~2~: ~m \le 2~, ~n \le 5000~, ~|M_{i, j}| \le 150000~, số lượng test ~\le 20~.

Input Set ~3~: ~m \le 2~, ~n \le 100000~, ~|M_{i, j}| \le 150000~, số lượng test ~\le 10~.

Input Set ~4~: ~m \le 3~, ~n \le 5000~, ~|M_{i, j}| \le 150000~, số lượng test ~\le 15~.

Sample Input

3
1 1
-1
2 2
1 2
3 4
2 2
1 4
4 3

Sample Output

-1.000
3.000
3.250

Comments

Please read the guidelines before commenting.


There are no comments at the moment.