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

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

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

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

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

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

6

1 3 7

5 12 6

6 9 11

5 4 8

3 5 4

1 1 1

Для указанных входных данных в случае, если k = 5, искомой суммой является число 44.

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

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

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

Имеется набор данных, состоящий из положительных целых чисел, каждое из которых не превышает 1000. Требуется найти для этой последовательности контрольное значение – наибольшее число R, удовлетворяющее следующим условиям:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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