24676: 共同富裕

http://cs101.openjudge.cn/practice/24676/

Z&Z公司设计了一种发奖金的规则：把n个人的总奖金分成n x n份，放入一个矩阵中，每一份都为正整数，每个人最终拿到的奖金是矩阵中某一列的和。

但财务认为其中运气成分太高，所以提出了一种平衡性调整：可以对奖金矩阵的任意一行进行右移。具体来说，如果对某一行ai1, ai2, ..., ain进行一次右移，最右侧的奖金移动到这一行的开头：ain, ai1, ai2, ..., ai(n-1)。每一行都可以进行任意次右移操作。

最终的目标是希望在对奖金矩阵的每一行经过若干次右移后，个人拿到奖金的最高值最小，即每列和的最大值最小。

输入

输入包括多组数据，每一组数据的第一行包含一个正整数n（n不大于5），代表有n个人参与奖金发放，接下来的n行，每行包含n个正整数，代表奖金矩阵。输入数据以一个0为结尾代表结束

输出

对于每组数据，输出一行，包括一个正整数，为奖金最高值的最小值

样例输入

样例输出

11
15

itertools product permutation区别？

itertools.product和itertools.permutation是Python标准库中的两个模块，用于处理组合和排列的操作。

itertools.product函数返回两个或多个可迭代对象的笛卡尔积。它接受多个可迭代对象作为输入，并返回一个迭代器，该迭代器生成包含所有输入可迭代对象元素的元组。换句话说，它返回了所有可能的组合情况。例如，itertools.product('ABCD', 'xy')将生成('A', 'x')，('A', 'y')，('B', 'x')，('B', 'y')，('C', 'x')和('C', 'y')。

itertools.permutation函数返回一个可迭代对象，该对象生成指定长度的所有可能排列。它接受一个可迭代对象和一个整数作为参数，整数表示每个排列的长度。它生成的排列中的元素顺序不同，但保持了原始集合中元素的顺序。例如，itertools.permutation('ABCD', 2)将生成('A', 'B')，('A', 'C')，('A', 'D')，('B', 'A')，('B', 'C')，('B', 'D')，('C', 'A')，('C', 'B')，('C', 'D')，('D', 'A')，('D', 'B')和('D', 'C')。

因此，itertools.product用于生成多个可迭代对象的所有可能组合，而itertools.permutation用于生成一个可迭代对象的所有可能排列。

为了解决这个问题，我们可以用暴力搜索的方法来尝试每一行的所有可能的右移操作，然后寻找每一列的最大值，最终得到所有情况中的最小值。

为了进行暴力搜索，我们可以利用Python的itertools库中的product函数来产生所有可能的行移动组合。对于每一种组合，我们计算每一列的和，并保留所有组合中的最大列和的最小值。

下面是对应的Python代码实现：

python

from itertools import product

def right_shift(row, shift):
    return row[-shift:] + row[:-shift]

def calculate_max_column_sum(matrix):
    n = len(matrix)
    column_sums = [0] * n
    for row in matrix:
        for i, val in enumerate(row):
            column_sums[i] += val
    return max(column_sums)

def find_min_max_column_sum(n, original_matrix):
    min_max_sum = float('inf')

    # 产生所有行可能的移动方式
    all_shifts = list(product(range(n), repeat=n))
    for shifts in all_shifts:
        # 应用移动
        shifted_matrix = [
            right_shift(original_matrix[i], shifts[i]) for i in range(n)
        ]
        # 计算当前移动方式下的最大列和
        max_column_sum = calculate_max_column_sum(shifted_matrix)
        # 更新最小的最大列和
        min_max_sum = min(min_max_sum, max_column_sum)
    
    return min_max_sum

# 输入处理
results = []
while True:
    n = int(input())
    if n == 0:
        break
    
    original_matrix = [list(map(int, input().split())) for _ in range(n)]
    result = find_min_max_column_sum(n, original_matrix)
    results.append(result)

# 输出结果
for result in results:
    print(result)

24676: 共同富裕 ​

24676: 共同富裕