@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
  • Вопрос задан
  • 1053 просмотра
Решения вопроса 2
wataru
@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)
Ответ написан
Комментировать
@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


Если есть советы, как оптимизировать, то, пожалуйста, очень буду рад)
Ответ написан
Комментировать
Пригласить эксперта
Ответы на вопрос 1
Rsa97
@Rsa97
Для правильного вопроса надо знать половину ответа
вычитаем первую разницу и уменьшаем кол-ва чётных на единицу, а кол-во нечётных увеличиваем на единицу
Вы действуете исходя из предположения, что в паре одно число чётное, а второе нет? Это не так. В паре могут быть и два чётных и два нечётных числа.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы