0

Вот условия задачи, будет ли задача подходить под один из форматов о эффективности по времени или памяти?

Дана последовательность N целых положительных чисел. Рассматриваются все пары элементов последовательности, разность которых чётна, и в этих парах, по крайней мере, одно из чисел пары делится на 17. Порядок элементов в паре неважен. Среди всех таких пар нужно найти и вывести пару с максимальной суммой элементов. Если одинаковую максимальную сумму имеет несколько пар, можно вывести любую из них. Если подходящих пар в последовательности нет, нужно вывести два нуля.

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

В первой строке входных данных задаётся количество чисел N (2 ≤ N ≤ 10 000). В каждой из последующих N строк записано одно натуральное число, не превышающее 10 000.

Пример входных данных:

5
34
12
51
52
51

Пример выходных данных для приведённого выше примера входных данных:

51 51

Пояснение. Из данных пяти чисел можно составить три различные пары, удовлетворяющие условию: (34, 12), (34, 52), (51, 51). Наибольшая сумма получается в паре (51, 51). Эта пара допустима, так как число 51 встречается в исходной последовательности дважды.

Напишите эффективную по времени и памяти программу для решения этой задачи.

Программа считается эффективной по времени, если при увеличении количества исходных чисел N в k раз время работы программы увеличивается не более чем в k раз.

Программа считается эффективной по памяти, если память, необходимая для хранения всех переменных программы, не превышает 1 Кбайт и не увеличивается с ростом N.

n=int(input())
n17h=0
n17n=0
neh=0
het=0
for i in range(0,n):
    g=int(input())
    if g%17==0 and g%2==0 and g>=n17h:
       n17h=g
    elif g%17==0 and g%2!=0 and g>n17n:
       n17n=g
    elif g%2==0 and g>het:
       het=g
    elif g%2!=0 and g>neh:
       neh=g
if het!=0 and n17h!=0 and (het+n17h>neh+het):
    print(het,n17h)
elif neh!=0 and n17n!=0 and (het+n17h<neh+het):
    print(neh,n17n)
else:
    print("00")

1 ответ 1

1

Да. Не проверял программу на корректность работы, но эффективность по времени и по памяти такая, какая требуется в экзамене. По списку чисел осуществляется проход только один раз при вводе, память используется константного размера, вводимые числа не сохраняются в массив.

Ваш ответ

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

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