Имеется набор данных, состоящий из пар положительных целых чисел. Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма всех выбранных чисел не делилась на 3 и при этом была максимально возможной. Гарантируется, что искомую сумму получить можно. Программа должна напечатать одно число — максимально возможную сумму, соответствующую условиям задачи.
Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке количество пар N (1 ≤ N ≤ 100 000). Каждая из следующих N строк содержит два натуральных числа, не превышающих 10 000.
Пример организации исходных данных во входном файле:
6
1 3
5 12
6 9
5 4
3 3
1 1
Для указанных входных данных значением искомой суммы должно быть число 32.
В ответе укажите два числа: сначала значение искомой суммы для файла А, затем для файла B.
Предупреждение: для обработки файла B не следует использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.
Ответ:
Решение.
Последовательно считывая данные из файла, будем прибавлять к сумме максимальное число в паре. Также заметим, что в случае, если получившееся в результате суммирования максимальных чисел во всех парах число будет кратно трём, достаточно будет вычесть из этой суммы минимальную разницу между какими-либо двумя числами. Для этого при считывании пар помимо максимального числа в каждой паре будем искать минимальную разницу среди пар, не кратную трём.
Приведём решение задачи на языке Pascal.
var
x, y: longint;
n: longint;
sum: longint;
mindif: longint;
f: text;
begin
assign(f,'C:\27-A.txt');
reset(f);
readln(f, n);
sum := 0;
mindif := 20001;
while not eof(f) do begin
readln(f, x, y);
if x > y then
sum := sum + x
else
sum := sum + y;
if (abs(x - y) < mindif) and (abs(x-y) mod 3 <> 0) then mindif := abs(x-y);
end;
if sum mod 3 <> 0 then
writeln(sum)
else
writeln(sum - mindif);
end.
В результате работы данного алгоритма при вводе данных из файла A ответ — 127127, из файла B — 399762080.
Примечание.
Путь к файлу необходимо указать согласно расположению файла на Вашем компьютере.
Приведём другое решение на языке Python.
f = open("27-B_demo (2).txt") # для файла A замените название
s = f.readlines()
n = int(s[0]) # количество пар
summi = 0
d = 10**6
for i in range(1, n + 1):
x, y = map(int, s[i].split())
summi += max(x, y)
if abs(x - y) % 3 != 0:
d = min(d, abs(x - y))
if summi % 3 != 0:
print(summi)
else:
print(summi - d)
Приведём решение Юрия Красильникова на языке Python:
a=[list(map(int,s.split())) for s in open('27-B_demo.txt')][1:]
s=sum([max(x) for x in a])
d=min([abs(x[0]-x[1]) for x in a if (x[0]-x[1])%3!=0])
Последовательность натуральных чисел характеризуется числом Х — наибольшим числом, кратным 14 и являющимся произведением двух элементов последовательности с различными номерами. Гарантируется, что хотя бы одно такое произведение в последовательности есть.
Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке количество чисел N (1 ≤ N ≤ 100 000). В каждой из последующих N строк записано одно натуральное число, не превышающее 1000.
Пример организации исходных данных во входном файле:
5
40
1000
7
28
55
Пример выходных данных для приведённого выше примера входных данных:
28000 В ответе укажите два числа: сначала значение искомого произведения для файла А, затем для файла B.
Ответ:
Решение.
Произведение двух чисел делится на 14, если:
— либо один из сомножителей делится на 14 (второй может быть любым),
— либо ни один из сомножителей не делится на 14, но один из сомножителей делится на 7, а другой — на 2.
Поэтому программа, вычисляющая число X, может работать так.
Программа читает все входные данные один раз, не запоминая все данные в массиве. Программа для прочитанного фрагмента входной последовательности хранит значения четырёх величин:
1) М7 — самое большое число, кратное 7, но не кратное 2;
2) M2 — самое большое число, кратное 2, но не кратное 7;
3) M14 — самое большое число, кратное 14;
4) МAX — самое большое число среди всех элементов последовательности, отличное от М14 (если число М14 встретилось более одного раза и оно же является максимальным, то MAX = M14).
После того как все данные прочитаны, искомое число X вычисляется как максимум из произведений М14 · MAX и М7 · М2.
Ниже приведён пример программы на языке Паскаль, которая реализует описанный алгоритм.
Приведём решение задачи на языке Pascal.
var M7,M2,M14,MAX,dat,res,i,N: longint; var s: string;
begin
M7 := 0;
M2 := 0;
M14 := 0;
MAX := 0;
assign(input, '27-B_2.txt');
readln(N);
for i := 1 to N do
begin
readln(dat);
if ((dat mod 7) = 0) and ((dat mod 2) > 0) and (dat > M7) then
M7 := dat;
if ((dat mod 2) = 0) and ((dat mod 7) > 0) and (dat > M2) then
M2 := dat;
if (dat mod 14 = 0) and (dat > M14) then
begin
if M14 > MAX then MAX := M14;
M14 := dat
end
else
if dat > MAX then
MAX := dat;
end;
if (M7*M2 < M14*MAX) then
res := M14*MAX
else
res := M7*M2;
writeln(res);
end.
В результате работы данного алгоритма при вводе данных из файла A ответ — 447552, из файла B — 994000.
Примечание.
Путь к файлу необходимо указать согласно расположению файла на Вашем компьютере.
Приведём решение Юрия Лысакова на языке Python.
f = open('27-B_2.txt')
f.readline()
a = [int(i) for i in f]
a.sort()
a = a[::-1]
max1 = 0
for i in range(0,len(a)-1):
if a[i]*a[i+1] < max1: break
for j in range(i+1,len(a)):
if (a[i]*a[j]) % 14 == 0:
max1 = max(max1,a[i]*a[j])
print(max1)
Приведём решение Михаила Глинского на языке Python.
f = open('27-A_2.txt')
n = int(f.readline())
m = [int (x) for x in f]
m2 = [0]
m7 = [0]
m14 = [0]
ma = max(m)
for i in range(n):
if m[i]%14 == 0 and m[i]!= ma:
m14.append(m[i])
elif m[i]%7 == 0:
m7.append(m[i])
elif m[i]%2 == 0:
m2.append(m[i])
print(max(max(m2)*max(m7),max(m14)*ma))
Приведём решение Юрия Красильникова на языке Python:
На вход программы поступает последовательность из N целых положительных чисел. Рассматриваются все пары различных элементов последовательности (элементы пары не обязаны стоять в последовательности рядом, порядок элементов в паре не важен). Необходимо определить количество пар, для которых произведение элементов делится на 26.
В первой строке входных данных задаётся количество чисел N(1 ≤ N ≤ 60 000). В каждой из последующих N строк записано одно целое положительное число, не превышающее 10 000. В качестве результата программа должна напечатать одно число: количество пар, в которых произведение элементов кратно 26.
Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке количество чисел N(1 ≤ N ≤ 60 000). В каждой из последующих N строк записано одно натуральное число, не превышающее 10 000.
Пример организации исходных данных во входном файле:
4
2
6
13
39
Пример выходных данных для приведённого выше примера входных данных:
4
В ответе укажите два числа: сначала значение искомой суммы для файла А, затем для файла B.
Ответ:
Пояснение. Из четырёх заданных чисел можно составить 6 попарных произведений: 2 · 6, 2 · 13, 2 · 39, 6 · 13, 6 · 39, 13 · 39 (результаты: 12, 26, 78, 78, 234, 507). Из них на 26 делятся 4 произведения (2 · 13 = 26; 2 · 39 = 78; 6 · 13 = 78; 6 · 39 = 234).
Решение.
Произведение двух чисел делится на 26, если выполнено одно из следующих условий (условия не могут выполняться одновременно).
А. Оба сомножителя делятся на 26.
Б. Один из сомножителей делится на 26, а другой не делится.
В. Ни один из сомножителей не делится на 26, но один сомножитель делится на 2, а другой — на 13.
Примечание для проверяющего. Условие делимости произведения на 26 можно сформулировать проще, например так: (один из сомножителей делится на 26) ИЛИ (один сомножитель делится на 2, а другой — на 13). Но в этом случае пара сомножителей может удовлетворять обоим условиям, что затруднит подсчёт количества пар.
При вводе чисел можно определять, делится ли каждое из них на 26, 2 и 13, и подсчитывать следующие значения:
1) n26 — количество чисел, кратных 26;
2) n13 — количество чисел, кратных 13, но не кратных 26;
3) n2 — количество чисел, кратных 2, но не кратных 26.
Примечание для проверяющего. Сами числа при этом можно не хранить. Каждое число учитывается не более чем в одном из счётчиков. Количество пар, удовлетворяющих условию А, можно вычислить по формуле n26 · (n26 – 1) : 2.
Количество пар, удовлетворяющих условию Б, можно вычислить по формуле n26 · (N – n26).
Количество пар, удовлетворяющих условию В, можно вычислить по формуле n2 · n13.
Приведём решение Юрия Красильникова на языке Python.
#Решение на питоне, подсчет чисел с разной делимостью:
a=[int(s) for s in open('27989_B.txt')][1:]
m2=len([x for x in a if x%2==0 and x%13!=0])
m13=len([x for x in a if x%13==0 and x%2!=0])
m26=len([x for x in a if x%26==0])
m=len(a)
print(m26*(m26-1)//2 + m26*(m-m26) + m2*m13)
Приведём решение Юрия Красильникова на языке Python.
#Выбираем числа последовательности по очереди и прибавляем к счетчику пар число пар, которое очередное число образует с предыдущими:
a = [int(s) for s in open('27989_B.txt')][1:]
cnts = [0]*4
k = 0 # счетчик количества пар
for x in a:
n = (x%2==0)*2 + (x%13==0) # n=0 - не делится ни на 2, ни на 13.
# n=2 - делится на 2; n=1 - делится на 13; n=3 - делится на 26;
Дана последовательность N целых положительных чисел. Рассматриваются все пары элементов последовательности, разность которых чётна, и в этих парах, по крайней мере, одно из чисел пары делится на 17. Порядок элементов в паре неважен. Среди всех таких пар нужно найти и вывести пару с максимальной суммой элементов. Если одинаковую максимальную сумму имеет несколько пар, можно вывести любую из них. Если подходящих пар в последовательности нет, нужно вывести два нуля.
В первой строке входных данных задаётся количество чисел N(2 ≤ N ≤ 10 000). В каждой из последующих N строк записано одно натуральное число, не превышающее 10 000.
Пример организации исходных данных во входном файле:
5
34
12
51
52
51
Пример выходных данных для приведённого выше примера входных данных:
51 51 В ответе укажите четыре числа: сначала значение искомой пары для файла А (два числа через пробел), затем для файла B (два числа через пробел). Числа пар впишите в порядке убывания.
Ответ:
Пояснение. Из данных пяти чисел можно составить три различные пары, удовлетворяющие условию: (34, 12),(34, 52),(51, 51). Наибольшая сумма получается в паре (51, 51). Эта пара допустима, так как число 51 встречается в исходной последовательности дважды.
Решение.
Приведём решение задачи на языке 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 укажите его название
На вход программы поступает последовательность из N натуральных чисел. Рассматриваются все пары различных элементов последовательности, у которых различные остатки от деления на d = 160 и хотя бы одно из чисел делится на p = 7. Среди таких пар необходимо найти и вывести пару с максимальной суммой элементов.
В первой строке входных данных задаётся количество чисел N(1 ≤ N ≤ 1000). В каждой из последующих N строк записано одно натуральное число, не превышающее 10 000. В качестве результата программа должна напечатать элементы искомой пары. Если среди найденных пар максимальную сумму имеют несколько, то можно напечатать любую из них. Если таких пар нет, то вывести два нуля.
Пример организации исходных данных во входном файле:
4
168
7
320
328
Пример выходных данных для приведённого выше примера входных данных:
168 320 В ответе укажите четыре числа: сначала значение искомой пары для файла А (два числа через пробел по возрастанию), затем для файла B (два числа через пробел по возрастанию).
Ответ:
Решение.
Отметим:
m71 — самое большое число, кратное 7;
m72 — второе по величине число, кратное 7, и остаток от деления на 160 не равен остатку от деления m71 на 160;
m1 — самое большое число, не кратное 7;
m2 — второе по величине число, не кратное 7, и остаток от деления на 160 не равен остатку от деления m71 на 160.
Приведём решение задачи на языке Pascal.
var
n, i, m71, m72, m1, m2, max1, max2, x: integer;
f: text;
begin
m71:=0;
m72:=0;
m1:=0;
m2:=0;
max1:=0;
max2:=0;
assign(f,'28129_A.txt');
reset(f);
readln(f, N);
while not eof(f) do begin
readln(f, x);
if (x mod 7 = 0) and (x mod 160 = m71 mod 160) and (x > m71) then
m71 := x
else if (x mod 7 = 0) and (x mod 160 <> m71 mod 160) and (x > m71) then
begin
m72 := m71;
m71 := x;
end
else if (x mod 7 = 0) and (x mod 160 <> m71 mod 160) and (x > m72) then
m72 := x
else if (x mod 7 <> 0) and (x mod 160 = m1 mod 160) and (x > m1) then
m1 := x
else if (x mod 7 <> 0) and (x mod 160 <> m1 mod 160) and (x > m1) then
begin
m2 := m1;
m1 := x;
end
else if (x mod 7 <> 0) and (x mod 160 <> m1 mod 160) and (x > m2) then
m2 := x;
end;
if (m71 = 0) and (m72 = 0) then
writeln(0, ' ', 0)
else if (m72 = 0) and (m2 = 0) and (m71 mod 160 = m1 mod 160) then
writeln(0, ' ', 0)
else
begin
if (m71+m72)>(max1+max2) then
begin
max1 := m71;
max2 := m72;
end;
if ((m71+m1)>(max1+max2)) and (m71 mod 160 <> m1 mod 160) then
begin
max1 := m71;
max2 := m1;
end;
if ((m71+m2)>(max1+max2)) and (m71 mod 160 <> m2 mod 160) then
begin
max1 := m71;
max2 := m2;
end;
if (((m72 + m1) > (max1 + max2)) and ((m72 mod 160) <> (m1 mod 160))) then
begin
max1 := m72;
max2 := m1;
end;
writeln(max1, ' ', max2);
end;
end.
Приведём решение Ивана Корниенко на языке Pascal.
var
s, n, x, x1, k7, n7, t: integer;
a: array[0..159, 0..1] of integer;
f: text;
begin
for var j := 0 to 159 do
for var l := 0 to 1 do
a[j][l] := 0;
s := 0;
assign(f, 'C:\28129_A.txt');
reset(f);
readln(f, n);
readln(f, x);
for var i := 2 to n do
begin
t := 1;
if x mod 7 = 0 then
t := 0;
if x >= a[x mod 160][t] then
a[x mod 160][t] := x;
readln(f, x);
for var k := 0 to 159 do
for var r := 0 to 1 do
if ((x + a[k][r]) > s) and (x mod 160 <> k) and
((x * a[k][r]) mod 7 = 0) then
begin
s := x + a[k][r];
x1 := x;
end;
end;
if s = 0 then
writeln('00')
else
if (s - x1) < x1 then writeln(s - x1, ' ', x1)
else writeln(x1, ' ', s - x1)
end.
В результате работы данного алгоритма при вводе данных из файла A ответ — 728 977, из файла B — 9982 9992.
Примечание.
Путь к файлу необходимо указать согласно расположению файла на Вашем компьютере.
Приведём решение на языке Python.
f = open("28129_B.txt")
s = f.readlines()
m71 = 0
m72 = 0
m1 = 0
m2 = 0
max1 = 0
max2 = 0
for i in range(len(s)):
x = int(s[i])
if x % 7 == 0 and x % 160 == m71 % 160 and x > m71:
m71 = x
elif x % 7 == 0 and x % 160 != m71 % 160 and x > m71:
m72 = m71
m71 = x
elif (x % 7 == 0) and (x % 160 != m71 % 160) and (x > m72):
m72 = x
elif x % 7 != 0 and x % 160 == m1 % 160 and x > m1:
m1 = x
elif x % 7 != 0 and x % 160 != m1 % 160 and x > m1:
m2 = m1
m1 = x
elif x % 7 != 0 and x % 160 != m1 % 160 and x > m2:
m2 = x
if m71 == 0 and m72 == 0:
print(0, 0)
elif (m72 == 0) and (m2 == 0) and (m71 % 160 == m1 % 160):
print(0, 0)
else:
if (m71 + m72) > (max1 + max2):
max1 = m71
max2 = m72
if ((m71 + m1) > (max1 + max2)) and (m71 % 160 != m1 % 160):
max1 = m71
max2 = m1
if ((m71+m2)>(max1+max2)) and (m71 % 160 != m2 % 160):
max1 = m71
max2 = m2
if (((m72 + m1) > (max1 + max2)) and ((m72 % 160) != (m1 % 160))):
max1 = m72
max2 = m1
print(max1, max2)
Приведём решение Юрия Лысакова на языке Python.
f = open('28129_B.txt')
f.readline()
s = 0
b1 = 0
b2 = 0
a = [int(i) for i in f]
for i in range(len(a) - 1):
for j in range(i+1, len(a)):
if a[i] % 160 != a[j] % 160 and (a[i] % 7 == 0 or a[j] % 7 == 0):
if a[i] + a[j] > s:
s = a[i] + a[j]
b1 = a[i]
b2 = a[j]
print(b1,b2)
Приведём решение Юрия Красильникова на языке Python.
a = sorted([int(s) for s in open('28129_B.txt')][1:],reverse=True)
r=[[] for _ in range(160)]
for x in a: r[x%160].append(x) # распределяем по остаткам
ans = [[0,0]] # если не найдем других решений
for i in range(160):
m7 = [x for x in r[i] if x%7==0]
if m7:
dop=[r[j][0] for j in range(160) if j!=i and r[j]]
