Задание 27. Информатика. ЕГЭ. Поляков-2661
- Просмотры: 101
- Изменено: 24 ноября 2024
Имеется набор данных, состоящий из пар положительных целых чисел. Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма всех выбранных чисел не делилась на \(3\) и при этом была минимально возможной. Гарантируется, что искомую сумму чисел получить можно.
Программа должна напечатать одно число — минимально возможную сумму, соответствующую условиям задачи.
Входные данные.
Даны два входных файла (файл \( A \) и файл \( B\)), каждый из которых содержит в первой строке количество пар \(N\) ( \( 1 \leqslant N \leqslant 100000\)). Каждая из следующих \( N \) строк содержит два натуральных числа, не превышающих \( 10\, 000\).
Пример организации исходных данных во входном файле:
\(6\)
\(1\,\, 3\)
\(5\,\, 12\)
\(6\,\, 9\)
\(5\,\, 4\)
\(3\,\, 3\)
\(1\,\, 1\)
Для указанных входных данных значением искомой суммы должно быть число \(20\).
В ответе укажите два числа: сначала значение искомой суммы для файла \( A \), затем для файла \( B\).
Предупреждение: для обработки файла \( B \) не следует использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.
Решение:
Python
fnames = ['27-1a.txt', '27-1b.txt']
for fn in fnames:
fd = open(fn)
n = int(fd.readline())
s = 0
min_diff = 10**10
for line in fd:
a, b = map(int, line.split())
s += min(a, b)
if (abs(a - b)):
min_diff = min(min_diff, abs(a - b))
if s % 3 == 0:
s += min_diff
print(s)
C++
#include<iostream>
#include<fstream>
#include<string>
using namespace std;
int32_t main() {
const string fname[] = {"27-1a.txt", "27-1b.txt"};
for(string st: fname) {
ifstream in(st);
unsigned int n;
unsigned long long sum = 0;
unsigned int min_diff = 100000;
in >> n;
while(n--) {
int a, b;
in >> a >> b;
sum += min(a, b);
unsigned int tmp = abs(a - b);
if (tmp % 3)
min_diff = min(min_diff, tmp);
}
if(sum % 3 == 0)
sum += min_diff;
cout << sum << endl;
in.close();
}
}
Ответ: \(67303 \,\, 200157496\)