Массивы и последовательности чисел. Вычисление обобщённых характеристик элементов массива или числовой последовательности (суммы, произведения, среднего арифметического, минимального и максимального элементов, количества элементов, удовлетворяющих заданному условию). Линейный поиск заданного значения в массиве. Алгоритмы работы с элементами массива с однократным просмотром массива. Сортировка одномерного массива. Простые методы сортировки (метод пузырька, метод выбора, сортировка вставками). Сортировка слиянием. Быстрая сортировка массива (алгоритм QuickSort). Двоичный поиск в отсортированном массиве — ЕГЭ по информатике — страница 11

Задание выполняется с использованием прилагаемых
файлов.

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

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

В первой строке входного файла находится число N – количество форм для коржей в кондитерской (натуральное число,
не превышающее 10 000). В следующих N строках находятся значения диаметров форм для коржей (все числа натуральные,
не превышающие 10 000), каждое – в отдельной строке. Диаметр формы равен диаметру коржа, который выпекается в этой в форме.

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

Типовой пример организации данных во входном файле

5

43

40

32

40

30

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

При таких исходных данных условию задачи удовлетворяют наборы коржей с диаметрами 30, 40 и 43 или 32, 40 и 43 соответственно, т.е. количество коржей равно 3, а максимально возможный диаметр самого маленького коржа равен 32.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.

Задание выполняется с использованием прилагаемых
файлов.

При онлайн-покупке билета на концерт известно, какие места в зале уже заняты. Необходимо купить два билета на такие соседние места в одном ряду, чтобы перед ними все кресла с такими же номерами были свободны, а ряд находился как можно дальше от сцены. Если в этом ряду таких пар мест несколько, найдите пару с наибольшими номерами. В ответе запишите два целых числа: искомый номер ряда и наибольший номер места в найденной паре. Нумерация рядов и мест ведётся с 1. Гарантируется, что хотя бы одна такая пара в зале есть.

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

В первой строке входного файла находятся три числа: N – количество занятых мест в зале (целое положительное число,
не превышающее 10 000), M – количество рядов (целое положительное число, не превышающее 100 000) и K – количество мест в каждом ряду (целое положительное число, не превышающее 100 000). В следующих N строках находятся пары натуральных чисел: номер ряда и номер места занятого кресла соответственно (первое число не превышает значения M, а второе – K).

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

Два целых положительных числа: наибольший номер ряда
и наибольший номер места в найденной паре кресел.

Типовой пример организации данных во входном файле

7 7 8

1 1

6 6

5 5

6 7

4 4

2 2

3 3

При таких исходных данных ответом является пара чисел 5 и 8. Условию задачи удовлетворяют места 7 и 8 в ряду 5: перед креслами 7 и 8 нет занятых мест и это последняя из двух возможных пар в этом ряду. В рядах 6 и 7 искомую пару найти нельзя.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

Задание выполняется с использованием прилагаемых файлов.

Сервер выполняет запросы на передачу данных, при этом сведения
о каждом выполненном запросе (время регистрации, идентификатор клиента и объём переданных данных) сохраняются в журнале работы, а сам запрос $–$ в специальном разделе памяти сервера, имеющем ограниченный объём. Каждый раз, когда в специальном разделе остаётся недостаточно свободной памяти, сервер создаёт резервную копию всех накопленных там данных, после чего освобождает раздел и продолжает выполнение запросов. Напишите программу для обработки журнала работы сервера и с её помощью определите наименьший суммарный объём данных, переданных на сервер с двух клиентских устройств (не менее 150 000 Кбайт
с каждого устройства), а также наименьший объём резервной копии специального раздела (в Кбайт), выполненной не позднее 11:59:59.

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

Первая строка входного файла (журнала работы сервера) содержит два натуральных числа: N (N < 1 000 000) $–$ количество строк
в журнале и K (K < 1 000 000) $–$ вместимость специального раздела памяти сервера в Кбайт. Каждая из следующих N строк содержит информацию об одном выполненном запросе: время регистрации запроса в формате ЧЧ:ММ:СС (часы, минуты, секунды) и два натуральных числа: C (C < 1 000 000) $–$ идентификатор клиентского устройства и S (S < K) $–$ объём данных запроса в Кбайт.

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

В ответе запишите два числа: сначала наименьший суммарный объём данных с двух клиентских устройств (не менее 150 000 Кбайт с каждого устройства), а затем наименьший объём резервной копии (в Кбайт), выполненной не позднее 11:59:59.

Типовой пример организации данных во входном файле

8 140000

01:01:01 101 20000

03:03:03 202 110000

05:05:05 101 90000

07:07:07 303 62000

10:10:10 101 48000

15:15:15 202 12000

21:21:21 303 120000

23:23:23 404 134000

При таких исходных данных резервное копирование специального раздела выполняется четыре раза: в 05:05:05 (в объёме
130 000 Кбайт), в 07:07:07 (в объёме 90 000 Кбайт), в 21:21:21
(в объёме 122 000 Кбайт) и в 23:23:23 (в объёме 120 000 Кбайт). Всего на сервер передано 596 000 Кбайт данных: 158 000, 122 000,
182 000 и 134 000 Кбайт от клиентов с идентификаторами 101,
202, 303 и 404 соответственно. Ответ для приведённого примера: 340 000        90 000.

Типовой пример имеет иллюстративный характер.
Для выполнения задания используйте данные из прилагаемого файла.

Задание выполняется с использованием прилагаемых
файлов.

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

Определите три таких переданных числа, чтобы между моментами передачи любых двух из них прошло не менее K мин., а сумма этих трёх чисел была минимально возможной. Запишите в ответе найденную сумму.

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

Даны два входных файла (файл A и файл B), каждый из которых
в первой строке содержит натуральное число K – минимальное количество минут, которое должно пройти между моментами передачи показаний, а во второй – количество переданных показаний N (1 ≤ N ≤ 10 000 000, N > K). В каждой из следующих
N строк находится одно натуральное число, не превышающее 10 000 000, которое обозначает значение силы тока в соответствующую минуту.

Запишите в ответе два числа: сначала значение искомой величины для файла А, затем – для файла B.

Типовой пример организации данных во входном файле

2

6

15

14

20

23

21

10

При таких исходных данных искомая величина равна 45 – это сумма значений, зафиксированных на первой, третьей и шестой минутах измерений.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.

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

Задание выполняется с использованием прилагаемых
файлов.

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

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

В первой строке входного файла находится натуральное число N
(N ≤ 1000) – количество заявок на проведение мероприятий. Следующие N строк содержат пары чисел, обозначающих время начала и время окончания мероприятий. Каждое из чисел натуральное, не превосходящее 1440.

Запишите в ответе два числа: максимальное количество мероприятий и самый длинный перерыв между двумя последними мероприятиями (в минутах).

Типовой пример организации данных во входном файле

5

10 150

100 120

131 170

150 180

120 130

При таких исходных данных можно провести максимум три мероприятия, например, мероприятия по заявкам 2, 3 и 5. Максимальный перерыв между двумя последними мероприятиями составит 20 мин., если состоятся мероприятия по заявкам 2, 4 и 5.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.

Задание выполняется с использованием прилагаемых
к заданию файлов.

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

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

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

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

7

1

3

4

43

8

5

95

Для указанных входных данных при k = 50 искомая длина последовательности равна 2.

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

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