Вам предлагается два задания с похожими условиями: задание А и задание Б. Вы можете решать оба задания или одно из них по своему выбору. Задание Б более сложное, его решение оценивается выше. Итоговая оценка выставляется как максимальная из оценок за задания А и Б.
Задание А. Имеется набор данных, состоящий из 6 пар положительных целых чисел. Необходимо выбрать из каждой пары ровно одно число, так чтобы сумма всех выбранных чисел не делилась на 3 и при этом была максимально возможной. Если получить требуемую сумму невозможно, в качестве ответа нужно выдать 0.
Напишите программу для решения этой задачи. В этом варианте задания оценивается только правильность программы, время работы и размер использованной памяти не имеют значения.
Максимальная оценка за правильную программу – 2 балла.
Задание Б. Имеется набор данных, состоящий из пар положительных целых чисел. Необходимо выбрать из каждой пары ровно одно число, так чтобы сумма всех выбранных чисел не делилась на 3 и при этом была максимально возможной. Если получить требуемую сумму невозможно, в качестве ответа нужно выдать 0.
Напишите программу для решения этой задачи.
Постарайтесь сделать программу эффективной по времени и по используемой памяти (или хотя бы по одной из этих характеристик).
Программа считается эффективной по времени, если время работы программы пропорционально количеству пар чисел N, т.е. при увеличении N в k раз время работы программы должно увеличиваться не более чем в k раз.
Программа считается эффективной по памяти, если размер памяти, использованной в программе для хранения данных, не зависит от числа N и не превышает 1 килобайта.
Максимальная оценка за правильную программу, эффективную по времени и по памяти, – 4 балла.
Максимальная оценка за правильную программу, эффективную по времени, но не эффективную по памяти, – 3 балла.
Как в варианте А, так и в варианте Б программа должна напечатать одно число – максимально возможную сумму, соответствующую условиям задачи (или 0, если такую сумму получить нельзя).
НАПОМИНАЕМ! Не забудьте указать, к какому заданию относится каждая из представленных Вами программ.
Перед текстом программы кратко опишите Ваш алгоритм решения, укажите использованный язык программирования и его версию (например, Free Pascal 2.6.4).
Входные данные
Для варианта А на вход программе подаётся 6 строк, каждая из которых содержит два натуральных числа, не превышающих 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
Решение задания A:
ОбъяснениеДля решения задания А просто создадим двумерный массив 6 на 2 и переберем все возможные варианты.
Решение на языке Pascal
Показать решение|
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 |
var mas: array[1..6, 1..2] of word; s: word; max_s: word; begin max_s := 0; for var i := 1 to 6 do readln(mas[i, 1], mas[i, 2]); for var q := 1 to 2 do for var w := 1 to 2 do for var e := 1 to 2 do for var r := 1 to 2 do for var t := 1 to 2 do for var y := 1 to 2 do begin s := mas[1, q] + mas[2, w] + mas[3, e] + mas[4, r] + mas[5, t] + mas[6, y]; if (s mod 3 > 0) and (s > max_s) then max_s := s; end; write(max_s); end. |
Решение на языке Python
Показать решение|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
s = 0 max_s = 0 mas = [list(map(int, input().split())) for j in range(6)] for q in range(2): for w in range(2): for e in range(2): for r in range(2): for t in range(2): for y in range(2): s = mas[0][q] + mas[1][w] + mas[2][e] + mas[3][r] + mas[4][t] + mas[5][y] if s % 3 != 0 and s > max_s: max_s = s print(max_s) |
Решение задания Б:
ОбъяснениеДля решения задания Б будем брать самое большое значение из пары. Если полученная сумма делится на 3, то придется заменить один элемент в сумме на другой в его паре, так чтобы полученная сумма не делилась на 3 и была как можно больше. Создадим переменную, в которой будем хранить минимальную разность всех пар, которая не делится на 3
Решение на языке Pascal
Показать решение|
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 36 37 38 39 40 41 42 43 44 45 46 47 48 |
const valid_value = 10001; //Максимальное значение очередных переменных var N: longword; //Количество элементов min_range: word; //Минимальная разность элементов a1, a2: word; //Очередные значения k: word; //Вспомогательная переменная s: longword; //Необходимая сумма max: word; //Маскимальное число в серии (a1 или a2) min: word;//Минимальное число в серии (a1 или a2) begin min_range := valid_value; s := 0; readln(N); for var i := 1 to N do begin readln(a1, a2); if a1 > a2 then begin max := a1; min := a2; end else begin max := a2; min := a1; end; s := s + max; k := max - min; if (k mod 3 > 0) and (k < min_range) then min_range := k end; if s mod 3 = 0 then if min_range = valid_value then s := 0 else s := s - min_range; writeln(s); end. |
Решение на языке Python
Показать решение|
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 |
valid_value = 10001#Максимально возможное значениие переменных s = 0 #Сумма k = 0 #Вспомогательная переменная min_range = 10001 #Минимальная разность элементов N = int(input()) #Количество элементов for i in range(N): a1, a2 = map(int, input().split()) if a1 > a2: s += a1 else: s += a2 k = abs(a1 - a2) if k < min_range and k % 3 != 0: min_range = k if s % 3 == 0: if min_range == valid_value: s = 0 else: s -= min_range print(s) |