# APCS實作題2016年10月第2題：最大和
> 第1版：2023年2月11日
> 第2版：2023年6月9日，加上 C++ 程式碼
> 第3版：2023年10月19日，將程式碼改為更精簡的版本
> 作者：王一哲
> 題目來源：[105年10月29日實作題第2題](https://apcs.csie.ntnu.edu.tw/wp-content/uploads/2020/11/1051029APCSImplementation.pdf)
> [ZeroJudge 題目連結](https://zerojudge.tw/ShowProblem?problemid=c295)
<br />
## 題目
### 問題描述
給定 $N$ 群數字，每群都恰有 $M$ 個正整數。若從每群數字中各選擇一個數字(假設第 $i$ 群所選出數字為 $t_i$)，將所選出的 $N$ 個數字加總即可得總和 $S = t_1 + t_2 + \dots + t_N$。請寫程式計算 $S$ 的最大值(最大總和)，並判斷各群所選出的數字是否可以整除 $S$。
<br />
### 輸入格式
第一行有二個正整數 $N$ 和 $M$， $1 \leq N \leq 20$，$1 \leq M \leq 20$。接下來的 $N$ 行，每一行各有 $M$ 個正整數 $x_i$，代表一群整數，數字與數字間有一個空格，且 $1 \leq i \leq M$，以及 $1 \leq x_i \leq 256$。
<br />
### 輸出格式
第一行輸出最大總和 $S$。
第二行按照被選擇數字所屬群的順序，輸出可以整除 $S$ 的被選擇數字，數字與數字間以一個空格隔開，最後一個數字後無空白；若 $N$ 個被選擇數字都不能整除 $S$，就輸出 $-1$。
<br />
### 範例一：輸入
```
3 2
1 5
6 4
1 1
```
### 範例一：正確輸出
```
12
6 1
```
（說明）挑選的數字依序是 5,6,1，總和 $S = 12$。而此三數中可整除 $S$ 的是 6 與 1，6 在第二群，1 在第 3 群所以先輸出 6 再輸出 1。注意，1 雖然也出現在第一群，但它不是第一群中挑出的數字，所以順序是先 6 後 1。
<br />
### 範例二：輸入
```
4 3
6 3 2
2 7 9
4 7 1
9 5 3
```
### 範例二：正確輸出
```
31
-1
```
（說明）挑選的數字依序是 6,9,7,9，總和 $S = 31$。而此四數中沒有可整除 $S$ 的，所以第二行輸出 $-1$。
<br />
### 評分說明
輸入包含若干筆測試資料，每一筆測試資料的執行時間限制(time limit)均為 1 秒，依正確通過測資筆數給分。其中：
- 第 1 子題組 20 分：$1 \leq N \leq 20$，$M = 1$。
- 第 2 子題組 30 分：$1 \leq N \leq 20$，$M = 2$。
- 第 3 子題組 50 分：$1 \leq N \leq 20$，$1 \leq M \leq 20$。
<br /><br />
## Python 程式碼
```python=
ts, ds = [], [] # ts 儲存每群數字中最大的值，ds 儲存 ts 當中可以整除最大和的值
N, M = map(int, input().split()) # 由標準輸入讀取資料行數 N、每行資料筆數 M
for _ in range(N): # 讀取 N 行資料
t = max(list(map(int, input().split()))) # 將讀取的資料用空格分隔，轉換成整數格式、組成串列，最後用 max 取出最大值 t
#t = max(map(int, input().split())) # 省略 list，寫成這樣也可以
ts.append(t) # 將 t 加到 ts 最後面
S = sum(ts) # 用 sum 計算最大和 S
for t in ts: # 由 ts 依序讀取元素存入 t，如果 t 可以整除 S 則加到 ds 最後面
if S%t == 0: ds.append(t)
print(S) # 印出最大和 S
if not ds: # 若 N 個被選擇數字都不能整除 S 印出 −1
print("-1")
else: # 按照被選擇數字所屬群的順序，輸出可以整除 S 的被選擇數字
for i in range(len(ds)):
print("{:d}".format(ds[i]), end="\n" if i == len(ds)-1 else " ")
```
<br />
1. 如果將測料存成 data.txt 並與程式碼 test.py 放在同一個資料夾中，於 Linux 的指令界面可以使用以下指令執行程式，就可以不需要每次執行程式時還需要手動輸入測資。
```shell
python3 test.py < data.txt
```
如果使用 Windows PowerShell，則要改成以下的指令
```shell
Get-Content data.txt | python test.py
```
2. 第18行：要注意**最後一筆資料後沒有空格、直接換行**。
6. ZeroJudeg 測試結果，單筆測資費時間久為 20 ms，使用記憶體最多為 3.3 MB，通過測試。
<br /><br />
## C++ 程式碼
### 方法1：用 array 儲存讀取的資料
```cpp=
#include <iostream>
#include <deque>
using namespace std;
int main(int argc, char* argv[]) {
// 由標準輸入讀取資料行數 N、每行資料個數 M、資料 data
int N, M;
cin >> N >> M;
int data[N][M];
for(int i=0; i<N; i++) {
for(int j=0; j<M; j++) {
cin >> data[i][j];
}
}
// 找出每行資料中最大值並儲存到 ts
int ts[N] = {0};
for(int i=0; i<N; i++) {
for(int j=0; j<M; j++) {
if (data[i][j] > ts[i]) ts[i] = data[i][j];
}
}
// 計算並印出最大和 total
int total = 0;
for(int i=0; i<N; i++) {
total += ts[i];
}
cout << total << endl;
// 不確定最大和可被幾個數值整除，使用 deque 儲存資料
deque<int> ds;
for(int i=0; i<N; i++) {
if (total % ts[i] == 0) ds.push_back(ts[i]);
}
// 如果 ds 是空的印出 -1，否則依序印出 ds 的內容
int len = ds.size();
if (ds.empty()) {
cout << "-1" << endl;
} else {
for(int i=0; i<len; i++) {
if (i < (len-1)) cout << ds[i] << " ";
else cout << ds[i] << endl;
}
}
return 0;
}
```
<br />
1. 第7 ~ 14行：由標準輸入讀取資料行數 N、每行資料個數 M、資料 data。
2. 第17 ~ 22行：找出每行資料中最大值並儲存到 ts。
3. 第25 ~ 29行：計算並印出最大和 total。
4. 第32 ~ 35行：因為不確定最大和可被 ts 中的幾個數值整除，使用 deque 儲存資料，將可以整除最大和的數值儲存到 ds。
5. 第38 ~ 46行：如果 ds 是空的印出 -1，否則依序印出串列 ds 的資料，特別注意**最後一筆資料後沒有空格、直接換行**。
6. ZeroJudeg 測試結果：花費時間為 3 ms，使用記憶體 336 kB，通過測試。
<br /><br />
### 方法2：用 vector 儲存讀取的資料，並且合併重複的程式碼
```cpp=
#include <iostream>
#include <vector>
using namespace std;
int main() {
// 由標準輸入讀取資料行數 N、每行資料個數 M
int N, M; cin >> N >> M;
vector<int> ts (N, 0); // ts 儲存每群數字中最大的值，預設為 N 個 0；tmp 暫存讀取的資料，預設為 M 個 0
for(int i=0; i<N; i++) { // 讀取 N 行資料
for(int j=0; j<M; j++) { // 每行 M 筆資料
int t; cin >> t; // 讀取資料並暫存為 t
if (t > ts[i]) ts[i] = t; // 依序讀取 M 個數值並存入 t，如果 t 大於 ts[i] 則更新 ts[i] 的值
}
}
int S = 0; // 最大和 S
for(auto t : ts) S += t; // 依序讀取 ts 的內容暫存給 t，再將 t 加到 S 計算最大和
vector<int> ds; // ds 儲存 ts 當中可以整除最大和的值，不確定最大和可被幾個數值整除，使用 vector 儲存資料
for(auto t : ts) { // 依序讀取 ts 的內容暫存給 t，如果 t 可以整除 S，將 t 加到 ds 最後面
if (S%t == 0) ds.push_back(t);
}
cout << S << endl; // 印出最大和 S
if(ds.empty()) { // # 若 N 個被選擇數字都不能整除 S 印出 −1
cout << "-1" << endl;
} else { // 按照被選擇數字所屬群的順序，輸出可以整除 S 的被選擇數字
for(auto it = ds.begin(); it != ds.end(); it++) {
cout << *it << " \n"[it == ds.end()-1];
}
}
return 0;
}
```
<br />
基於方法1的程式碼，但是改成使用 vector 儲存讀取的資料，並試著合併重複的程式碼，使程式碼更為精簡。於 ZeroJudeg 測試結果，花費時間為 4 ms，使用記憶體 340 kB，通過測試。
<br /><br />
---
###### tags:`APCS`、`Python`
Sign in with Wallet
Connect another wallet