Вам предлагается два задания с похожими условиями: задание А и задание Б. Вы можете решать оба задания или одно из них по своему выбору. Задание Б более сложное, его решение оценивается выше.
Итоговая оценка выставляется как максимальная из оценок за задания А и Б.
Как в варианте А, так и в варианте Б программа должна напечатать одно число – максимально возможную сумму, соответствующую условиям задачи (или 0, если такую сумму получить нельзя).
НАПОМИНАЕМ! Не забудьте указать, к какому заданию относится каждая из представленных Вами программ.
Перед текстом программы кратко опишите Ваш алгоритм решения, укажите использованный язык программирования и его версию (например, Free Pascal 2.6.4).
Для варианта Б на вход программе в первой строке подаётся количество пар N (1 ≤ N ≤ 100 000). Каждая из следующих N строк содержит два натуральных числа, не превышающих 10 000.
Пример входных данных для варианта Б:
6
1 3
5 12
6 9
5 4
3 3
1 1
Пример выходных данных для приведённых выше примеров входных данных:
32
Решение:
Задание Б. Cначала рассмотрим решение для более общего задания (вариант Б).
Решение 1.
Чтобы получить максимально возможную сумму, будем брать из каждой пары самое большое число. Если полученная при этом сумма будет делиться на 3, её необходимо уменьшить. Для этого достаточно в одной из пар, где числа имеют разные остатки при делении на 3, заменить ранее выбранное число на другое число из той же пары. При этом разница между числами в паре должна быть минимально возможной. Если во всех парах оба числа имеют одинаковый остаток при делении на 3, получить нужную сумму
невозможно.
Замечание для эксперта. От ученика не требуется доказывать правильность предложенного алгоритма. Для удобства экспертов докажем, что при наличии решения достаточно заменить одно число. Пусть это не так,
т.е. найдутся две такие пары, от которых в искомую сумму входят не бόльшие в своих парах числа x1 и y1, а меньшие числа из соответствующих пар: x2 и y2. При этом x2 + y2 имеет остаток от деления на 3, отличный от остатка от деления на 3 числа x1 + y1 (иначе мы могли бы включить в сумму x1 + y1 вместо x2 + y2). Но это означает, что хотя бы одно из чисел x2, y2 тоже при делении на 3 имеет остаток, отличный от соответствующего максимального числа пары. Значит, оптимальной является замена только одного из таких чисел.Программа читает все данные один раз. В каждой паре определяется большее число Max и разность между бόльшим и меньшим числами пары D. После обработки очередной пары программа хранит два числа: s – сумму всех максимальных элементов прочитанных пар и D_min – наименьшую возможную разность D, не кратную 3. Окончательным ответом будет значение s, если оно не делится на 3, и s–D_min в противном случае. Если s делится на 3, а D_min не определено (разность между числами во всех парах кратна 3), ответ в соответствии с условиями задачи считается равным 0
Программа 1. Пример правильной и эффективной программы для задания Б на языке Паскаль
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
|
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. |
на языке C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35
|
#include <iostream> using namespace std; const int aMax = 10000; //наибольшее возможное число в исходных данных int main() { long N; //количество пар long a, b; //пара чисел long Max; //максимум в паре long Min; //минимум в паре long s; //сумма выбранных чисел long Dmin; //минимальная разница Max-Min не кратная 3 long i; s = 0; Dmin = aMax + 1; cin >> N; for (i = 1; i<=N; i++){ cin>>a>>b; if(a > b){ Max=a; Min=b; }else{ Max=b; Min=a; } s = s + Max; if ((Max - Min) % 3 > 0 && Max - Min < Dmin) Dmin = Max - Min; } if (s % 3 == 0){ if (Dmin > aMax) s = 0; else s = s - Dmin; } cout<<s; return 0; } |
Программа 2. Пример правильной и эффективной программы для задания Б на языке Паскаль
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34
|
const aMax = 10000; {наибольшее возможное число в исходных данных} 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. |
Замечание для эксперта. Ученик может «перестраховаться» и явно проверить, что хотя бы одно из чисел s_new[1], s_new[2] отлично от 0.
Эта проверка излишня (см. комментарий в конце программы), однако она не влияет на порядок роста времени программы. Снижать баллы за такую избыточную проверку не следует.Задание А. Это задание можно выполнить «в лоб»: сохранить в массиве все исходные данные, перебрать все возможные способы выбора одного элемента из каждой пары и найти максимальную сумму, соответствующую условиям задачи.
Ниже приводится пример такого решения
Решение 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.
Эта идея приводит к более громоздкой реализации, но все основные требования по эффективности в ней выполнены, поэтому подобное решение при отсутствии ошибок можно оценить максимальным количеством баллов.
Ниже приводится пример основанной на этом принципе программы на языке Паскаль.
Замечание для эксперта. В приведённом ниже решении для хранения s0, s1, s2 используется массив s_new[0..2]. Это упрощает реализацию, однако решение, в котором используются простые переменные, также допустимо. Не следует снижать баллы только за то, что в программе использованы простые
переменные, а не массив, как в приведённом ниже примере
Пример решения задачи А на языке Паскаль
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
|
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. |