27.03 Цепочки, выбор подпоследовательности, префиксные суммы
Ошибка.
Попробуйте повторить позже
Задание выполняется с использованием прилагаемых файлов
Имеется набор данных, состоящий из положительных целых чисел 
или 
.
Необходимо расположить числа в таком порядке, чтобы максимизировать число сумм на всех префиксах последовательности, которые являются простыми числами. Программа должна напечатать одно число — максимальное количество префиксных сумм, которые являются простыми числами.
Входные данные:
Даны два входных файла (файл А и файл В), каждый из которых содержит в первой строке одно целое число
— количество чисел. Каждая из следующих 
строк содержит натуральное число 
или
.
Пример входного файла:
При таких исходных данных оптимально расположить числа следующим образом: 
или 
. Тогда
префиксные суммы будут равны 
или 
соответственно. Ответ: 
.
В ответе укажите два числа: сначала значение для файла А, затем для файла 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)
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
