РЕШУ ЕГЭ — информатика

Задания

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

Входные данные.

Файл A

Файл B

Первая строка входного файла содержит число N  — общее количество пар в наборе. Каждая из следующих N строк содержит два натуральных числа, не превышающих 10 000.

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

15 8

5 11

6 3

7 2

9 14

Для указанных данных надо выбрать числа 8, 5, 3, 2 и 9. Большинство из них нечётны, сумма выбранных чисел равна 27 и тоже нечётна. В ответе надо записать число 27.

Вам даны два входных файла (A и B), каждый из которых имеет описанную выше структуру. В ответе укажите два числа: сначала значение искомой суммы для файла A, затем для файла B.

Предупреждение: для обработки файла B не следует использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.

Ответ:

Решение. Последовательно считывая данные из файла, будем прибавлять к сумме значение минимального числа в паре, при этом, если число чётное, будем увеличивать значение переменной 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 (y - x < dif1) and (y mod 2 <> 0) then begin
                    dif2 := dif1;
                    dif1 := y - x;
                end 
                else if (y - x < dif2) and (y mod 2 <> 0) then
                    dif2 := y - x;
                if (y - x < dif3) and (y mod 2 = 0) then begin
                    dif4 := dif3;
                    dif3 := y - x;
                end
                else if (y - x < dif4) and (y mod 2 = 0) then
                    dif4 := y - x;
            end;
        end
        else begin
            if y mod 2 = 0 then count0 := count0 + 1
            else count1 := count1 + 1;
            sum := sum + y;
            if x mod 2 <> y mod 2 then begin
                if (x - y < dif1) and (x mod 2 <> 0) then begin
                    dif2 := dif1;
                    dif1 := x - y;
                end 
                else if (x - y < dif2) and (x mod 2 <> 0) then
                    dif2 := x - y;
                if (x - y < dif3) and (x mod 2 = 0) then begin
                    dif4 := dif3;
                    dif3 := x - y;
                end
                else if (x - y < dif4) and (x mod 2 = 0) then
                    dif4 := x - y;
            end;
        end;
    end;
    if (count1 > count0) then begin
        if sum mod 2 = 1 then
            writeln(sum)
        else if dif1 <= dif3 then
            writeln(sum + dif1)
        else if (count1 - count0) <> 1 then
            writeln(sum + dif3)
        else if (dif3 + dif4) < dif1 then
            writeln(sum + dif3 + dif4)
        else writeln(sum + dif1)
    end
    else begin
        if sum mod 2 = 0 then
            writeln(sum)
        else if dif3 <= dif1 then
            writeln(sum + dif3)
        else if (count0 - count1) <> 1 then
            writeln(sum + dif1)
        else if (dif1 + dif2) < dif3 then
            writeln(sum + dif1 + dif2)
        else writeln(sum + dif3)
    end;
end.

В результате работы данного алгоритма при вводе данных из файла A ответ  — 61772, из файла B  — 18484085.

Примечание.

Путь к файлу необходимо указать согласно расположению файла на Вашем компьютере.

Приведём решение на языке Python.

f = open("27-B (3).txt")

s = f.readlines()

n = int(s[0])

sum = 0

dif1 = 20001

dif2 = 20001

dif3 = 20001

dif4 = 20001

count0 = 0

count1 = 0

for i in range(1, n + 1):

x, y = map(int, s[i].split())

if x < y:

sum = sum + x

if x % 2 == 0: count0 = count0 + 1

else: count1 = count1 + 1

if x % 2 != y % 2:

if (y - x < dif1) and (y % 2 != 0):

dif2 = dif1

dif1 = y - x

elif (y - x < dif2) and (y % 2 != 0): dif2 = y - x

if (y - x < dif3) and (y % 2 == 0):

dif4 = dif3

dif3 = y - x

elif (y - x < dif4) and (y % 2 == 0):

dif4 = y - x

else:

if y % 2 == 0: count0 = count0 + 1

else: count1 = count1 + 1

sum = sum + y

if x % 2 != y % 2:

if (x - y < dif1) and (x % 2 != 0):

dif2 = dif1

dif1 = x - y

elif (x - y < dif2) and (x % 2 != 0):

dif2 = x - y

if (x - y < dif3) and (x % 2 == 0):

dif4 = dif3

dif3 = x - y

elif (x - y < dif4) and (x % 2 == 0):

dif4 = x - y

if count1 > count0:

if sum % 2 == 1:

print(sum)

elif dif1 <= dif3:

print(sum + dif1)

elif (count1 - count0) != 1:

print(sum + dif3)

elif (dif3 + dif4) < dif1:

print(sum + dif3 + dif4)

else: print(sum + dif1)

else:

if sum % 2 == 0:

print(sum)

elif dif3 <= dif1:

print(sum + dif3)

elif (count0 - count1) != 1:

print(sum + dif1)

elif (dif1 + dif2) < dif3:

print(sum + dif1 + dif2)

else: print(sum + dif3)

№ п/п	№ задания	Ответ
1	33772	61772 18484085

Ключ