Определите максимальную сумму, которую можно получить при таком выборе.
Условие
Набор данных состоит из нечётного количества пар натуральных чисел. Необходимо выбрать из каждой пары ровно одно число так, чтобы чётность суммы выбранных чисел совпадала с чётностью большинства выбранных чисел и при этом сумма выбранных чисел была как можно больше. Определите максимальную сумму, которую можно получить при таком выборе. Гарантируется, что удовлетворяющий условиям выбор возможен.Входные данные.Файл AФайл BПервая строка входного файла содержит число N — общее количество пар в наборе. Каждая из следующих N строк содержит два натуральных числа, не превышающих 10 000.Пример входного файла:515 85 116 37 29 14Для указанных данных надо выбрать числа 15, 11, 6, 7 и 14. Большинство из них нечётны, сумма выбранных чисел равна 53 и тоже нечётна. В ответе надо записать число 53.Вам даны два входных файла (A и B), каждый из которых имеет описанную выше структуру. В ответе укажите два числа: сначала значение искомой суммы для файла A, затем для файла B. Предупреждение: для обработки файла B не следует использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго. Ответ:
Ответ
12118436898658
Решение по шагам
Как рассуждать
Решение. Последовательно считывая данные из файла, будем прибавлять к сумме значение максимального числа в паре, при этом, если число чётное, будем увеличивать значение переменной count0 на единицу, если нечётное — увеличивать значение переменной count1 на единицу. Поскольку может возникнуть ситуация, когда, например, получившаяся сумма будет чётной, а количество чётных чисел будет меньше количества нечётных чисел и будет отличаться от количества нечётных чисел на единицу, будем находить две минимальных разницы для ситуации, когда будет убираться два чётных числа (переменные dif3 и dif4), и две минимальных разницы для ситуации, когда будет убираться два нечётных числа (переменные dif1 и dif2). Приведём решение задачи на языке Pascal.var x, y, count0, count1: longint;n: longint;sum: longint;dif1, dif2, dif3, dif4: longint;f: text;begin assign(f,'C:\27-B.txt'); reset(f); readln(f, n); sum := 0; dif1 := 20001; dif2 := 20001; dif3 := 20001; dif4 := 20001; count0 := 0; count1 := 0; while not eof(f) do begin readln(f, x, y); if x > y then begin sum := sum + x; if x mod 2 = 0 then count0 := count0 + 1 else count1 := count1 + 1; if x mod 2 <> y mod 2 then begin if (x - y < dif1) and (x mod 2 <>
Осталось ещё 9 шагов — откроются после входа:
- Шаг 2
- Шаг 3
- Шаг 4
- Шаг 5
- Шаг 6
- Шаг 7
- Шаг 8
- Шаг 9
- Шаг 10
Бесплатно · займёт минуту