На вход программы поступает последовательность из N целых положительных чисел. Рассматриваются все пары различных элементов последовательности (элементы пары не обязаны стоять в последовательности рядом), такие, что ai > aj при i < j ≤ N. Среди пар, удовлетворяющих этому условию, необходимо найти и вывести пару с максимальной суммой элементов, которая делится
Входные данные.
В первой строке входных данных задаётся количество
В качестве результата программа должна напечатать элементы искомой пары. Если таких пар несколько, можно вывести любую из них.
Пример организации исходных данных во входном файле:
7
1
119
2
118
3
237
123
Пример выходных данных для приведённого выше примера входных данных:
237 123 В ответе укажите четыре числа: сначала значение искомой суммы для
Ответ:
Пояснение. Из
Заметим, что сумма двух элементов
Приведём решение задачи на языке Pascal.
var
a: array[0..119] of integer;
i, j, n, x, t, n1, n2: integer;
f: text;
begin
assign(f,'28133_A.txt');
reset(f);
readln(f, n);
for i := 0 to 119 do
a[i] := 0;
n1 := 0;
n2 := 0;
for i := 1 to n do begin
readln(f, x);
t := x mod 120;
if t = 0 then t := 120;
if (a[120-t] > x) and (a[120-t] + x > n1 + n2) then begin
n1 := a[120-t];
n2 := x;
end;
if t < 120 then begin
if a[t] < x then a[t] := x;
end
else if (x > a[0]) then
a[0] := x;
end;
if n1 + n2 <> 0 then writeln(n1, ' ', n2)
else writeln('00');
end.
В результате работы данного алгоритма при вводе данных из
Примечание.
Путь к файлу необходимо указать согласно расположению файла на Вашем компьютере.
Приведём решение Петра Полякова на языке Python.
def f(x,dict):
for key,keybord in dict.items():
if key==x:
return keybord
g=open('27.txt')
n=int(g.readline())
numbers=[int(x) for x in g]
i=0
dict={}
k=0
maxk=0
while i!=n:
for h in range(i+1,n):
if ((numbers[h]+numbers[i]) % 120 ==0) and (numbers[h] < numbers[i]) and (numbers.index(numbers[h]) > numbers.index(numbers[i])):
dict[numbers[h]+numbers[i]]=numbers[i],numbers[h]
k=numbers[h]+numbers[i]
maxk=max(k,maxk)
i=i+1
if maxk==0:
print('00')
else:print('Максимальная сумма:',maxk,'.Искомые элементы:',f(maxk,dict))
Приведём другое решение Сурина Игната на языке Python.
f = open('28133_B.txt')
n=int(f.readline())
a = [int(i.strip()) for i in f]
x = 0
y = 0
max_xy = 0
for i in range (len(a)-1):
for k in range(i+1,len(a)):
if(a[i]+a[k])%120==0 and max_xy < a[i]+a[k] and a[i] > a[k]:
x =a[i]
y = a[k]
max_xy=a[i]+a[k]
print(x,y)