Задание 27. Информатика. ЕГЭ. Поляков-2664
- Просмотры: 70
- Изменено: 25 ноября 2024
Имеется набор данных, состоящий из пар положительных целых чисел. Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма всех выбранных чисел делилась на \(5\) и при этом была максимально возможной. Гарантируется, что искомую сумму чисел получить можно.
Программа должна напечатать одно число — максимально возможную сумму, соответствующую условиям задачи.
Входные данные.
Даны два входных файла (файл \( A \) и файл \( B\)), каждый из которых содержит в первой строке количество пар \(N\) ( \( 1 \leqslant N \leqslant 100000\)). Каждая из следующих \( N \) строк содержит два натуральных числа, не превышающих \( 10\, 000\).
Пример организации исходных данных во входном файле:
\(6\)
\(1\,\, 3\)
\(5\,\, 11\)
\(6\,\, 9\)
\(5\,\, 4\)
\(3\,\, 3\)
\(1\,\, 1\)
Для указанных входных данных значением искомой суммы должно быть число \(30\).
В ответе укажите два числа: сначала значение искомой суммы для файла \( A \), затем для файла \( B\).
Решение:
C++
#include<iostream>
#include<fstream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
int32_t main() {
string filenames[] = {"27-4a.txt", "27-4b.txt"};
for(string fn: filenames) {
ifstream in(fn);
int N, s = 0;
int r1[4] = {100000, 100000, 100000, 100000}, r2[2] = {100000, 100000}, r3 = 100000, r4 = 100000;
in >> N;
while(N--) {
int x, y;
in >> x >> y;
s += max(x, y);
int d = abs(x - y);
if (d % 5 == 1) {
r1[3] = min(r1[3], d);
sort(r1, r1+4);
}
else if (d % 5 == 2) {
r2[1] = min(r2[1], d);
sort(r2, r2+2);
}
else if (d % 5 == 3)
{
r3 = min(r3, d);
}
else if (d % 5 == 4)
{
r4 = min(r4, d);
}
}
int r = s % 5;
vector<int> v;
if (r == 1) {
s -= r1[0];
}
else if (r == 2)
{
s -= min(r1[0] + r1[1], r2[0]);
}
else if (r == 3)
{
v.push_back(r1[0] + r1[1] + r1[2]);
v.push_back(r2[0] + r1[0]);
v.push_back(r3);
s -= *min_element(v.begin(), v.end());
}
else if (r == 4)
{
v.push_back(r1[0]+ r1[1] + r1[2] + r1[3]);
v.push_back(r1[0] + r1[1] + r2[0]);
v.push_back(r2[0] + r2[1]);
v.push_back(r3 + r1[0]);
v.push_back(r4);
s -= *min_element(v.begin(), v.end());
}
cout << s << '\n';
}
}
Ответ: \(123720 \,\, 402332230\)