Задание 27. Информатика. ЕГЭ. Поляков-2663

Просмотры: 127
Изменено: 24 ноября 2024

Имеется набор данных, состоящий из пар положительных целых чисел. Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма всех выбранных чисел делилась на \(3\) и при этом была минимально возможной. Гарантируется, что искомую сумму чисел получить можно.
Программа должна напечатать одно число — минимально возможную сумму, соответствующую условиям задачи.

Входные данные.
Даны два входных файла (файл \( A \) и файл \( B\)), каждый из которых содержит в первой строке количество пар \(N\) ( \( 1 \leqslant N \leqslant 100000\)). Каждая из следующих \( N \) строк содержит два натуральных числа, не превышающих \( 10\, 000\).
Пример организации исходных данных во входном файле:
\(6\)
\(1\,\, 3\)
\(5\,\, 11\)
\(6\,\, 9\)
\(5\,\, 4\)
\(3\,\, 3\)
\(1\,\, 1\)
Для указанных входных данных значением искомой суммы должно быть число \(21\).
В ответе укажите два числа: сначала значение искомой суммы для файла \( A \), затем для файла \( B\).

Файл с данными

Решение:

Python


fnames = ['27-3a.txt', '27-3b.txt']

for fn in fnames:
    fd = open(fn)
    N = int(fd.readline())
    s = 0
    rem1 = [10**10, 10**10]
    rem2 = 10**10

    for line in fd:
        x, y = map(int, line.split())
        s += min(x, y)
        d = abs(x - y)
        if d % 3 == 1 and rem1[1] > d:
            rem1[1] = d
            rem1.sort()
        elif d % 3 == 2:
            rem2 = min(rem2, d)

    r = s % 3

    if r == 1:
        s += min(rem2, sum(rem1))
    elif r == 2:
        s += rem1[0]

    print(s)

C++


#include<iostream>
#include<fstream>
#include<string>
#include<algorithm>

using namespace std;

int32_t main() {
    string fnames[] = {"27-3a.txt", "27-3b.txt"};

    for(string fn: fnames) {
        ifstream in(fn);

        unsigned int N, s = 0;
        in >> N;

        int rem1[2] = {100000, 100000}, rem2 = 100000;

        while (N--)
        {
            int x, y;
            in >> x >> y;

            s += min(x, y);
            int d = abs(x - y);
            if (d % 3 == 1 && d < rem1[1]) {
                rem1[1] = d;
                sort(rem1, rem1+2);
            }
            else if(d % 3 == 2) 
                rem2 = min(rem2, d);
        }

        int r = s % 3;
        if (r == 1) 
            s += min(rem2, rem1[0] + rem1[1]);
        else if (r == 2)
            s += min(rem1[0], rem1[1]);

        cout << s << '\n';
    }

}

Ответ: \(66228 \,\, 203412732\)