Задача к ЕГЭ по информатике на тему «Программирование – оптимизация по времени и по памяти» №1

Просмотров 11 Комментарии 0

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

Имеется набор данных, состоящий из положительных целых чисел $1$ или $2$ .

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

Входные данные:

Даны два входных файла (файл А и файл В), каждый из которых содержит в первой строке одно целое число $N (1 ≤ N ≤ 1000000)$ — количество чисел. Каждая из следующих $N$ строк содержит натуральное число $1$ или $2$ .

Пример входного файла:

$5$

$1$

$2$

$1$

$2$

$1$

При таких исходных данных оптимально расположить числа следующим образом: $1 1 1 2 2$ или $2 1 2 1 1$ . Тогда префиксные суммы будут равны $1,2,3,5,7$ или $2,3,5,6,7$ соответственно. Ответ: $4$ .

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

def is_prime(k):
    if k == 1:
        return False
    for j in range(2, int(k ** 0.5) + 1):
        if k % j == 0:
            return False
    return True


f = open(’Задание_27_B__loof.txt’)
n = int(f.readline())
ones, twos = 0, 0
for i in range(n):
    ones += (int(f.readline()) == 1)
twos = n - ones
# Если не существует единиц или двоек
if not ones or not twos:
    a = [1] * ones + [2] * twos
else:
    a = [2, 1] + [2] * (twos - 1) + [1] * (ones - 1)
# Простое число - нечетное. Первое простое - это 2. Далее 3, 5, 7, 11 и тд - все они нечетные.
# Но лучшего расположения мы добьемся при скачках сначала по нечетным, а потом все остальное.
ans = 0
s = 0
for i in range(len(a)):
    s += a[i]
    if is_prime(s):
        ans += 1
print(ans)

Ответ: 36 114163