27 задание ЕГЭ
материал для подготовки к егэ (гиа) по информатике и икт (11 класс)

Задание 27 (№1208).

Составьте сумму из N чисел, выбрав из каждой тройки ровно одно число так, чтобы эта сумма не делилась нацело на k = 103 и была максимально возможной.

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

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

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

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

Ответ: 720367, 7871426276

Решение:

Из тройки чисел добавляем в сумму максимальное. Находим минимальную разность, которая не делится нацело на k. Если сумма делится нацело на k = 103, то вычитаем минимальную разность.

Программа:

k = 103

s = 0

razn = 10000

f = open('27_B (1).txt')

N = int(f.readline())

for i in range(N):

    a, b, c = map(int, f.readline().split())

    s += max(a, b, c)

    x = max(a, b, c) - min(a, b, c)

    if x % k !=0 and x < razn:

        razn = x

    sr = a + b + c - max(a, b, c) - min(a, b, c)

    x = max(a, b, c) - sr

    if x % k !=0 and x < razn:

        razn = x

if s % k ==0:

    s -=razn

print(s)

Задание 27 (добровольное тестирование СПб).

Найти контрольное значение – наибольшее число R, удовлетворяющее следующим условиям:

– R – произведение двух различных переданных элементов последовательности («различные» означает, что не рассматриваются квадраты переданных чисел, произведения различных, но равных по величине элементов допускаются);

– R делится на 6.

Решение

Произведение делится на 6:

– один из множителей делится на 6, а другой любой;

– один из множителей делится на 2, а другой на 3.

В наборе данных ищем наибольшие числа, удовлетворяющие этим условиям. Для этих чисел выбираем наибольшее произведение.

Решение в электронных таблицах:

Программа А:

R = 0

a = []

f = open('27A.txt')

N = int(f.readline())

for i in range(N):

    a.append(int(f.readline()))

for i in range(N-1):

    for j in range(i+1, N):

        if a[i]*a[j] % 6 == 0 and a[i]*a[j] > R:

            R = a[i]*a[j]

print(R)

Программа В:

R = 0

f = open('27B.txt')

N = int(f.readline())

d, d2, d3, d6 = 0, 0, 0, 0

for i in range(N):

    a = int(f.readline())

    if a % 2 == 0 and a % 3 !=0 and a > d2:

        d2 = a

    if a % 2 != 0 and a % 3 ==0 and a > d3:

        d3 = a

    if a % 6 == 0 and a > d6:

        if d6 > a:

            d = d6

        d6 = a

    elif a > d:

        d = a

R = max(d*d6, d2*d3)

print(R)

Ответ: 782040, 997002.

Задание 27 (демоверсия)

Дана последовательность из N натуральных чисел. Рассматриваются все её подпоследовательности такие, что сумма элементов каждой из них кратна k = 43. Найдите среди них подпоследовательность с максимальной суммой, определите её длину. Если таких последовательностей найдено несколько, в ответе укажите количество элементов самой короткой из них.

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

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

Решение

Способ 1

k = 43

s, mx, a = 0, 0, 0

f = open('27_B.txt')

N = int(f.readline())

for i in range(N):

    x = int(f.readline())

    if (s+x) % k == 0:

        s += x

        a += 1

    else:

        if s > mx:

            mx = s

            dlina = a

        elif s == mx:

            dlina = min(dlina,a)

        s = 0

        a = 0

print(dlina)

Способ 2

k = 43

s, a = 0, 0

dl = []

ans = []

f = open('27_B.txt')

N = int(f.readline())

for i in range(N):

    x = int(f.readline())

    if (s+x) % k == 0:

        s += x

        a += 1

    else:

        dl.append(a)

        ans.append(s)

        s, a = 0, 0

m = ans.index(max(ans))

print(dl[m])

Ответ: 185, 844158.

Задание 27 (Поляков В-13, 2020-2021)

Решение.

Разность двух чисел кратна m, если остатки от деления этих чисел на m равны. При этом для получения максимальной суммы нужно взять два наибольших числа с одинаковым остатком.

Электронные таблицы

Сортируем столбец А по убыванию и находим два максимальных числа с одинаковым остатком. Максимально возможная сумма 19996 получается для чисел 9998 и 9998.

Программа:

m = 80

m1 = [0] * m

m2 = [0] * m

f = open('27B_13.txt')

N = int(f.readline())

for i in range(N):

    x = int(f.readline())

    p = x % m

    #поиск двух максимумов

    if x > m1[p]:

        m2[p] = m1[p]

        m1[p] = x

    elif x > m2[p]:

        m2[p] = x

s = 0

for i in range(m):

    if m2[i] > 0 and m1[i] + m2[i]> s:

        s = m1[i] + m2[i]

if s == 0:

    print(0)

else:

    print(s)

Ответ: 1728, 19996.