2016.10大學程式先修檢測實作題 第二題(最大和)

問題描述
給定 N群數字 ，每 群都恰有 M個正整數 。若從 每群數字 中各選擇一個數字 (假設第 i群所選出數字為 ti )，將所選出的 ，將所選出的 N個數字加總即可得和 S = S = S = S = t1+t2+…+ +…+ tN。請寫程 式計算 S的最大值 (最大總和 )，並判斷各群所選出的數字是 否可以整除 S。
輸入格式
第一行有二個正整數 N和 M， 1≦ N ≦ 20 ，1≦ M ≦ 20 。
接下來的 N行 ，每一各有 M個正整數 xi ，代表一群整數， 數字與間有一個空 格，且 1≦ i ≦M，以及 1≦ xi ≦256 。
輸出格式
第一行輸出最大總和 S。
第二行按照被選擇數字 所屬群的 順序，輸出可以整除 順序，輸出可以整除 順序，輸出可以整除 順序，輸出可以整除 S的被選擇數字，與間 的被選擇數字，與間 的被選擇數字，與間 以一個空格隔開 ，最後一個數字無空白 ；若 N個被選擇數字都不能整除 個被選擇數字都不能整除 個被選擇數字都不能整除 個被選擇數字都不能整除 個被選擇數字都不能整除 個被選擇數字都不能整除 個被選擇數字都不能整除 S，就輸出 ，就輸出 ，就輸出 ，就輸出 -1。
範例一：輸入 範例一：輸入
3 2
1 5
6 4
1 1
範例一：正確輸出 範例一：正確輸出
12
6 1
（說明） 挑選的數字依序是 5, 6, 1，總和 ，總和 S=12S=12S=12 。而此三數中可整除 。而此三數中可整除 。而此三數中可整除 S的是 6與 1， 6在第二群， 在第二群， 1在第 3群所以先輸出 6再 輸出 1。注意， 1雖然也出現在第一群， 但她不是第一群中挑出的數字，所以順 但她不是第一群中挑出的數字，所以順 但她不是第一群中挑出的數字，所以順 但她不是第一群中挑出的數字，所以順 但她不是第一群中挑出的數字，所以順 但她不是第一群中挑出的數字，所以順 但她不是第一群中挑出的數字，所以順 但她不是第一群中挑出的數字，所以順 但她不是第一群中挑出的數字，所以順 但她不是第一群中挑出的數字，所以順 但她不是第一群中挑出的數字，所以順 但她不是第一群中挑出的數字，所以順 但她不是第一群中挑出的數字，所以順 但她不是第一群中挑出的數字，所以順 但她不是第一群中挑出的數字，所以順 但她不是第一群中挑出的數字，所以順 但她不是第一群中挑出的數字，所以順 序是先 6後 1。
範例二：輸入 範例二：輸入
4 3
6 3 2
2 7 9
4 7 1
9 5 3
範例二：正確輸出 範例二：正確輸出
31
-1
（說明） 挑選的數字依序是 挑選的數字依序是 挑選的數字依序是 挑選的數字依序是 挑選的數字依序是 挑選的數字依序是 挑選的數字依序是 挑選的數字依序是 6, 9,7,9 ，總 和 S= 31 。而此四數中沒有可整除 S的， 所以第二行輸出 -1。
程式碼：
n=int(input())
a=[];b=0 #
for i in range(n):
    data=input().split() #分開字串
    d=[int(x) for x in data] #將字串轉成文字
    a.append(d)
    a[i]=max(a[i]) #取出每一群的最大值
    b+=a[i] #將每一群的最大值相加
flag=0 #指標，若不能整除則加1
print(b)
for j in range(n):
    if b%a[j]==0: #能整除如者，則印出
        print(a[j],end=' ') #隔一空格輸出
    else:
        flag+=1
if flag==n: #若每一群的最大值皆不能整除最大和，則flag會等於群數，輸出-1
    print('-1')