Вам предлагается два задания с похожими условиями: задание А и задание
Условие
Вам предлагается два задания с похожими условиями: задание А и задание Б. Вы можете решать оба задания или одно из них по своему выбору. Задание Б более сложное, его решение оценивается выше. Итоговая оценка выставляется как максимальная из оценок за задания А и Б. Задание А. Имеется набор данных, состоящий из 6 пар положительных целых чисел. Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма всех выбранных чисел не делилась на 3 и при этом была максимально возможной. Если получить требуемую сумму невозможно, в качестве ответа нужно выдать 0.Напишите программу для решения этой задачи. В этом варианте задания оценивается только правильность программы, время работы и размер использованной памяти не имеют значения.
Максимальная оценка за правильную программу - 2 балла. Задание Б. Имеется набор данных, состоящий из пар положительных целых чисел. Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма всех выбранных чисел не делилась на 3 и при этом была максимально возможной. Если получить требуемую сумму невозможно, в качестве ответа нужно выдать 0.Напишите программу для решения этой задачи.
Постарайтесь сделать программу эффективной по времени и используемой памяти (или хотя бы по одной из этих характеристик).Программа считается эффективной по времени, если время работы программы пропорционально количеству пар чисел N, т. е. при увеличении N в k раз время работы программы должно увеличиваться не более чем в k раз.
Программа считается эффективной по памяти, если размер памяти, использованной в программе для хранения данных, не зависит от числа N и не превышает 1 килобайта.
Максимальная оценка за правильную программу, эффективную по времени и памяти, — 4 балла.
Максимальная оценка за правильную программу, эффективную по времени, но неэффективную по памяти, — 3 балла. Как в варианте А, так и в варианте Б программа должна напечатать одно число — максимально возможную сумму, соответствующую условиям задачи (или 0, если такую сумму получить нельзя). НАПОМИНАЕМ! Не забудьте указать, к какому заданию относится каждая из представленных Вами программ. Перед текстом программы кратко опишите Ваш алгоритм решения, укажите использованный язык программирования и его версию (например, Free Pascal 2.6.4). Входные данныеДля варианта А на вход программе подаётся шесть строк, каждая из которых содержит два натуральных числа, не превышающих 10 000.Пример входных данных для варианта А:1 35 126 95 43 31 1 Для варианта Б на вход программе в первой строке подаётся количество пар N (1 ≤ N ≤ 100 000). Каждая из следующих N строк содержит два натуральных числа, не превышающих 10 000.Пример входных данных для варианта Б:61 35 126 95 43 31 1Пример выходных данных для приведённых выше примеров входных данных: 32
Ответ
Ответ и полный разбор откроются после входа
Посмотреть ответРешение по шагам
Как рассуждать
Решение. Задание Б. Cначала рассмотрим решение для более общего задания (вариант Б).Решение 1.Чтобы получить максимально возможную сумму, будем брать из каждой пары самое большое число. Если полученная при этом сумма будет делиться на 3, её необходимо уменьшить. Для этого достаточно в одной из пар, где числа имеют разные остатки при делении на 3, заменить ранее выбранное число на другое число из той же пары. При этом разница между числами в паре должна быть минимально возможной. Если во всех парах оба числа имеют одинаковый остаток при делении на 3, получить нужную сумму невозможно.
Замечание для эксперта. От ученика не требуется доказывать правильность предложенного алгоритма. Для удобства экспертов докажем, что при наличии решения достаточно заменить одно число. Пусть это не так, т. е. найдутся две такие пары, от которых в искомую сумму входят не бόльшие в своих парах числа x₁ и y₁, а меньшие числа из соответствующих пар: x₂ и y₂. При том x₂ + y₂ имеет остаток от деления на 3, отличный от остатка от деления на 3 числа x₁ + y₁ (иначе мы могли бы включить в сумму x₁ + y₁ вместо x₂ + y₂). Но это означает, что хотя бы одно из чисел x₂, y₂ тоже при делении на 3 имеет остаток, отличный от соответствующего максимального числа пары. Значит, оптимальной является замена только одного из таких чисел.
Программа читает все данные один раз. В каждой паре определяется большее число Max и разность между бόльшим и меньшим числами пары D. После обработки очередной пары программа хранит два числа: s — сумму всех максимальных элементов прочитанных пар и D_(min) — наименьшую возможную разность D, не кратную
Осталось ещё 7 шагов
Окончательным ответом будет значение s, если…
Пример правильной и эффективной программы для…
and (Max - Min < D_min) then D_min := Max…
При обработке очередной пары (a₁, a₂) эти…
Пример правильной и эффективной программы для…
then begin r := (s_old[j] + a[k]) mod 3; if…
and (s > sMax) then sMax := s end…
Бесплатно · займёт минуту