Форум программистов, компьютерный форум, киберфорум
Python для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.93/55: Рейтинг темы: голосов - 55, средняя оценка - 4.93
0 / 0 / 0
Регистрация: 02.05.2021
Сообщений: 10

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

30.05.2021, 15:38. Показов 11763. Ответов 8

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

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

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

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:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
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
0
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
30.05.2021, 15:38
Ответы с готовыми решениями:

Не могу понять почему выводит неверный ответ вроде не равно правильно стоит
f = open('17 (1).txt') a = list(map(int, f.readlines())) s = 0 m = -1 for i in range(len(a) - 1): for j in range(i + 1,...

Есть код,но при запуске говорит неверный синтаксис,а я не могу понять где,вроде все верно
есть код,но при запуске говорит неверный синтаксис,а я не могу понять где,вроде все верно import os try: os.makedirs('folder') ...

Не могу понять почему не получается нужный ответ
#include <iostream> #include <vector> #include <cmath> #define M_PI 3.14159265358979323846 using namespace std; double...

8
║XLR8║
 Аватар для outoftime
1212 / 909 / 270
Регистрация: 25.07.2009
Сообщений: 4,360
Записей в блоге: 5
30.05.2021, 16:35
Цитата Сообщение от GeloBer Посмотреть сообщение
найти ошибку и объяснить её
У вас не предусмотрен вариант когда надо не минимальную разницу отнимать от суммы. Т.е. надо из массива разниц выбирать не индексы 1, 2, 3 и т.д., а 1 и 3 без 2 или 2 и 3 без 1.

Эффективный алгоритм ещё не придумал, но ваш подход мне не очень по душе. Интуиция подсказывает смореть в сторону ДП по массиве разниц, либо по массиву до препроцессинга. Возможные переходы ток надо продумать, станет ясно.
0
0 / 0 / 0
Регистрация: 02.05.2021
Сообщений: 10
30.05.2021, 16:52  [ТС]
Не очень понял, что это значит:
Т.е. надо из массива разниц выбирать не индексы 1, 2, 3 и т.д., а 1 и 3 без 2 или 2 и 3 без 1.
Можете объяснить?
0
║XLR8║
 Аватар для outoftime
1212 / 909 / 270
Регистрация: 25.07.2009
Сообщений: 4,360
Записей в блоге: 5
30.05.2021, 17:22
Цитата Сообщение от GeloBer Посмотреть сообщение
Можете объяснить?
У тебя ответ на 100 ниже, ты лишнее отнимаешь. Я алгоритм ещё не придумал.

Добавлено через 28 минут
Начинаться всё может с того чтобы подсчитать сумму максимальных значений для пар в которых чётность одинаковая и вычеркнуть их из списка.
0
0 / 0 / 0
Регистрация: 02.05.2021
Сообщений: 10
30.05.2021, 17:22  [ТС]
Задача решена. Код следующий:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
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
        a, b = numbers_array
        if a % 2 == b % 2:
            diff_parity_more_less_array.append([abs(a - b), '00'])
        else:
            if a % 2 == 0:
                diff_parity_more_less_array.append([abs(a - b), '01'])
            else:
                diff_parity_more_less_array.append([abs(a - b), '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
Если есть советы по оптимизации, то, пожалуйста, буду очень рад)
0
║XLR8║
 Аватар для outoftime
1212 / 909 / 270
Регистрация: 25.07.2009
Сообщений: 4,360
Записей в блоге: 5
30.05.2021, 17:32
Лучший ответ Сообщение было отмечено GeloBer как решение

Решение

Цитата Сообщение от GeloBer Посмотреть сообщение
if a % 2 == 0:
                diff_parity_more_less_array.append([abs(a - b), '01'])
            else:
                diff_parity_more_less_array.append([abs(a - b), '01'])
зачем условие если выполняется одно и то же?
0
0 / 0 / 0
Регистрация: 02.05.2021
Сообщений: 10
30.05.2021, 17:45  [ТС]
Упс. Спасибо, что заметили. Поправил ошибку и всё снова сломалось(

Добавлено через 11 минут
Исправленная версия:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
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
0
║XLR8║
 Аватар для outoftime
1212 / 909 / 270
Регистрация: 25.07.2009
Сообщений: 4,360
Записей в блоге: 5
30.05.2021, 18:58
Лучший ответ Сообщение было отмечено GeloBer как решение

Решение

GeloBer, 1. Подсчитываем сумму максимальных значений для пар, у которых чётность одинаковая и формируем список пар где чётность отличается.

Так как в некоторых парах чётность не отличается, смысла брать меньшее значение нет никакого, как и принимать их во внимание при дальшених расчётах.

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

Что у нас имеется на данный момент: список пар значнеий в которых чётность отличается, максимально возможная сумма, её чётность, а также количество чётных (Ч) и нечётных (НЧ) элементов в ней.

Если у нас сумма чётная и чётных эллементов больше чем нечётных - мы нашли ответ.
Если у нас сумма чётная и чётных эллементов меньше либо равно нечётных - нужно модифицировать сумму.
Если у нас сумма нечётная и нечётных эллементов больше чем чётных - мы нашли ответ.
Если у нас сумма нечётная и нечётных эллементов меньше либо равно чётных - нужно модифицировать сумму.

Так как у нас остались пары с разной чётностью вида (a, b), замена одного другим (при подсчёте суммы) это изменение чётности суммы (увеличение количества Ч не меняет чётность суммы, но каждое НЧ меняет чётность суммы один раз а мы либо делаем +НЧ либо -HЧ, т.е. меняем чётность суммы один раз.)

2. Рассмотрим вариант когда у нас сумма чётная (если мы не нашли ответ).

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

Можем получить либо неравенство Ч+1 ? НЧ-1, либо Ч-1 ? НЧ+1. Может оказаться так что мы будем прыгать туда-сюда до конца ибо изменние взятого значения в паре изменяет парность суммы, но как оно влияет на соотношение Ч к НЧ нельзя скзаать не посмотрев на конкретные значения.

Если количество НЧ до смены было на 3 больше Ч, тогда при любом раскладе мы переходим к НЧ сумме и количество НЧ > Ч (Если НЧ = Ч+3, тогда НЧ-1 > Ч+1 => Ч+3-1 > Ч+1 => Ч+2 > Ч+1), т.е. мы получаем ответ.

Если количество НЧ = Ч + 2.
Если количество НЧ = Ч + 1.
Если количество НЧ = Ч.

Здесь вся соль, на этих 3х случаях. Если следовать жадному алгоритму нужно иметь строгое доказательство что выбранный алгоритм действия является оптимальным. Я, пожалуй, не возьмусь, ибо это больше на ДП похоже, прям сильно. Задачей "лестница" попахивает. Мы на каждый шаг меняем чётность суммы, сумму нужно максимизивароть, но мы можем взять сейчас минимальную разницу, а можем взять не минимальную разницу в паре но так чтобы сразу получить ответ, т.е. чтобы HЧ было больше Ч после перехода к НЧ сумме.

Отсюда делаю вывод что запускать рекурсию имеет смысл до предела, который можно вычислить на этом шаге - сумма которую можно получить уже сейчас либо -1 (если такую найти нельзя).

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

Если НЧ = Ч + 1, найдя такую же пару получим НЧ+1 ? Ч-1 => (Ч+1)+1 ? Ч-1, т.е. НЧ станет больше Ч, и мы найдём ответ.
Если мы возьмём пару где НЧ меняется на Ч, тогда НЧ-1 ? Ч+1 => (Ч+1)-1 ? Ч+1 => Ч ? Ч+1, т.е. НЧ станет меньше и мы ответа не найдём, такую пару брать нельзя для поиска ответа в 1 ход.

Если НЧ = Ч + 2, если мы найдём пару где Ч меняется на НЧ, НЧ+1 > Ч-1, если НЧ менять на Ч, получим равенство которое не даёт ответ.

В этих 3х случая общее:
* если можем поменять Ч на НЧ, можем получит ответ в один ход, но не факт что он даст максимальную сумму.
* если поменять НЧ на Ч, нужно будет делать ещё одну итерацию.

Как определить оптимальный поиск, в такой, можно сказать рекурсивной зависимости, пока, не вижу. (полагаю нужндо дальше варианты расписать, и оно само всплывёт)

Симметрично с нечётной суммой.
1
Эксперт Python
8849 / 4500 / 1864
Регистрация: 27.03.2020
Сообщений: 7,316
30.05.2021, 20:08
GeloBer, если с условиями не напутал...
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
with open('27-B.txt') as f:
    count_row = int(f.readline())
    count_eo = total_sum = 0
    diff_01, diff_10 = [], []
 
    for row in range(count_row):
        a, b = map(int, f.readline().split())
        if a > b:
            a, b = b, a
        total_sum += b
        count_eo += 1 - 2 * (b%2)
        if (a+b)%2:
            if b%2:
                diff_01.append(b-a)
            else:
                diff_10.append(b-a)
 
if total_sum%2 == 0 and count_eo<0:
    total_sum -= min(min(diff_10),
     sum(sorted(diff_01)[:1-count_eo]))
     
elif total_sum%2 and count_eo>0:
    total_sum -= min(min(diff_01),
     sum(sorted(diff_10)[:count_eo+1]))
     
elif count_eo == 0:
    
    if total_sum%2:
        total_sum -= min(min(diff_01),
         sum(sorted(diff_10)[:2]))
         
    else:
        if diff_11:
            total_sum -= min(min(diff_10),
                 sum(sorted(diff_01)[:2]))
        
print(total_sum)
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
30.05.2021, 20:08
Помогаю со студенческими работами здесь

не могу понять почему ответ всегда нулевой
#include &lt;stdio.h&gt; #include &lt;conio.h&gt; #include &lt;math.h&gt; void gauss(int mm,int n,float e,float r); void slag(int mm,int n,float f); ...

Сделал задачу, не могу понять, почему не выводит плавоющие запятые!
Условия задачи: Составить программу, которая будет вычислять следующую последовательность y= 1+ 1/2 + 1/3 + 1/4 + ... 1/n (Если кому...

Почему такой ответ?(ЕГЭ А6)
Всем здравствуйте! Делал демо 2013, там 6 задание части А. Решить решила, но ответ не правильный я не могу понять почему? Задание. ...

Задача из егэ по инфе номер 27
Здравствуйте, подскажите алгоритм решения задачи. Имеется набор данных, состоящий из N различных положительных чисел. Необходимо из этих...

№ 12 ЕГЭ. Почему программа зациклилась? Долго не выдаёт ответ
s='1'*95 + '7'*31 while '1111' in s: s.replace('1111','7') s.replace('77','1') print(s) (А.М. Кабанов)...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
9
Ответ Создать тему
Новые блоги и статьи
SDL3 для Web (WebAssembly): Работа со звуком через SDL3_mixer
8Observer8 08.02.2026
Содержание блога Пошагово создадим проект для загрузки звукового файла и воспроизведения звука с помощью библиотеки SDL3_mixer. Звук будет воспроизводиться по клику мышки по холсту на Desktop и по. . .
SDL3 для Web (WebAssembly): Основы отладки веб-приложений на SDL3 по USB и Wi-Fi, запущенных в браузере мобильных устройств
8Observer8 07.02.2026
Содержание блога Браузер Chrome имеет средства для отладки мобильных веб-приложений по USB. В этой пошаговой инструкции ограничимся работой с консолью. Вывод в консоль - это часть процесса. . .
SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве
8Observer8 02.02.2026
Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .
Философия технологии
iceja 01.02.2026
На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .
SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf
8Observer8 01.02.2026
Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .
SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли
8Observer8 30.01.2026
Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm
8Observer8 30.01.2026
Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .
SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров
8Observer8 29.01.2026
Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru