【題目敘述】https://zerojudge.tw/ShowProblem?problemid=c295
【Tag】算術運算、條件判斷
【解題想法】
- 給定N群數字，每群都恰有M個「正整數」。
- 若從每群數字中各選擇一個數字，計算N個數字的最大總和 (S)。
- 因為所有數字都是正整數，意即從每群數字中選擇最大的數字。
- 並判斷各群所選出的數字是否可以整除 S。
【作法-1】array
#include <iostream>
using namespace std;
int main() {
int N, M;
cin >> N >> M;
int sum = 0;
int a[N];
for (int i = 0; i < N; i++) {
int x, mx = 0;
for (int j = 0; j < M; j++) {
cin >> x;
mx = max(mx, x);
}
a[i] = mx;
sum += mx;
}
cout << sum << "\n";
int cnt = 0;
for (int i = 0; i < N; i++) {
if (sum % a[i] == 0) {
cnt++;
cout << a[i] << " ";
}
}
if (cnt == 0) {
cout << "-1\n";
}
return 0;
}
【作法-2】vector
#include <iostream>
#include <vector>
using namespace std;
int main() {
int N, M;
cin >> N >> M;
int sum = 0;
vector <int> v(N);
for (int i = 0; i < N; i++) {
int x, mx = 0;
for (int j = 0; j < M; j++) {
cin >> x;
mx = max(mx, x);
}
v[i] = mx;
sum += mx;
}
cout << sum << "\n";
int cnt = 0;
for (int i = 0; i < N; i++) {
if (sum % v[i] == 0) {
cnt++;
cout << v[i] << " ";
}
}
if (cnt == 0) {
cout << "-1\n";
}
return 0;
}
【作法-3】使用兩個一維vector
#include <iostream>
#include <vector>
using namespace std;
int main() {
int N, M;
cin >> N >> M;
int sum = 0;
vector <int> v(N);
for (int i = 0; i < N; i++) {
int x, mx = 0;
for (int j = 0; j < M; j++) {
cin >> x;
mx = max(mx, x);
}
v[i] = mx;
sum += mx;
}
cout << sum << "\n";
vector <int> ans;
for (int i = 0; i < N; i++) {
if (sum % v[i] == 0) {
ans.push_back(v[i]);
}
}
if (ans.size() == 0) {
cout << "-1\n";
} else {
for (auto x : ans) {
cout << x << " ";
}
}
return 0;
}
【作法-4】使用二維 vector 和 max_element()
但是，這一題，其實不需要把所有input data存下來。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int N, M;
cin >> N >> M;
int sum = 0;
vector <vector <int>> v(N);
for (int i = 0; i < N; i++) {
int x;
for (int j = 0; j < M; j++) {
cin >> x;
v[i].push_back(x);
}
sum += *max_element(v[i].begin(), v[i].end());
}
cout << sum << "\n";
vector <int> ans;
for (int i = 0; i < N; i++) {
int mx = *max_element(v[i].begin(), v[i].end());
if (sum % mx == 0) {
ans.push_back(mx);
}
}
if (ans.size() == 0) {
cout << "-1\n";
} else {
for (auto x : ans) {
cout << x << " ";
}
}
return 0;
}
Python code
while True:
try:
n, m = map(int, input().split())
lst = []
total = 0
for i in range(n):
templst = list(map(int, input().split()))
num = max(templst)
total += num
lst.append(num)
print(total)
anslst = []
for num in lst:
if total % num == 0:
anslst.append(num)
if anslst:
print(' '.join([str(i) for i in anslst]))
else:
print(-1)
except:
break