Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
MMATRIX - SHIFT Operator on Matrix |
English | Vietnamese |
Given an n×n matrix A, whose entries Ai,j are integer numbers (0 ≤ i < n, 0 ≤ j < n). An operation SHIFT at row i (0 ≤ i < n) will move the integers in the row one position right, and the rightmost integer will wrap around to the leftmost column.
You can do the SHIFT operation at arbitrary row, and as many times as you like. Define Cj = A[0, j] + A[1, j] + ... + A[n-1, j], and M = max{Cj|0 <= j < n}. Cj is the sum of all number in column ith.
Your job is to minimize M.
Input
The input consists of several test cases. The first line of each test case contains an integer n. Each of the following n lines contains n integers, indicating the matrix A. The input is terminated by a single line with an integer −1. You may assume that 1 ≤ n ≤ 7 and |Ai,j| < 10^4.
Output
For each test case, print a line containing the minimum value of the maximum of column sums.
Example
Input: 2 4 6 3 7 3 1 2 3 4 5 6 7 8 9 -1 Output: 11 15
Được gửi lên bởi: | psetter |
Ngày: | 2009-02-23 |
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: | Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET |
Nguồn bài: | Pre Shanghai 2004 |