Задача к ЕГЭ по информатике на тему «Макс/мин, кол-во пар, произведение кратно/не кратно» №1

Задание выполняется с использованием прилагаемых файлов

Имеется набор данных, состоящий из положительных целых чисел. Необходимо найти наибольшее произведение двух элементов, с разными номерами, кратное 3  . Гарантируется, что хотя бы одно такое произведение в последовательности есть. Программа должна напечатать одно число — максимально возможное произведение, которое соответствует условиям задачи.

Входные файлы:

Файл 27 A

Файл 27 B

Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке количество пар N (1 ≤ N ≤ 100000).  Каждая из следующих N строк содержит натуральное число, не превышающих 1000.

В ответе укажите два числа: сначала значение искомого произведения для файла А, затем для файла B.

Переборное решение

f = open("27A.txt")
n = int(f.readline())
a = [int(f.readline()) for x in range(n)]
ans = 0
for i in range(n):
    for j in range(i + 1, n):
        if (a[i] * a[j]) % 3 == 0:
            ans = max(ans, a[i] * a[j])
print(ans)

Статическое решение

file = open(’Задание_27_A__hi6v__swy9.txt’)
n = int(f.readline())

max_kr3 = 0  # Максимальное число, кратное 3
predmax_kr3 = 0  # Второе по величине число, кратное 3
max_nekr = 0  # Максимальное число, не кратное 3

for i in range(n):
    x = int(f.readline())
    if x % 3 == 0:
        if x > max_kr3:
            predmax_kr3 = max_kr3
            max_kr3 = x
        elif x > predmax_kr3:
            predmax_kr3 = x
    else:
        max_nekr = max(x, max_nekr)

print(max_kr3 * max(predmax_kr3, max_nekr))

Динамическое решение

file = open(’Задание_27_A__hi6v__swy9.txt’)
n = int(file.readline())
ans = 0  # Максимальное произведение чисел, кратное 3
kr3 = 0  # Максимальное число, кратное 3
nekr = 0  # Максимальное число, не кратное 3
for i in range(n):
    x = int(file.readline())
    if x % 3 == 0:
        ans = max(ans, x * kr3, x * nekr)
        kr3 = max(kr3, x)
    else:
        ans = max(ans, x * kr3)
        nekr = max(nekr, x)
print(ans)

Ответ: 800961 999000
Оцените статью
Я решу все!