В текстовом файле записан набор натуральных чисел, не превышающих 108. Гарантируется, что все числа различны. Из набора нужно выбрать три числа, сумма которых делится
Входные данные.
Первая строка входного файла содержит целое число N — общее количество чисел в наборе. Каждая из следующих N строк содержит одно число.
Пример входного файла:
4
5
8
14
11 В данном случае есть четыре подходящие тройки: 5, 8, 11
Вам даны два входных файла
Ответ:
Заметим, что сумма трёх чисел будет делиться
Приведём решение задачи на языке Pascal.
var
n, i, x, sum0, sum1, sum2, sum12: longint;
m0: array[1..3] of longint;
m1: array[1..3] of longint;
m2: array[1..3] of longint;
f: text;
begin
assign(f,'C:\27-B.txt');
reset(f);
readln(f, n);
for i := 1 to 3 do begin
m0[i] := 100000000;
m1[i] := 100000000;
m2[i] := 100000000;
end;
for i := 1 to n do begin
readln(f, x);
if x mod 3 = 0 then begin
if x < m0[1] then begin
m0[3] := m0[2];
m0[2] := m0[1];
m0[1] := x;
end
else if x < m0[2] then begin
m0[3] := m0[2];
m0[2] := x;
end
else if x < m0[3] then m0[3] := x;
end
else if x mod 3 = 1 then begin
if x < m1[1] then begin
m1[3] := m1[2];
m1[2] := m1[1];
m1[1] := x;
end
else if x < m1[2] then begin
m1[3] := m1[2];
m1[2] := x;
end
else if x < m1[3] then m1[3] := x;
end
else if x mod 3 = 2 then begin
if x < m2[1] then begin
m2[3] := m2[2];
m2[2] := m2[1];
m2[1] := x;
end
else if x < m2[2] then begin
m2[3] := m2[2];
m2[2] := x;
end
else if x < m2[3] then m2[3] := x;
end;
end;
sum0 := m0[1] + m0[2] + m0[3];
sum1 := m1[1] + m1[2] + m1[3];
sum2 := m2[1] + m2[2] + m2[3];
sum12 := m0[1] + m1[1] + m2[1];
if (sum0 < sum1) and (sum0 < sum2) and (sum0 < sum12) then writeln(sum0)
else if (sum1 < sum0) and (sum1 < sum2) and (sum1 < sum12) then writeln(sum1)
else if (sum2 < sum1) and (sum2 < sum0) and (sum2 < sum12) then writeln(sum2)
else writeln(sum12);
end.
В результате работы данного алгоритма при вводе данных из
Примечание.
В файле A число в первой строке — общее количество чисел в файле.
Приведём другое решение на языке Python.
f = open("27-B (5).txt")
s = f.readlines()
n = int(s[0])
m0 = [1 for i in range(4)]
m1 = [1 for i in range(4)]
m2 = [1 for i in range(4)]
for i in range(1, 4):
m0[i] = 100000000
m1[i] = 100000000
m2[i] = 100000000
for i in range(1, n + 1):
x = int(s[i])
if x % 3 == 0:
if x < m0[1]:
m0[3] = m0[2]
m0[2] = m0[1]
m0[1] = x
elif x < m0[2]:
m0[3] = m0[2]
m0[2] = x
elif x > m0[3]: m0[3] = x
elif x % 3 == 1:
if x < m1[1]:
m1[3] = m1[2]
m1[2] = m1[1]
m1[1] = x
elif x < m1[2]:
m1[3] = m1[2]
m1[2] = x
elif x < m1[3]: m1[3] = x
elif x % 3 == 2:
if x < m2[1]:
m2[3] = m2[2]
m2[2] = m2[1]
m2[1] = x
elif x < m2[2]:
m2[3] = m2[2]
m2[2] = x
elif x > m2[3]: m2[3] = x
sum0 = m0[1] + m0[2] + m0[3]
sum1 = m1[1] + m1[2] + m1[3]
sum2 = m2[1] + m2[2] + m2[3]
sum12 = m0[1] + m1[1] + m2[1]
if (sum0 < sum1) and (sum0 < sum2) and (sum0 < sum12): print(sum0)
elif (sum1 < sum0) and (sum1 < sum2) and (sum1 < sum12): print(sum1)
elif (sum2 < sum1) and (sum2 < sum0) and (sum2 < sum12): print(sum2)
else: print(sum12)
Приведём решение Королихина Валерия на языке Python.
f = open("27.txt")
n = int(f.readline())
a = sorted(list(map(int, f.readlines())))
min0 = []
min1 = []
min2 = []
for i in a:
if i % 3 == 0:
min0.append(i)
if i % 3 == 1:
min1.append(i)
if i % 3 == 2:
min2.append(i)
ans = 111111
if len(min0) >= 3:
ans = min(ans, sum(min0[:3]))
if len(min1) >= 3:
ans = min(ans, sum(min1[:3]))
if len(min2) >= 3:
ans = min(ans, sum(min2[:3]))
if min0 and min1 and min2:
ans = min(ans, min0[0] + min1[0] + min2[0])
print(ans)
Приведём решение Юрия Красильникова на языке Python.
nums = sorted([int(s) for s in open('27-B.txt') ][1:])
t = [(0, 0, 3), (0, 3, 0), (3, 0, 0), (1, 1, 1)]
rems = [[],[],[]]
for x in nums: rems[x%3].append(x)
ans=[]
for p in t:
if all([p[i] <= len(rems[i]) for i in range(3)]):
ans.append(sum([sum(rems[i][0:p[i]]) for i in range(3)]))
print(min(ans))
Приведём решение Сергея Фефелова на языке Python.
n, *a = map(int, open('27-A.txt'))
r3 = [[10**8]*3 for i in range(3)]
for x in a: r3[x%3].append(x)
for i in range(3): r3[i].sort()
smin = r3[0][0]+r3[1][0]+r3[2][0]
for i in range(3):
smin = min(smin, sum(r3[i][:3]))
print(smin)
Приведём решение Дмитрия Денисова на языке Python.
f = open('27-B.txt')
a = [int(i) for i in f]
sp0 = sorted([int(i) for i in a if i%3==0])
sp1 = sorted([int(i) for i in a if i%3==1])
sp2 = sorted([int(i) for i in a if i%3==2])
c1 = sp0[0] + sp0[1] + sp0[2]
c2 = sp0[0] + sp1[0] + sp2[0]
c3 = sp1[0] + sp1[1] + sp1[2]
c4 = sp2[0] + sp2[1] + sp2[2]
print(min(c1, c2, c3, c4))