Задание №27 ЕГЭ Информатика с ответом и решением
Ответ: 8759 3077 10000 9996
Условие
Дана последовательность N целых положительных чисел. Рассматриваются все пары элементов последовательности, разность которых чётна, и в этих парах, по крайней мере, одно из чисел пары делится на 17. Порядок элементов в паре неважен. Среди всех таких пар нужно найти и вывести пару с максимальной суммой элементов. Если одинаковую максимальную сумму имеет несколько пар, можно вывести любую из них. Если подходящих пар в последовательности нет, нужно вывести два нуля.
Входные данные.
Файл A
Файл B
В первой строке входных данных задаётся количество чисел N (2 ≤ N ≤ 10 000). В каждой из последующих N строк записано одно натуральное число, не превышающее 10 000.
Пример организации исходных данных во входном файле:
5
34
12
51
52
51
Пример выходных данных для приведённого выше примера входных данных:
51 51 В ответе укажите четыре числа: сначала значение искомой пары для файла А (два числа через пробел), затем для файла B (два числа через пробел). Числа пар впишите в порядке убывания.
Подсказки — как подойти к решению
- Файл обрабатывай программой, а не вручную, и храни не всю последовательность, а лучшие найденные значения по нужным категориям.
- Условие на пару состоит из двух независимых признаков: разность должна быть чётной, то есть числа имеют одинаковую чётность, и хотя бы одно число пары делится на 17. Разложи элементы по этим признакам и держи в каждой категории максимум.
- Осталось перебрать допустимые комбинации категорий и выбрать пару с наибольшей суммой. Следи, чтобы в пару не попал один и тот же элемент дважды, и не забудь про требуемый порядок записи чисел.
Решение
Приведём решение задачи на языке Pascal.
var
N: integer;
a: integer;
i: integer;
max: array [0..1] of integer;
max17: array [0..1] of integer;
f: text;
begin
max[0] := 0;
max[1] := 0;
max17[0] := 0;
max17[1] := 0;
assign(f,'27991_A.txt');
reset(f);
readln(f, n);
for i := 1 to n do begin
readln(f, a);
if (a mod 17 = 0) and (a mod 2 = 0) and (a >= max17[0]) then begin
if max17[0] > max[0] then max[0] := max17[0];
max17[0] := a;
end
else if (a mod 17 = 0) and (a mod 2 = 1) and (a >= max17[1]) then begin
if max17[1] > max[1] then max[1] := max17[1];
max17[1] := a;
end
else if (a mod 17 > 0) and (a mod 2 = 0) and (a > max[0]) then max[0] := a
else if (a mod 17 > 0) and (a mod 2 = 1) and (a > max[1]) then max[1] := a;
end;
if (max[0] = 0) or (max17[0] = 0) then begin
max[0] := 0;
max17[0] := 0;
end;
if (max[1] = 0) or (max17[1] = 0) then begin
max[1] := 0;
max17[1] := 0;
end;
if (max[0] + max17[0]) > (max[1] + max17[1]) then begin
if max[0] > max17[0] then writeln(max[0], ' ', max17[0])
else writeln(max17[0], ' ', max[0])
end
else then begin
if max[1] > max17[1] then writeln(max[1], ' ', max17[1])
else writeln(max17[1], ' ', max[1])
end;
end.
В результате работы данного алгоритма при вводе данных из файла A ответ — 8759 3077, из файла B — 10000 9996.
Примечание.
Путь к файлу необходимо указать согласно расположению файла на Вашем компьютере.
Приведём решение Юрия Красильникова на языке Pascal.
var
nums: array [0..3] of integer;
n, ctg, p1, p2, i, x, second: integer;
f: text;
begin
assign(f,'27991_B.txt');
reset(f);
readln(f, n);
p1 := 0; p2 := 0;
for i := 0 to 3 do nums[i] := 0;
for i := 1 to n do begin
readln(f, x);
ctg := x mod 2;
if (x mod 17) = 0 then ctg := ctg+2;
if ctg > 1 then second := nums[ctg-2]
else if nums[ctg] > nums[ctg+2] then second := nums[ctg] else second := nums[ctg+2];
if (second>0) and (x+second > p1+p2) then
begin
p1 := x; p2 := second
end;
if x > nums[ctg] then nums[ctg] := x
end;
if p1 > p2 then writeln(p1,' ',p2) else writeln(p2,' ',p1)
end.
Приведём другое решение на языке Python.
f = open("27991_B.txt") # для файла A укажите его название
s = f.readlines()
n = int(s[0])
max_ch = 0
max_n = 0
max_ch17 = 0
max_n17 = 0
for i in range(1, n + 1):
s[i] = int(s[i])
if s[i] % 2 == 0:
if s[i] % 17 == 0 and s[i] > max_ch17:
max_ch17 = s[i]
elif s[i] % 17 == 0 and s[i] <= max_ch17: # поиск второго максимума
if s[i] > max_ch:
max_ch = s[i]
elif s[i] > max_ch:
max_ch = s[i]
elif s[i] % 2 != 0:
if s[i] % 17 == 0 and s[i] > max_n17:
max_n17 = s[i]
elif s[i] % 17 == 0 and s[i] <= max_n17:
if s[i] > max_n:
max_n = s[i]
elif s[i] > max_n:
max_n = s[i]
if max_n17 + max_n == 0 and max_ch17 + max_ch == 0:
print(0, 0)
elif max_n17 + max_n > max_ch17 + max_ch:
print(max_n17, max_n)
else:
print(max_ch17, max_ch)
Приведём решение Юрия Красильникова на языке Python.
f = open('27991_A.txt')
n = int(f.readline())
nums = [0]*4 # максимальное число в каждой из категорий (см. ниже)
pair = [0,0] # наилучшая пара
for s in f:
x=int(s)
ctg = (x%17!=0)*2 + x % 2 # ctg - категория (0-3):
# 0 - четное, делится на 17; 2 - четное, не делится на 17;
# 1 - нечетное, делится на 17; 3 - нечетное, не делится на 17;
second = max(nums[ctg],nums[ctg+2]) if ctg < 2 else nums[ctg-2]
if second > 0 and x + second > sum(pair):
pair = sorted([x,second],reverse=True)
nums[ctg] = max(nums[ctg],x)
print(*pair)
Приведём решение Арсения Пышнного на языке Python.
def func(x, y):
if len(x)>=2:
for i in y:
if (x[0]+i)%2==0 and (x[0]+i)>(x[0]+x[1]):
return (i, x[0])
elif (x[0]+i)<(x[0]+x[1]):
return (x[0], x[1])
elif len(x)==1:
for i in y:
if (x[0]+i)%2==0:
return (i, x[0])
with open("27991_B.txt") as f:
sp = sorted(map(int, f.readlines()[1:]),reverse=True)
sp_17 = [i for i in sp if i%17==0]
sp.sort(key=lambda x: x%17==0)
print(sp[:10], sp_17[:10])
print(func(sp_17, sp))
Приведём решение Дмитрия Денисова на языке Python.
file = open('27991_A.txt')
a = sorted([int(i) for i in file][1:], reverse=True)
flag = True
for j in range(len(a)):
m = a[j]
for i in range(1, len(a)):
if (a[i] % 17) == 0 and (a[i] - m) % 2 == 0:
print(m, a[i])
flag = False
break
if flag == False:
break
Типичные ошибки
- Пары записаны в обратном порядке: сначала идёт ответ для файла A, затем для файла B. Сверься с требованием задания о порядке записи.
- В пару для файла A дважды попало одно и то же число: элементы пары должны иметь разные номера, а одинаковые значения допустимы, только если число действительно встречается в файле дважды.
В тренажёре: подсказки по шагам, разбор твоей ошибки ИИ-репетитором (он не даёт готовый ответ), повторение ошибок по интервалам и общий прогресс. Все задания №27 по информатике