На вход даны пары чисел. Нужно выбрать из каждой пары по одному числу так, чтобы сумма всех выбранных чисел не была кратна 6 и при этом была минимально возможной. Напишите программу, выводящую такую сумму на экран. Если же ее невозможно получить, выведите 0.
Вам предлагается два задания, связанных с этой задачей: задание А и задание Б. Вы можете решать оба задания или одно из них по своему выбору. Итоговая оценка выставляется как максимальная из оценок за задания А и Б. Если решение одного из заданий не представлено, то считается, что оценка за это задание — 0 баллов.
Задание Б является усложнённым вариантом задания А, оно содержит дополнительные требования к программе.
А. Напишите на любом языке программирования программу для решения поставленной задачи, в которой входные данные будут запоминаться в массиве. Перед программой укажите версию языка программирования.
Обязательно укажите, что программа является решением задания А. Максимальная оценка за выполнение задания А — 2 балла.
Б. Напишите программу для решения поставленной задачи, которая будет эффективна как по времени, так и по памяти (или хотя бы по одной из этих характеристик). Программа считается эффективной по времени, если время работы программы пропорционально количеству полученных показаний прибора N, т. е. при увеличении N в k раз время работы программы должно увеличиваться не более чем в k раз. Программа считается эффективной по памяти, если размер памяти, использованной в программе для хранения данных, не зависит от числа N и не превышает 1 килобайта.
Перед программой укажите версию языка программирования и кратко опишите использованный алгоритм.
Обязательно укажите, что программа является решением задания Б. Максимальная оценка за правильную программу, эффективную по времени и по памяти, — 4 балла.
Максимальная оценка за правильную программу, эффективную по времени, но неэффективную по памяти, — 3 балла.
Напоминаем! Не забудьте указать, к какому заданию относится каждая из представленных Вами программ.
Задача А. Количество пар известно заранее и равно 6. Числа не превышают 30 000.
Пример входных данных:
5 4
3 2
1 1
18 3
11 12
2 5
Пример выходных данных:
23
Задача Б. Количество пар N не известно заранее и может принимать значения 2 <= N <= 200 000. На вход подается сначала количество пар, затем сами пары. Числа по модулю не превышают 30 000.
Пример входных данных:
6
5 4
3 2
1 1
18 3
11 12
2 5
Пример выходных данных:
23
Задание А.
Пример программы написанной на Python 3.3.
a=[] sum=600001 for i in range(6): a.append(list(map(int, input().split()))) for i in range (2): for j in range (2): for k in range (2): for l in range (2): for m in range (2): for n in range (2): if a[1][i]+a[2][j]+a[3][k]+a[4][l]+a[5][m]+a[0][n] < sum and (a[1][i]+a[2][j]+a[3][k]+a[4][l]+a[5][m]+a[0][n])%6!=0: sum=a[1][i]+a[2][j]+a[3][k]+a[4][l]+a[5][m]+a[0][n] if sum==600001: print(0) else: print(sum)
Задание А.
Пример программы написанной на Паскаль ABC.
vara: array[1..6, 1..2] of integer; {исходные данные}
sum: integer; {минимальная сумма}
i, j, k, l, m, n: integer;
begin
sum := 600001;
for i := 1 to 6 do read(a[i,1], a[i, 2]);
for i := 1 to 2 do
for j := 1 to 2 do
for k := 1 to 2 do
for l := 1 to 2 do
for m := 1 to 2 do
for n := 1 to 2 do
if (a[1, i] + a[2, j] + a[3, k] + a[4, l] + a[5, m] + a[6, n] < sum) and
((a[1, i] + a[2, j] + a[3, k] + a[4, l] + a[5, m] + a[6, n]) mod 6 <> 0) then
sum := a[1, i] + a[2, j] + a[3, k] + a[4, l] + a[5, m] + a[6, n];
if sum = 600001 then
writeln(0)
else writeln(sum);
end.
Задание Б.
Выберем из каждой пары минимальное число и сложим эти числа: данная сумма будет минимальной возможной. Если она не будет кратна 6, то это и есть требуемая сумма и её надо вывести. Иначе из какой-то пары придётся взять не минимальное, а максимальное число. Найдём минимальную разность между числами одной пары, не кратную 6. Если такая существует, то, сложив её с минимальной суммой, получим минимально возможную сумму не кратную 6, а если её нет (то есть между числами пары пары разность всегда кратна 6), то любая сумма будет кратна 6, и мы выведем 0.
Пример программы написанной на PascalABC.NET
var i, n, x, y, sum, min_r: longint; begin readln(n); min_r:=30001; sum:=0; for i:=1 to n do begin read(x); read(y); if x < y then sum:=sum+x else sum:= sum + y; if (abs(x - y) mod 6 <> 0) and (abs(x - y) < min_r) then min_r:= abs(x - y); end; if sum mod 6 <> 0 then writeln(sum) else if (sum mod 6 = 0) and (min_r < 30001) then writeln (sum + min_r) else writeln(0); end.