Файл: Федеральное государственное казенное общеобразовательное.docx

Предлагается два задания с похожими условиями: задание А и задание Б. Можно решать оба задания или одно из них по своему выбору. Задание Б более сложное, его решение оценивается выше. Итоговая оценка выставляется как максимальная из оценок за задания А и Б.

Задание А. Имеется набор данных, состоящий из 6 пар положительных целых чисел. Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма всех выбранных чисел не делилась на 3 и при этом была максимально возможной. Если получить требуемую сумму невозможно, в качестве ответа нужно выдать 0. Напишите программу для решения этой задачи. В этом варианте задания оценивается только правильность программы, время работы и размер использованной памяти не имеют значения.
Максимальная оценка за правильную программу– 2 балла.
Задание Б. Имеется набор данных, состоящий из пар положительных целых чисел. Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма всех выбранных

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

Программа считается эффективной по времени, если время работы программы пропорционально количеству пар чисел N, т.е. при увеличении N в k раз время работы

программы должно увеличиваться не более чем в k раз.

Программа считается эффективной по памяти, если размер памяти, использованной в программе для хранения данных, не зависит от числа N и не превышает 1 килобайта.

Максимальная оценка за правильную программу, эффективную по времени и памяти, – 4 балла.

Максимальная оценка за правильную программу, эффективную по времени, но неэффективную по памяти, – 3 балла.

Как в варианте А, так и в варианте Б программа должна напечатать одно число – максимально возможную сумму, соответствующую условиям задачи (или 0, если такую сумму получить нельзя).
НАПОМИНАЕМ! Не забудьте указать, к какому заданию относится каждая из представленных Вами программ.
Перед текстом программы кратко опишите Ваш алгоритм решения, укажите использованный язык программирования и его версию (например, Free Pascal 2.6.4).
Входные данные

Для варианта А на вход программе подаѐтся шесть строк, каждая из которых содержит два натуральных числа, не превышающих 10 000.

Пример входных данных для варианта А:

1 3

5 12

6 9

5 4

3 3

1 1
Для варианта Б на вход программе в первой строке подаѐтся количество пар N (1

≤ N ≤100 000). Каждая из следующих N строк содержит два натуральных числа, не превышающих 10 000.

Пример входных данных для варианта Б:

6

1 3

5 12

6 9

5 4

3 3

1 1
Пример выходных данных для приведѐнных выше примеров входных данных: 32

Разбор 27 задания ЕГЭ 2017

Задание Б.

Сначала рассмотрим решение для более общего задания (вариант Б).
Решение 1.
Чтобы получить максимально возможную сумму, будем

брать из каждой пары самое большое число. Если полученная при этом сумма будет делиться на 3, еѐ необходимо уменьшить. Для этого достаточно в одной из пар, где числа имеют разные остатки при делении на 3, заменить ранее выбранное число на другое число из той же пары. При этом разница между числами в паре должна быть минимально возможной. Если во всех парах оба числа имеют одинаковый остаток при делении на 3, получить нужную сумму невозможно.
Программа читает все данные один раз. В каждой паре определяется большее число Max и разность между большим и меньшим числами пары D. После обработки очередной пары программа хранит два числа: s – сумму всех максимальных элементов прочитанных пар и D_min – наименьшую возможную разность D, не кратную 3. Окончательным ответом будет значение s, если оно не делится на 3, и s–D_min в противном случае. Если s делится на 3, а D_min не определено (разность между числами во всех парах кратна 3), ответ в соответствии с условиями задачи считается равным 0.
Программа 1. Пример правильной и эффективной программы для задания Б на языке Паскаль.
const

aMax = 10000; {наибольшее возможное число в исходных данных} var

N: longint; {количество пар} a, b: longint; {пара чисел}

Max: longint; {максимум в паре} Min: longint; {минимум в паре}

s: longint; {сумма выбранных чисел}

D_min: longint; {минимальная разница Max-Min не кратная 3} i: longint;

begin

s := 0;

D_min := aMax + 1; readln(N);

for i := 1 to N do begin readln(a, b);

if a>b then begin Max:=a; Min:=b end else begin Max:=b; Min:=a end;

s := s + Max;

if ((Max — Min) mod 3 > 0) and (Max — Min < D_min) then D_min := Max — Min

end;

if s mod 3 = 0 then begin

if D_min > aMax then s := 0 else s := s – D_min

end; writeln(s)

end.
Решение 2.
Возможно и решение, основанное на другой идее, а именно будем хранить для каждого прочитанного набора пар три суммы (s0, s1, s2) – максимальные суммы элементов пар, имеющие при делении на 3 соответственно остатки 0, 1 и 2. При обработке очередной пары (a1, a2) эти суммы обновляются. Для этого достаточно рассмотреть суммы s0+a1, s1+a1, s2+a1, s0+a2, s1+a2, s2+a2 и для каждого возможного остатка от деления на 3 выбрать в качестве нового значения s0, s1 или s2 значение наибольшей из указанных сумм, дающей данный остаток. Окончательным ответом будет большая из сумм s1 и s2.

Эта идея приводит к более громоздкой реализации, но все основные требования по эффективности в ней выполнены, поэтому подобное решение при отсутствии ошибок можно оценить максимальным количеством баллов.
Ниже приводится пример основанной на этом принципе программы на языке Паскаль.
Программа 2. Пример правильной и эффективной программы для задания Б на языке Паскаль
var

N: longint; {количество пар}

a: array[1..2] of longint; {пара чисел} s_old, s_new: array[0..2] of longint;

{суммы с соответствующими остатками от деления на 3} i, j, k, r: longint;

begin

readln(N);

for j := 0 to 2 do s_old[j] := 0;

for i := 1 to N do begin readln(a[1], a[2]); for j := 0 to 2 do

s_new[j] := 0;

for k := 1 to 2 do begin for j := 0 to 2 do begin

if (s_old[j] > 0) or (i = 1) then begin r := (s_old[j] + a[k]) mod 3;

if s_new[r] < s_old[j] + a[k] then s_new[r] := s_old[j] + a[k]

end end

end;

s_old := s_new end;

if s_new[1] > s_new[2] then writeln(s_new[1])

else

writeln(s_new[2]);

{если решения не существует, тоs_new[1] и s_new[2] окажутся равными нулю}

end.
Задание А.
Это задание можно выполнить «в лоб»: сохранить в массиве все исходные данные, перебрать все возможные способы выбора одного элемента из каждой пары и найти максимальную сумму, соответствующую условиям задачи.

Ниже приводится пример такого решения Пример решения задачи А на языке Паскаль. var

a: array[1..6, 1..2] of longint;

i1, i2, i3, i4, i5, i6: longint; s, sMax: longint;

begin

for i1:= 1 to 6 do readln(a[i1,1], a[i1,2]); sMax := 0;

for i1:=1 to 2 do for i2:=1 to 2 do for i3:=1 to 2 do for i4:=1 to 2 do for i5:=1 to 2 do

for i6:=1 to 2 do begin s:=a[1,i1]+a[2,i2]+a[3,i3]+a[4,i4]+a[5,i5]+a[6,i6];

if (s mod 3 <> 0) and (s > sMax) then sMax := s end;

writeln(sMax) end.

Эффективность

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

Работая в группах, объясняя друг другу материал, помогая преодолеть трудности, кадеты становятся самостоятельными, ответственными за результат и отзывчивыми, что положительно сказывается на их развитии, в общем.