Дана последовательность целых чисел. Необходимо выбрать из последовательности три числа так, чтобы они образовали возрастающую последовательность. Определите минимально возможную сумму выбранных чисел.
Входные данные.
Первая строка входного файла содержит
Пример.
Дан входной файл:
4
3
5
2
6
Из этого файла надо выбрать числа 3, 5 и 6, сумма которых
Выбрать числа 3, 5 и 2 нельзя, так как они не образуют возрастающую последовательность.
Вам даны два входных файла
Ответ:
Приведем решение для файла А на языке Python.
f = open ('27-A.txt')
n = int(f.readline())
a = []
for x in range(n):
a.append(int(f.readline()))
min_summa=10**10
for i in range (len(a)):
for j in range(i+1,len(a)):
for k in range(j+1,len(a)):
if a[i] < a[j] < a[k]:
min_summa=min(min_summa, a[i]+a[j]+a[k])
print(min_summa)
Приведем решение на языке Python.
f = open ('27-B.txt')
n = int(f.readline())
a = []
for x in range(n):
a.append([int(f.readline()),x]) # Добавляем в массив число и его индекс
a.sort()
a = a[:10] # Так как массив отсортирован по возрастанию, берем первые 10 значений и ищем среди них 3 числа удовлетворяющие условию. Если среди 10 чисел не будет найден ответ, диапазон можно увеличить
a.sort(key=lambda x: x[1]) #сортируем массив по индексам
min_summa = 10**10
for i in range (len(a)):
for j in range(i+1,len(a)):
for k in range(j+1,len(a)):
if a[i][0] < a[j][0] < a[k][0]:
min_summa = min(min_summa, a[i][0] + a[j][0] + a[k][0])
print(min_summa)
Ответ: 30419&398.
Приведем решение Виталия Будилова на языке Python.
with open('27-A.txt') as f:
n = int(f.readline())
data = [int(i) for i in f]
min_l = 10 ** 10 # минимальное число слева
min_m = 10 ** 10 # минимальное число посередине
mid_sum = 10 ** 10 # минимальная сумма первых двух чисел
res = 10 ** 10 # искомая сумма трёх чисел
for i in range(2, len(data)):
min_l = min(min_l, data[i - 2]) # нашли минимум слева
if data[i - 1] > min_l: # проверяем, что следующее число с предыдущим даёт возрастающую посл.
if min_l + data[i - 1] <= mid_sum: # если новая сумма «лучше» прежней
mid_sum = min_l + data[i - 1] # обновляем мин сумму пары
min_m = data[i - 1] # и обновляем значение минимального посередине
if data[i] > min_m: # проверяем, что следующее число тоже входит в возрастающую последовательность
res = min(res, mid_sum + data[i])
print(res)
Приведём решение Юрия Красильникова на языке Python.
a = [int(s) for s in open('27.txt')][1:]
left = [a[0]] # минимальное число слева
for x in a[1:]: left.append(min(left[-1],x))
right = [a[-1]] # минимальное число справа
for x in a[-2::-1]: right.append(min(right[-1],x))
right = right[::-1]
r = [left[i-1] + right[i+1] + a[i] for i in range(1,len(a) - 1) if left[i-1] < a[i] < right[i+1]]
print(min(r))