Не могу верно решить задачу из ЕГЭ по инфе. Почему ответ неверный?

Question

[GeloBer]

Написал код к следующей задачи из ЕГЭ по информатике:

Набор данных состоит из нечётного количества пар натуральных чисел. Необходимо выбрать из каждой пары ровно одно число так, чтобы чётность суммы выбранных чисел совпадала с чётностью большинства выбранных чисел и при этом сумма выбранных чисел была как можно больше. Определите максимальную сумму, которую можно получить при таком выборе. Гарантируется, что удовлетворяющий условиям выбор возможен.

Пример входного файла:

5
15 8
5 11
6 3
7 2
9 14

Для указанных данных надо выбрать числа 15, 11, 6, 7 и 14. Большинство из них нечётны, сумма выбранных чисел равна 53 и тоже нечётна. В ответе надо записать число 53.

Вам даны два входных файла (A и B), каждый из которых имеет описанную выше структуру. В ответе укажите два числа: сначала значение искомой суммы для файла A, затем для файла B.

Ответы на эту задачу следующие:

A — 121184
B — 36898658.

Написал следующий код на python:

with open('27-B.txt') as f:
    count_row = int(f.readline())
    count_even, count_odd, total_sum = 0, 0, 0
    diff_array = []
    for row in range(count_row):
        a, b = map(int, f.readline().split())
        max_number = max(a, b)
        if max_number % 2 == 0:
            count_even += 1
        else:
            count_odd += 1
        total_sum += max_number
        diff_array.append(abs(a - b))

diff_array = sorted(diff_array)
i = 0
while True:
    if count_even > count_odd and total_sum % 2 != 0:
        count_even -= 1
        count_odd += 1
        total_sum -= diff_array[i]
    elif count_odd > count_even and total_sum % 2 == 0:
        count_even += 1
        count_odd -= 1
        total_sum -= diff_array[i]
    else:
        print(total_sum)
        break
    i += 1

Алгоритм для задачи, который я придумал, работает следующим образом:
считываем из строки в файле максимальное число и проверяем его чётность, после чего записываем в соответствующий счётчик. Также создаём массив из всех разниц между числами, который в последствии сортируем по возрастанию, Переходим в проверке условия задачи. Если кол-ва чётных больше нечётных, а сумма нечётна, то вычитаем первую разницу и уменьшаем кол-ва чётных на единицу, а кол-во нечётных увеличиваем на единицу. Всё это работает в цикле и пока наше условие не выполнится, то мы из не выйдем.

В результате я получаю верный ответ для A, а для файла B – 36898558.

Прошу вас помочь найти ошибку и объяснить её.

Прикрепляю файлы для данной задачи:
A: https://inf-ege.sdamgia.ru/get_file?id=79118
B: https://inf-ege.sdamgia.ru/get_file?id=79119

Comments

[V Sh.]

У меня в тестовом задании получилась сумма 55 (5, 15, 11, 3, 7, 14). Сумма нечетная и большинство выбранных чисел нечетные. Можете пояснить, где я ошибся?

Answer 1

[Wataru]

Тут вам повезло. Вы какую-то жадность сделали, но она в общем случае несработает.

Надо делать динамическое программирование:

F(n, k) - максимальная сумма, которую можно получить, взяв какие-то числа из первых n пар и при этом получить k нечетных чисел.

F(0,0) = 0

F(0,*) = -infinity

F(n,k) = max_i=0..1 a[n-1][i]+F(n-1,k-a[n-1][i]%2).

Ответ: max_i=0..n: F(n,i) (т.ч. F(n,i) - той же четно для i<=n//2 и нечетно для i > n//2)

Answer 2

[GeloBer]

Задача решена. Код:

with open('27-B.txt') as f:
    count_row = int(f.readline())
    count_even, count_odd, total_sum = 0, 0, 0
    diff_parity_more_less_array = []  # [разница; 10 – разной чётности при большем чётном, 01 – разной чётности при большем нечётном, 00 – одинаковой чётности]
    for row in range(count_row):
        numbers_array = sorted(list(map(int, f.readline().split())))
        max_number = numbers_array[1]
        if max_number % 2 == 0:
            count_even += 1
        else:
            count_odd += 1
        total_sum += max_number
        if (numbers_array[0] + numbers_array[1]) % 2 == 0:
            diff_parity_more_less_array.append([abs(numbers_array[0] - numbers_array[1]), '00'])
        else:
            if numbers_array[1] % 2 == 0:
                diff_parity_more_less_array.append([abs(numbers_array[0] - numbers_array[1]), '10'])
            else:
                diff_parity_more_less_array.append([abs(numbers_array[0] - numbers_array[1]), '01'])

diff_parity_more_less_array = sorted(diff_parity_more_less_array)
i = 0
while True:
    if count_even > count_odd and total_sum % 2 != 0 or count_odd > count_even and total_sum % 2 == 0:
        total_sum -= diff_parity_more_less_array[i][0]
        if diff_parity_more_less_array[i][1] == '01':
            count_even += 1
            count_odd -= 1
        elif diff_parity_more_less_array[i][1] == '10':
            count_even -= 1
            count_odd += 1
    else:
        print(total_sum)
        break
    i += 1

Если есть советы, как оптимизировать, то, пожалуйста, очень буду рад)

Answer 3

[Rsa97]

вычитаем первую разницу и уменьшаем кол-ва чётных на единицу, а кол-во нечётных увеличиваем на единицу

Вы действуете исходя из предположения, что в паре одно число чётное, а второе нет? Это не так. В паре могут быть и два чётных и два нечётных числа.

Comments

[GeloBer]

Действительно, об этом я не подумал.

[GeloBer]

Переписал код следующим образом. Теперь цикл стал бесконечным.

with open('27-B.txt') as f:
    count_row = int(f.readline())
    count_even, count_odd, total_sum = 0, 0, 0
    diff_parity_array = []  # 0, если числа разной чётности; 1 – одинаковой чётности
    for row in range(count_row):
        a, b = map(int, f.readline().split())
        max_number = max(a, b)
        if max_number % 2 == 0:
            count_even += 1
        else:
            count_odd += 1
        total_sum += max_number
        if a % 2 == b % 2:
            diff_parity_array.append([abs(a - b), 1])
        else:
            diff_parity_array.append([abs(a - b), 0])

diff_parity_array = sorted(diff_parity_array)
i = 0
while True:
    if count_even > count_odd and total_sum % 2 != 0:
        total_sum -= diff_parity_array[i][0]
        if diff_parity_array[i][1] == 0:
            count_even -= 1
            count_odd += 1
    elif count_odd > count_even and total_sum % 2 == 0:
        total_sum -= diff_parity_array[i][0]
        if diff_parity_array[i][1] == 0:
            count_even += 1
            count_odd -= 1
    else:
        print(total_sum)
        break
    i += 1

[Rsa97]

GeloBer, Хотя, не всё так просто, как кажется.
Если у нас нечётных чисел на два или более больше чем чётных либо чётных на два или более больше, чем нечётных, то всё просто, достаточно одной замены с минимальной разностью.
Если же нечётных на одно больше, чем чётных, то надо либо одну замену с чётного на нечётное, либо две замены с нечётного на чётное, смотря что даст меньшую дельту.
Ну и зеркально, если чётных на одно больше, чем нечётных.