Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

PTIT014G - 2014 Bài G - Trò chơi trên bảng số

Cho bảng số A gồm n hàng và n cột. Các hàng được đánh số từ 1 đến n, từ trên xuống dưới, các cột của lưới được đánh số từ 1 đến n, từ trái sang phải. Ô giao của hàng i và cột j gọi là ô (i, j) và được điền một số nguyên aij có giá trị tuyệt đối không vượt quá 109.

Xét trò chơi đối kháng giữa hai người trên bảng như sau: Trò chơi diễn ra trong n lượt đi, mỗi lượt người thứ nhất chọn một hàng, người thứ hai chọn một cột. Giả sử, tại một lượt đi, nếu người chơi thứ nhất chọn hàng i, người chơi thứ hai chọn cột j, khi đó người thứ nhất được cộng aij điểm, người thứ hai được cộng -aij điểm. Sau lượt đi đó, bảng bị xóa hàng và cột mà hai người chơi vừa chọn. Người có điểm càng cao càng thể hiện sự thông minh của mình.

Yêu cầu: Cho bảng số A và biết cả hai người đều chơi tối ưu, hãy tính điểm lớn nhất mà người thứ nhất có thể đạt được.

Input

Dữ liệu vào gồm nhiều bộ dữ liệu tương ứng với nhiều test. Dòng đầu tiên ghi K (K≤100) là số bộ test. Tiếp theo là K nhóm dòng,  mỗi nhóm là một bộ dữ liệu có cấu trúc như sau:

  • Dòng đầu của nhóm ghi số n (n≤ 8) ;
  • n dòng sau, mỗi dòng chứa n số nguyên mô tả bảng số.

Output

Với mỗi bộ dữ liệu, ghi ra trên một dòng một số nguyên là điểm lớn nhất có thể của người thứ nhất tương ứng với dữ liệu vào.

Example

Input:
3
2
10 10
-5 -5
2
10 -5
10 -5
2
10 -5
-5 10 Output: 5
5
-10

Được gửi lên bởi:adm
Ngày:2014-03-31
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

hide comments
2018-06-02 06:35:37
ô ở dưới nói sai rồi, đề bài bảo là cả 2 người cùng chơi tối ưu nên đáp án phải là điểm số cao nhất của người thứ nhất khi người thứ 2 chơi tối ưu.

Last edit: 2018-06-02 06:36:10
2018-03-08 10:52:32
mỗi khi chọn 1 hàng, người thứ nhất được cộng số điểm nào đó trên một cột bất kì --> sinh hoán vị của n
điểm cộng của người thứ nhất tùy thuộc vào cột mà người thứ hai chọn, mà hai người đêu chơi tối ưu để đạt được điểm cao nhất--> đáp án của bài toán là điểm số nhỏ nhất có thể có của người thứ nhất
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.