В первой строке подаются два натуральных
Требуется найти минимальное значение произведения тройки элементов так, что между любыми элементами тройки расстояние между двумя элементами не менее K (то есть разность их индексов по модулю больше или
Входные данные.
Ответ:
Приведём решение на языке Python.
f = open('27.txt')
k = int(f.readline())
n = int(f.readline())
a = [int(x) for x in f]
st = 10**10
fin = 10**10
pr = 10**10
for i in range(2*k,n):
st = min(st, a[i-2*k])
fin = min(fin, st * a[i-k])
pr = min(pr, fin * a[i])
print(pr)
В результате работы данного алгоритма при вводе данных из
Ответ: 12 84.
Примечание.
Путь к файлу необходимо указать согласно расположению файла на Вашем компьютере.
Приведём решение Юрия Лысакова на языке Python.
f = open('1_27_A.txt')
k = int(f.readline())
f.readline()
a = [int(i) for i in f]
b = [[j,a[j]] for j in range(len(a))]
b.sort(key = lambda x: x[1])
min1 = 10**10
rr = 3
# начинаем расширять диапазон перебираемых значений (то есть захватываем не весь диапазон, а только первые 4 элемента, чтобы уменьшить время поиска)
while b[0][1] * b[1][1] * b[rr+1][1] < min1:
# если произведение двух первых наименьших элементов и «после граничного»
# элемента окажется меньше минимальной тройки элементов, то это значит
# что дальнейшие расширение диапазона поиска не имеет смысла, все остальные найденные тройки
# будут больше найденной минимальной
rr += 1
for i1 in range(rr):
for i2 in range(i1+1,rr+1):
for i3 in range(i2+1,rr+2):
if abs(b[i1][0] - b[i2][0]) >= k and abs(b[i1][0] - b[i3][0]) >= k and abs(b[i2][0] - b[i3][0])>= k:
min1 = min(min1,b[i1][1] * b[i2][1] * b[i3][1])
print(min1)