|
0 / 0 / 0
Регистрация: 02.05.2021
Сообщений: 10
|
||||||||
Не могу верно понять задачу из ЕГЭ по инфе. Почему ответ неверный?30.05.2021, 15:38. Показов 11763. Ответов 8
Всем привет! Написал код к следующей задачи из ЕГЭ по информатике:
считываем из строки в файле максимальное число и проверяем его чётность, после чего записываем в соответствующий счётчик. Также создаём массив из всех разниц между числами, который в последствии сортируем по возрастанию, Переходим в проверке условия задачи. Если кол-ва чётных больше нечётных, а сумма нечётна, то вычитаем первую разницу и уменьшаем кол-ва чётных на единицу, а кол-во нечётных увеличиваем на единицу. Всё это работает в цикле и пока наше условие не выполнится, то мы из не выйдем. В результате я получаю верный ответ для A, а для файла B – 36898558. Прошу Вас помочь найти ошибку и объяснить её. Прикрепляю файлы для данной задачи: A: https://inf-ege.sdamgia.ru/get_file?id=79118 B: https://inf-ege.sdamgia.ru/get_file?id=79119
0
|
||||||||
| 30.05.2021, 15:38 | |
|
Ответы с готовыми решениями:
8
Не могу понять почему выводит неверный ответ вроде не равно правильно стоит Есть код,но при запуске говорит неверный синтаксис,а я не могу понять где,вроде все верно Не могу понять почему не получается нужный ответ |
|
║XLR8║
|
||
| 30.05.2021, 16:35 | ||
|
Эффективный алгоритм ещё не придумал, но ваш подход мне не очень по душе. Интуиция подсказывает смореть в сторону ДП по массиве разниц, либо по массиву до препроцессинга. Возможные переходы ток надо продумать, станет ясно.
0
|
||
|
0 / 0 / 0
Регистрация: 02.05.2021
Сообщений: 10
|
||
| 30.05.2021, 16:52 [ТС] | ||
|
Не очень понял, что это значит:
0
|
||
|
║XLR8║
|
||
| 30.05.2021, 17:22 | ||
|
Добавлено через 28 минут Начинаться всё может с того чтобы подсчитать сумму максимальных значений для пар в которых чётность одинаковая и вычеркнуть их из списка.
0
|
||
|
0 / 0 / 0
Регистрация: 02.05.2021
Сообщений: 10
|
||||||
| 30.05.2021, 17:22 [ТС] | ||||||
|
Задача решена. Код следующий:
0
|
||||||
|
0 / 0 / 0
Регистрация: 02.05.2021
Сообщений: 10
|
||||||
| 30.05.2021, 17:45 [ТС] | ||||||
|
Упс. Спасибо, что заметили. Поправил ошибку и всё снова сломалось(
Добавлено через 11 минут Исправленная версия:
0
|
||||||
|
║XLR8║
|
|
| 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
|
|
|
8849 / 4500 / 1864
Регистрация: 27.03.2020
Сообщений: 7,316
|
||||||
| 30.05.2021, 20:08 | ||||||
|
GeloBer, если с условиями не напутал...
0
|
||||||
| 30.05.2021, 20:08 | |
|
Помогаю со студенческими работами здесь
9
не могу понять почему ответ всегда нулевой Сделал задачу, не могу понять, почему не выводит плавоющие запятые! Почему такой ответ?(ЕГЭ А6)
Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |
|
Новые блоги и статьи
|
|||
|
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 была полностью переписана на Си, в. . .
|