Егэ информатика 27 задание динамическое программирование

Разбор задания № 27 ЕГЭ по информатике (динамическое программирование)

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

Если таких подпоследовательностей несколько, выбрать такую, у которой длина меньше.

Входные данные
Файл A
Файл B

Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке количество чисел N (2 ≤ N ≤ 68000). В каждой из последующих N строк записано одно целое положительное число, не превышающее 10000. Программа должна вывести длину найденной последовательности.

Для делителя 50 при указанных входных данных значением искомой суммы должно быть число 100 (3 + 4 + 93 или 5 + 95). Следовательно, ответ на задачу — 2. В ответе укажите два числа: сначала значение искомой суммы для файла A, затем для файла B.

Решение на 1 балл (полный перебор)

Решение на 1 балл основывается на полном переборе и проходит по тесту A. Считываем все данные в список и с помощью вложенного цикла перебираем все возможные длины. Для каждой такой последовательности вычисляем сумму. (сумма элементов среза списка)

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

f = open(‘test.txt’, ‘r’) # открываем файл для чтения
n = int(f.readline())
#mass = [int(x) for x in f.readlines()]

mass = list(map(int, f.readlines())) # считываем в список чисел
# print(mass)

const = 50 # число для проверки кратности
max_sum = 0 # инициализация максимальной суммы

for i in range(n):
for j in range(i, n):
s = sum(mass[i: j + 1]) # вычисляем сумму на отрезке списка

if s % const == 0 and s > max_sum: # если сумма кратна заданному числу и превышает максимальную сумму
max_sum, min_dlina = s, j — i + 1 # перезаписываем максимальную сумму, сохраняем минимальную длину
if s % const == 0 and s == max_sum: # в случае равенства сумм при необходимости перезаписываем минимальную длину
min_dlina = min(min_dlina, j — i + 1)

Решение на 2 балла (эффективный алгоритм)

Будем использовать словарь, в котором ключом будет являться остаток при делении текущей суммы на 89, а значением ключа будет являться кортеж, первый элемент которого хранит текущую сумму, а второй – порядковый номер числа. (начиная с 1)

Используем метод динамического программирования, при котором нам нужно запоминать все возможные значения. Если появился новый остаток, которого не было в словаре, нужно добавить его в словарь. Ключ – остаток при делении суммы на 89, а значение ключа – кортеж из двух чисел. (накопленная сумма и порядковый номер считываемого числа)

Если остаток уже есть в словаре, то нам нужно где-то запомнить разность между текущей накопленной суммой и суммой, хранящейся по этому ключу (остатку) в словаре. Очевидно, что эта разность будет кратна 89. (т.к. остатки совпали)

Чтобы вычислить длину подпоследовательности между двумя числами, следует определять разность по порядковым номерам этих чисел и хранить эти разности. А порядковые номера чисел у нас хранятся во втором элементе кортежа по заданному ключу словаря. Для хранения разностей удобно использовать список кортежей.

Чтобы найти максимальную разность с минимальным расстоянием, сделаем расстояния отрицательными величинами (будет вычитать из меньшего порядкового номера больший). Тогда минимум превратится в максимум, и для поиска ответа нам будет достаточно использовать функцию max(). Для восстановления ответа нужно не забыть поставить знак минус, т.к. полученные расстояния в списке будут отрицательными величинами.

Программа на языке Python (эффективна по времени и памяти)

f = open(‘test.txt’, ‘r’)
k, s = 89, 0 # инициализация значения кратности и суммы

mins = # используем словарь, где ключом будет остаток при делении суммы на величину k
res = [] # список, хранящий подходящие суммы и расстояния

for i in range(1, int(f.readline()) + 1):
s += int(f.readline()) # накапливаем сумму
if s % k in mins: # если остаток есть в словаре
res += [(s — mins[s % k][0], mins[s % k][1] — i)] # вычисляем сумму и расстояние и заносим их как кортеж в список (расстояния будут идти со знаком «-«)
else: # если такого остатка нет в словаре, то добавляем его в словарь
mins[s % k] = (s, i) # создаем новый ключ словаря, значением ключа будет сумма и текущий порядковый номер
print(-max(res)[1]) # выводим ответ

Данное решение проходит по двум тестам и набирает максимальный балл.

Источник

Подготовка к ЕГЭ по информатике (задание 27). Типы задач.

Разобраны основные типы задач, которые встречались в задании 27 ЕГЭ по информатике.

Просмотр содержимого документа
«Подготовка к ЕГЭ по информатике (задание 27). Типы задач.»

Методика подготовки к сдаче ЕГЭ по информатике (Задача 27)

В задании 27 встречаются несколько типов задач. Рассмотрим их подробнее. В качестве источника задач будем использовать сборник «ЕГЭ 2016 Информатика и ИКТ 20 вариантов» С.С. Крылова и Т.Е.Чуркиной.

Тип задач 1 (делимость).

Компьютер наземной станции слежения получает от объектов – самолетов, находящихся в зоне ее работы, идентификационные сигналы, представляющие собой последовательность из N целых положительных чисел. Каждый объект направляет на наземную станцию уникальное число, т.е. все числа в получаемой станцией последовательности различны. Обработка сигнала представляет собой рассмотрение всех пар различных элементов последовательности, при этом элементы пары не обязаны быть переданы непосредственно друг за другом, порядок элементов в паре не важен. Считается, что возникла критическая ситуация, если произведение элементов некоторой пары кратно 58. Необходимо определить общее количество возникших критических ситуаций.

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

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

В качестве результата программа должна напечатать одно число: общее количество возникших критических ситуаций.

Следует учитывать, что в задании 27 возможно несколько вариантов решения задачи и их оценивание при правильном решении варьируется от 2 до 4 баллов. От чего зависит результат? От эффективности работы программы. Простейшая программа, которая сохраняет все входные данные в массиве и потом путем обхода этого массива находящая решение оценивается в 2 балла. Если же полученное решение такого, что при росте количества данных, время выполнения и необходимая память растут линейно, то за такую программу экзаменуемый получает 4 балла.

Вернемся к конкретной задаче и сначала рассмотрим самое простое решение.

1. Ввод и сохранение всего набора данных в массиве.
2. С помощью двух циклов организовываем обход всех пар чисел, находящихся в массиве. Если их произведение делится на 58, то увеличиваем счетчик критических ситуаций.
3. Вывод полученных результатов.

1. Когда оба сомножителя делятся на 58.
2. Только один сомножитель делится на 58.
3. Одно число делится на 2, другое на 29.

1. Ввод данных и сохранение их в массиве.
2. С помощью циклов организация полного перебора и поиск нужного значения.
3. Вывод результатов на печать.

Задача Б требует другого подхода. После считывания каждой пары мы определяем максимальное и минимальное значения. Максимальные величины из разных пар суммируем. В результате получаем максимально возможную сумму. Но, возможен вариант, когда полученное число будет кратно 5. Для решения этой проблемы среди пар числа которых имеют разный остаток от деления на 5 необходимо найти минимальную разность. Тогда если мы отнимем от результата эту величину, то получим максимальную сумму не кратную 5. Ниже следуют примеры на нескольких языках программирования. #include using namespace std; int main() < long int max, max_t, min_t, min_d, temp; int N; max = 0; min_d = 0; cin N; for (int i=0;i cin max_t min_t; if (min_t max_t)< temp = max_t; max_t = min_t; main_t = temp; >max += max_t; temp = max_t – main_t; if (temp%5 != 0) < if (min_d == 0 || min_d temp) min_d = temp; >> If (max %5 != 0) cout else if (min_d 0) < max -= min_d; cout >else cout > Python max = 0 N = int(input()) min_d = 0 for i in range(N): max_t, min_t = map(int, input().split()) if max_t temp=max_t max_t=min_t main_t=temp max += max_t temp = max_t – main_t; if temp%5 != 0 && (min_d == 0 || min_dtemp)): min_d = temp if max%5==0: if min_d0: max -= min_d else: max = 0; print(max)

1. Вместо определения максимального и минимального чисел производится сортировка.
2. При поиске минимума для коррекции результата необходимо учитывать, что мы имеем не пару, а три числа.

1. Считать данные и поместить их в массив.
2. С помощью циклов проверить все пары значений.
3. Вывести результат.

1. Сначала наполняем очередь первыми 15 значениями.
2. Вынимаем из очереди первый зашедший элемент и используем его для определения минимального значения вне 15 сек зоны и, если элемент четный — то и минимального четного вне 15 сек зоны.
3. Считываем новое значение.
4. Если оно четное, то перемножаем его с минимальным значением вне 15 сек зоны, иначе с минимальным четным значением вне 15 сек зоны.
5. Полученное значение сравниваем с минимальным четным значением. При необходимости обновляем минимум.
6. Помещаем ранее считанное значение в конец очереди.
7. Если еще есть значения, то переходим к пункту 2.
8. Выводим результат на печать.

1. Считываем данные, попутно определяя:

Источник