2

Имеется набор данных, состоящий из положительных целых чисел, все числа не превышают 10000. Количество чисел известно, но может быть очень велико. Необходимо найти наименьшее произведение пары чисел, кратное 46, числа в которой находятся на расстоянии не больше 7 (разность в индексах ≤ 7). Под парой подразумеваются два числа, расположенных на разных местах в наборе, порядок в паре неважен. Программа должна напечатать одно число - минимально возможное произведение, соответствующее условиям задачи. Если такое произведение получить невозможно, вывести -1.

Описание входных и выходных данных

Даны два входных файла, каждый из которых содержит в первой строке количество чисел N (8 ≤ N ≤ 100000). В каждой из последующих N строк записано одно натуральное число, не превышающее 10000.

Моё решение:

f = open("27Б.txt")
n = int(f.readline())
mas = []
min_46 = 99**99
min_46_2 = 99**99
min_23 = 99**99
min_2 = 99**99
minimum_all = 99**99
for i in range(n):
    mas.append(int(f.readline()))

for j in range(n):
    if mas[j] % 23 == 0 and mas[j] % 2 == 0:
        if min_46 > mas[j] and min_46_2 < mas[j]:
            min_46 = mas[j]
        elif mas[j] < min_46 and mas[j] < min_46_2:
            min_46 = min_46_2 = mas[j]
    elif mas[j] % 23 == 0:
        if min_23 > mas[j]:
            min_23 = mas[j]
    elif mas[j] % 2 == 0:
        if min_2 > mas[j]:
            min_2 = mas[j]
    elif minimum_all > mas[j]:
        minimum_all = mas[j]

a = min(min_46*min_46_2,min_2*min_23,min_2*min_46_2,min_23*min_46_2,
        min_46*minimum_all,min_46_2*minimum_all)

if a > 99**99:
    print(-1)
else:
    print(a)

Проблема: Не знаю как добавить условие из задачи " числа в которой находятся на расстоянии не больше 7 (разность в индексах ≤ 7)".

6
  • У вашего алгоритма квадратичная сложность, пробуйте решать задачу за линию
    – tewboat
    14 дек 2021 в 4:31
  • 3
    По-моему, решение очевидное. Если произведение делится на 46, то либо одно из чисел делится на 46, либо одно чётное, а второе делится на 23. Так что по мере ввода сортируем числа на 3 кучки, и потом сравниваем произведение наименьшего из "23" и наименьшего из "2" и произведение наименьшего из "46" с наименьшим вообще.
    – Akina
    14 дек 2021 в 5:02
  • @Akina вы полностью правы! Только я не понимаю, как поставить условие "которой находятся на расстоянии не больше 7 (разность в индексах ≤ 7)."
    – Rendivy
    14 дек 2021 в 5:18
  • Значит, при парсинге сохранять позицию элемента, дропать излишне "старые" элементы из групп, сохранять текущее минимальное произведение.
    – Akina
    14 дек 2021 в 5:20
  • 2
    Берёшь элемент номер N - выбрасывай из групп элементы с номером N-8 и меньше, а потом смотри произведения и сравнивай с текущим минимальным. Всё.
    – Akina
    14 дек 2021 в 6:03

1 ответ 1

3

Вариант решения "в лоб". Вероятно не самый эффективный, но может натолкнет на верное решение:

min_m = []
for i in range(len(n)):
    for j in n[i+1:i+8]:
        m = n[i]*j
        if m%46==0:
            min_m.append(m)
if len(min_m)==0:
    res_m = -1
else:
    res_m = min(min_m)
print(res_m)

эту часть:

if len(min_m)==0:
    res_m = -1
else:
    res_m = min(min_m)

можно заменить на:

res_m = min(min_m, default=-1)

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.