Последняя задача ЕГЭ

Упражнения

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

Входные данные для всех задач записаны в файле input.txt или на стандартном вводе, результат работы нужно вывести в файл output.txt или на стандартный вывод.

В случае использования файлового ввода-вывода, повторное открытие и считывания файла запрещено.

A: ЕГЭ-2013, наибольшее произведение, кратное 21

Решение должно использовать \(O(1)\) памяти и иметь сложность \(O(N)\).

По каналу связи передаётся последовательность из \(N\) целых положительных чисел. Количество чисел может быть очень велико.

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

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

2) R делится на 21.

Если такого числа R нет, то контрольное значение полагается равным 0.

Напишите эффективную, в том числе по используемой памяти, программу которая будет вычислять контрольное значение.

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

Ввод Вывод
70
21
997
7
9
300
21000

B: ЕГЭ-2017, количество пар, произведение делится на 26

Решение должно использовать \(O(1)\) памяти и иметь сложность \(O(N)\).

На вход программы поступает последовательность из \(N\) целых положительных чисел, все числа в последовательности различны. Рассматриваются все пары различных элементов последовательности (элементы пары не обязаны стоять в последовательности рядом, порядок элементов в паре не важен). Необходимо определить количество пар, для которых произведение элементов делится на 26.

В каждой строке входного файла записано одно целое положительное число.

В качестве результата программа должна напечатать одно число: количество пар, в которых произведение элементов кратно 26.

Ввод Вывод
2
6
13
39
4

Примечание. Из четырёх заданных чисел можно составить 6 попарных произведений: 2·6, 2·13, 2·39, 6·13, 6·39, 13·39 (результаты: 12, 26, 78, 78, 234, 507). Из них на 26 делятся 4 произведения (2·13=26; 2·39=78; 6·13=78; 6·39=234).

C: ЕГЭ-2016, составить максимальную не делящуюся на 3 сумму

Решение должно использовать \(O(1)\) памяти и иметь сложность \(O(N)\).

Имеется набор данных, состоящий из \(N\) пар целых положительных чисел. Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма всех выбранных чисел не делилась на 3 и при этом была максимально возможной. Если получить требуемую сумму невозможно, в качестве ответа нужно выдать 0.

Каждая строка входного файла содержит два целых положительных числа, не превосходящих 10.000 каждое.

Ввод Вывод
1 3
5 12
6 9
5 4
3 3
1 1
32

D: ЕГЭ-2012, Камера хранения

Решение должно использовать \(O(K)\) памяти и иметь сложность \(O(NK)\), где \(N\) — количество пассажиров, \(K\) — количество ячеек.

На вход программе подаются сведения о пассажирах, желающих сдать свой багаж в камеру хранения на заранее известное время до полуночи. В первой строке дано количество ячеек в камере хранения \(K\). Каждая из следующих строк имеет следующий формат:

<Фамилия> <время сдачи багажа> <время освобождения ячейки>
где <Фамилия> – строка, состоящая не более чем из 20 непробельных символов; <время сдачи багажа> – через двоеточие два целых числа, соответствующие часам (от 00 до 23 – ровно 2 символа) и минутам (от 00 до 59 – ровно 2 символа); <время освобождения ячейки> имеет тот же формат. <Фамилия> и <время сдачи багажа>, а также <время сдачи багажа> и <время освобождения ячейки> разделены одним пробелом. Время освобождения больше времени сдачи.

Сведения отсортированы в порядке времени сдачи багажа. Если два пассажира приходят в одно время, то сначала обслуживается тот пассажир, который указан раньше во входных данных. Каждому из пассажиров в камере хранения выделяется свободная ячейка с минимальным номером. Если в момент сдачи багажа свободных ячеек нет, то пассажир уходит, не дожидаясь освобождения одной из них.

Требуется написать программу, которая будет выводить на экран для каждого пассажира номер ему предоставленной ячейки (можно сразу после ввода данных очередного пассажира). Если ячейка пассажиру не предоставлена, то его фамилия не печатается.

Ввод Вывод
10
Иванов 09:45 12:00
Петров 10:00 11:00
Сидоров 12:00 13:12
Иванов 1
Петров 2
Сидоров 1
1
Иванов 09:45 12:00
Петров 10:00 11:00
Сидоров 12:00 13:12
Иванов 1
Сидоров 1

E: ЕГЭ-2010, Палиндром

Решение должно иметь сложность \(O(N)\) и использовать \(O(1)\) памяти (\(N\) — длина входной строки). В частности, это означает, что чтение данных должно быть посимвольным.

Дана строка, состоящая только из заглавных латинский букв. Используя все или некоторые символы этой строки составьте строку максимальной длины, являющуюся палиндромом (то есть одинаково читающуюся слева направо и справа налево). Если таких строк несколько, то выведите минимальный в лексикографическом порядке палиндром.

Ввод Вывод
PARALLELOGRAM
ALRARLA
ONE
E

F: ЕГЭ-2011, Задачи олимпиады

Решение должно использовать \(O(1)\) памяти.

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

В каждой строке входного файла записано название задачи в виде текстовой строки. Длина строки не превосходит 100 символов, название может содержать буквы, цифры, пробелы и знаки препинания.

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

Порядок вывода — лексикографический порядок названий задач.

Ввод Вывод
A+B
Крестики-Нолики
Прямоугольник
Простой делитель
A+B
Простой делитель
А+В 2
Крестики-Нолики 1
Простой делитель 2
Прямоугольник 1

G: ЕГЭ-2009, проходной балл

Решение должно иметь сложность \(O(N + K)\) и использовать \(O(K)\) памяти (\(K\) — максимально возможный балл абитуриента, \(N\) — число абитуриентов). Чтение входных данных должно быть построчным, нельзя создавать массив, размер которого зависел бы от входных данных.

Для поступления в вуз абитуриент должен предъявить результаты трех экзаменов в виде ЕГЭ, каждый из них оценивается целым числом от 0 до 100 баллов. При этом абитуриенты, набравшие менее 40 баллов (неудовлетворительную оценку) по любому экзамену из конкурса выбывают. Остальные абитуриенты участвуют в конкурсе по сумме баллов за три экзамена.

В конкурсе участвует \(N\) человек, при этом количество мест равно \(K\). Определите проходной балл, то есть такое количество баллов, что количество участников, набравших столько или больше баллов не превосходит \(K\), а при добавлении к ним абитуриентов, набравших наибольшее количество баллов среди непринятых абитуриентов, общее число принятых абитуриентов станет больше \(K\).

Программа получает на вход количество мест \(K\). Далее идут строки с информацией об абитуриентах, каждая из которых состоит из фамилии, имени и трех чисел от 0 до 100, разделенных пробелами.

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

Также возможны две ситуации, когда проходной балл не определен.

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

Если количество абитуриентов, имеющих равный максимальный балл больше чем \(K\), программа должна вывести число 1.

Ввод Вывод
5
Иванов Сергей 70 70 70
Сергеев Петр 100 100 0
Петров Василий 70 60 70
Васильев Андрей 70 60 70
Андреев Денис 100 30 100
Денисов Роман 50 50 50
Романов Григорий 60 70 70
Григорьев Станислав 50 50 50
Станиславский Иван 40 40 40
200
1
Иванов Сергей 40 40 40
Сергеев Петр 100 100 39
0
1
Иванов Сергей 60 60 60
Сергеев Петр 100 40 40
1

H: ЕГЭ-2009, полупроходной балл

Требования к решению аналогичны предыдущей задаче

В условиях предыдущей задачи определите полупроходной балл, то есть такое значение балла, что количество абитуриентов, набравших балл выше полупроходного, меньше \(K\), а количество абитурентов, набравших балл выше или равный полупроходному, больше \(K\).

Программа должна вывести значение полупроходного балла, если полупроходного балла не существует, программа должна вывести одно число 0.

Ввод Вывод
5
Иванов Сергей 70 70 70
Сергеев Петр 100 100 0
Петров Василий 70 60 70
Васильев Андрей 70 60 70
Андреев Денис 100 30 100
Денисов Роман 50 50 50
Романов Иван 60 70 70
Григорьев Станислав 50 50 50
Станиславский Иван 40 40 40
150
1
Иванов Сергей 50 50 50
Сергеев Петр 100 100 100
Петров Иван 100 0 100
0

I: ЕГЭ-2009, Призеры олимпиады

Требования к решению аналогичны предыдущей задаче

Условия этой задачи соответствуют пункту 58 положения о всероссийской олимпиаде школьников, действовавшего в те годы.

В олимпиаде участвовало \(N\) человек, каждый из которых мог набрать от 0 до 100 баллов. По положению об олимпиаде жюри может наградить не более 45% от числа участников, округляя их число до целого при необходимости вниз.

При этом если последний участник, попавший в 45% набирает столько же баллов, сколько первый участник, не попавший в 45%, то решение по этим участникам, и всем участникам, набравшим такой балл принимается следующим образом:

Все данные участники объявляются призерами, если набранный ими балл больше половины от максимально возможного балла.

Все эти участники не объявляются призерами, если набранный ими балл не больше половины от максимально возможного.

Программа получает на вход информацию об участниках олимпиады (один участник в одной строке). Строка содержит фамилию и имя участника и набранный данным участником балл через пробел.

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

Ввод Вывод
Иванов Сергей 70
Сергеев Петр 30
Петров Василий 40
Васильев Андрей 80
Андреев Денис 50
Денисов Роман 90
Романов Иван 70
Иванов Григорий 60
Григорьев Сергей 100
70
Иванов Сергей 50
Сергеев Петр 70
Петров Василий 40
Васильев Андрей 10
Андреев Денис 50
Денисов Роман 20
Романов Иван 30
Иванов Григорий 70
Григорьев Сергей 100
70
Иванов Сергей 30
Сергеев Петр 60
Петров Василий 20
Васильев Андрей 100
Андреев Денис 30
Денисов Роман 80
Романов Иван 20
Иванов Григорий 40
Григорьев Сергей 10
40

J: Поезда

Это тренировочная задача по мотивам задач ЕГЭ.

Решение должно использовать \(O(K)\) памяти и иметь сложность \(O(K + N)\), где \(K\) — число станций, \(N\) — количество пассажиров.

Некоторый поезд в пути следования останавливается на \(K\) станциях (станция номер 1 — начальная, а станция номер \(K\) — конечная). Дан список пассажиров поезда, для каждого из которых известно, на какой станции он садится, а на какой выходит. Определите, на каких перегонах (то есть между какими соседними станциями) в поезде было наибольшее число пассажиров.

Первая строка входного файла содержит количество станций \(K\). В следующих строках находится информация о пассажирах в следующем формате:

Фамилия Имя станция_посадки станция_выхода
где Фамилия и Имя — строки, состоящие не более, чем из 20 символов без пробелов, станция_посадки и станция_выхода — числа от 1 до \(K\), при этом номер станции посадки меньше номера станции выхода.

Программа должна вывести список перегонов, на которых в поезде было набольшее число пассажиров, в порядке возрастания номеров. Каждый перегон выводится в виде двух последовательных номеров станций, разделенных знаком “-”.

Ввод Вывод
5
Иванов Сергей 1 5
Сергеев Петр 3 5
Петров Кирилл 1 2
1-2
3-4
4-5

K: ЕГЭ-2014, минимальное произведение, на расстоянии не менее 6

Решение должно использовать \(O(1)\) памяти и иметь сложность \(O(N)\).

На спутнике «Фотон» установлен прибор, предназначенный для измерения энергии космических лучей. Каждую минуту прибор передаёт по каналу связи неотрицательное вещественное число — количество энергии, полученной за последнюю минуту, измеренное в условных единицах. Временем, в течение которого происходит передача, можно пренебречь.

Необходимо найти в заданной серии показаний прибора минимальное произведение двух показаний, между моментами передачи которых прошло не менее 6 минут.

Каждая из \(N\) строк входных данных содержит одно неотрицательное вещественное число – очередное показание прибора, \(N\ge 7\). Входные числа не превосходят 40.000 каждое.

Программа должна вывести одно число – описанное в условии произведение.

Ввод Вывод
12
45
5.5
4
25
23
21
20
10
12
26
48.0

L: ЕГЭ-2015, минимальное чётное произведение на расстоянии не менее 6

Решение должно использовать \(O(1)\) памяти и иметь сложность \(O(N)\).

В физической лаборатории проводится долговременный эксперимент по изучению гравитационного поля Земли. По каналу связи каждую минуту в лабораторию передаётся положительное целое число – текущее показание прибора «Сигма 2015». Временем, в течение которого происходит передача, можно пренебречь.

Необходимо вычислить «бета-значение» серии показаний прибора – минимальное чётное произведение двух показаний, между моментами передачи которых прошло не менее 6 минут. Если получить такое произведение не удаётся, ответ считается равным –1.

Каждая из \(N\) строк входных данных содержит одно положительное целое число – очередное показание прибора, \(N\ge 7\). Входные числа не превосходят 40.000 каждое.

Программа должна вывести одно число – описанное в условии произведение либо –1, если получить такое произведение не удаётся.

Ввод Вывод
12
45
5
3
17
23
21
20
19
18
17
54

M: ЕГЭ-2018, количество пар на расстоянии не менее 4, произведение делится на 29

На вход программы поступает последовательность из N целых положительных чисел, все числа в последовательности различны. Рассматриваются все пары различных элементов последовательности, находящихся на расстоянии не меньше чем 4 (разница в индексах элементов пары должна быть 4 или более, порядок элементов в паре неважен). Необходимо определить количество таких пар, для которых произведение элементов делится на 29.

В каждой строке входного файла записано одно целое положительное число, не превышающее 10000. Количество чисел на входе не меньше 5.

Программа должна вывести одно число: количество пар элементов, находящихся в последовательности на расстоянии не меньше чем 4, в которых произведение элементов кратно 29.

Ввод Вывод
58
2
3
5
4
1
29
5

Примечание. Из 7 заданных элементов с учётом допустимых расстояний между ними можно составить 6 произведений: 58·4, 58·1, 58·29, 2·1, 2·29, 3·29. Из них на 29 делятся 5 произведений.

N: Школа танцев

А эта милая задача взята с заключительного этапа всероссийской олимпиады школьников по информатике. Только это не последняя, а первая задача варианта.

Решение должно иметь сложность \(O(n)\), ограничение по памяти \(O(n)\).

В школу бальных танцев профессора Падеграса записались \(n\) учеников — мальчиков и девочек. Профессор построил их в один ряд, и хочет отобрать из них для первого занятия группу стоящих подряд учеников, в которой количество мальчиков и девочек одинаково. Сколько вариантов выбора есть у профессора?

В первой строке задано число \(n\) (\(1 \le n \le 10^6\)). Во второй строке задается описание построенного ряда из мальчиков и девочек — строка из \(n\) символов a и b (символ a соответствует девочке, а символ b — мальчику).

В единственной строке должно содержаться единственное число — количество вариантов выбора требуемой группы.

Ввод Вывод
3
bab
2
8
abbababa
13