Задание 27. Информатика. ЕГЭ. Поляков-2671
- Просмотры: 68
- Изменено: 23 ноября 2024
Имеется набор данных, состоящий из троек положительных целых чисел. Необходимо выбрать из каждой тройки ровно одно число так, чтобы сумма всех выбранных чисел делилась на \(8\) и при этом была максимально возможной. Гарантируется, что искомую сумму получить можно. Программа должна напечатать одно число — максимально возможную сумму, соответствующую условиям задачи.
Входные данные. Даны два входных файла (файл \(A\) и файл \(B\)), каждый из которых содержит в первой строке количество троек \(N\) (\( 1 \leqslant N \leqslant 100000 \)). Каждая из следующих \(N\) строк содержит три натуральных числа, не превышающих \(10~000\).
Пример входного файла:
\(6\)
\(8 \,\, 3 \,\, 4\)
\(4 \,\, 8 \,\, 12\)
\(9 \,\, 5 \,\, 6\)
\(2 \,\, 8 \,\, 3\)
\(12 \,\, 3 \,\, 5\)
\(1 \,\, 4 \,\, 12\)
Для указанных входных данных значением искомой суммы должно быть число \(56\).
В ответе укажите два числа: сначала искомое значение для файла \(А\), затем для файла \(B\).
Решение:
C++
Код нуждается в оптимизации. Но пока так! :)
#include<iostream>
#include<fstream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
int32_t main() {
string base = "";
string fnames[] = {"27-A.txt", "27-B.txt"};
for(string fn: fnames) {
ifstream in(base + fn);
int n, s = 0;
vector<int> r1(7, 100000), r2(3, 100000), r3(2,100000);
int r4 = 100000, r5 = 100000, r6 = 100000, r7 = 100000;
in >> n;
for(int i = 0; i < n; i++) {
vector<int> t(3, 0);
in >> t[0] >> t[1] >> t[2];
sort(begin(t), end(t));
s += t[2];
int a1 = abs(t[2] - t[1]) % 8, a2 = abs(t[2] - t[0]) % 8;
if (a1) {
switch (a1) {
case 1:
r1[6] = min(r1[6], abs(t[2] - t[1]));
sort(begin(r1), end(r1));
break;
case 2:
r2[2] = min(r2[2], abs(t[2] - t[1]));
sort(begin(r2), end(r2));
break;
case 3:
r2[1] = min(r3[1], abs(t[2] - t[1]));
sort(begin(r3), end(r3));
break;
case 4:
r4 = min(r4, abs(t[2] - t[1]));
break;
case 5:
r5 = min(r5, abs(t[2] - t[1]));
break;
case 6:
r6 = min(r6, abs(t[2] - t[1]));
break;
case 7:
r7 = min(r7, abs(t[2] - t[1]));
break;
}
}
else if(a2) {
switch (a2)
{
case 1:
r1[6] = min(r1[6], abs(t[2] - t[0]));
sort(begin(r1), end(r1));
break;
case 2:
r2[2] = min(r2[2], abs(t[2] - t[0]));
sort(begin(r2), end(r2));
break;
case 3:
r2[1] = min(r3[1], abs(t[2] - t[0]));
sort(begin(r3), end(r3));
break;
case 4:
r4 = min(r4, abs(t[2] - t[0]));
break;
case 5:
r5 = min(r5, abs(t[2] - t[0]));
break;
case 6:
r6 = min(r6, abs(t[2] - t[0]));
break;
case 7:
r7 = min(r7, abs(t[2] - t[0]));
break;
}
}
}
if(s % 8) {
vector<int> tmp;
switch (s % 8) {
case 1:
s -= r1[0];
break;
case 2:
s -= min(r1[0] + r1[1], r2[0]);
break;
case 3:
tmp.push_back(r3[0]);
tmp.push_back(r2[0] + r1[0]);
tmp.push_back(r1[2] + r1[1] + r1[0]);
sort(begin(tmp), end(tmp));
s -= tmp[0];
break;
case 4:
tmp.push_back(r4);
tmp.push_back(r3[0] + r1[0]);
tmp.push_back(r2[0] + r2[1]);
tmp.push_back(r2[0] + r1[0] + r1[1]);
tmp.push_back(r1[0] + r1[1] + r1[2] + r1[3]);
sort(begin(tmp), end(tmp));
s -= tmp[0];
break;
case 5:
tmp.push_back(r5);
tmp.push_back(r4 + r1[0]);
tmp.push_back(r3[0] + r2[0]);
tmp.push_back(r3[0] + r1[0] + r1[1]);
tmp.push_back(r2[0] + r2[1] + r1[0]);
tmp.push_back(r2[0] + r1[0] + r1[1] + r1[2]);
tmp.push_back(r1[0] + r1[1] + r1[2] + r1[3] + r1[4]);
sort(begin(tmp), end(tmp));
s -= tmp[0];
break;
case 6:
tmp.push_back(r6);
tmp.push_back(r5 + r1[0]);
tmp.push_back(r4 + r2[0]);
tmp.push_back(r4 + r1[0] + r1[1]);
tmp.push_back(r3[0] + r3[1]);
tmp.push_back(r3[0] + r2[0] + r1[0]);
tmp.push_back(r3[0] + r1[0] + r1[1] + r1[2]);
tmp.push_back(r2[0] + r2[1] + r2[2]);
tmp.push_back(r2[0] + r2[1] + r1[0] + r1[1]);
tmp.push_back(r2[0] + r1[0] + r1[1] + r1[2] + r1[3]);
tmp.push_back(r1[0] + r1[1] + r1[2] + r1[3] + r1[4] + r1[5]);
sort(begin(tmp), end(tmp));
s -= tmp[0];
break;
case 7:
tmp.push_back(r7);
tmp.push_back(r6 + r1[0]);
tmp.push_back(r5 + r2[0]);
tmp.push_back(r5 + r1[0] + r1[1]);
tmp.push_back(r4 + r3[0]);
tmp.push_back(r4 + r2[0] + r1[0]);
tmp.push_back(r4 + r1[0] + r1[1] + r1[2]);
tmp.push_back(r3[0] + r3[1] + r1[0]);
tmp.push_back(r3[0] + r2[0] + r2[1]);
tmp.push_back(r3[0] + r2[0] + r1[0] + r1[1]);
tmp.push_back(r3[0] + r1[0] + r1[1] + r1[2] + r1[3]);
tmp.push_back(r2[0] + r2[1] + r2[2] + r1[0]);
tmp.push_back(r2[0] + r2[1] + r1[0] + r1[1] + r1[2]);
tmp.push_back(r2[0] + r1[0] + r1[1] + r1[2] + r1[3] + r1[4]);
tmp.push_back(r1[0] + r1[1] + r1[2] + r1[3] + r1[4] + r1[5] + r1[6]);
sort(begin(tmp), end(tmp));
s -= tmp[0];
break;
}
}
cout << s << '\n';
}
}
Ответ: \(14432 \,\, 45978688\)