Тренажёр ЕГЭ по информатике: задания с решениями

Менеджеры интернет-магазина составляют рейтинговый список новых моделей смартфонов по данным о продолжительности автономной работы устройства в режиме ожидания и в активном режиме использования. У каждой модели известны оба показателя. Для объективности бренды и марки устройств скрыты, в списке все смартфоны пронумерованы начиная с единицы.
Алгоритм формирования рейтинга выглядит следующим образом:
— все 2N чисел, обозначающих продолжительности работы в режиме ожидания и в режиме активного использования для N устройств, располагаются по возрастанию;
— если наименьший показатель соответствует продолжительности работы в режиме ожидания, устройство занимает первое свободное место от начала рейтинга;
— если наименьший показатель относится к продолжительности работы в активном режиме использования смартфона, устройство занимает первое свободное место от конца рейтинга;
— показатели устройств, ранее включённых в рейтинговый список, игнорируются.

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

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

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

Типовой пример организации данных во входном файле
5
800 120
150 200
250 300
60 100
180 220
Пример организации данных приведён для пяти смартфонов.

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

Организаторам спортивных соревнований необходимо доставить как можно большее число команд в некоторый город. Для доставки используются самолёты определённой пассажировместимости. Входной файл содержит сведения о количестве человек в команде и о пассажировместимости самолётов, которые имеются в наличии. Из соображений безопасности в одном самолёте может лететь только одна команда. Найдите способ доставить на соревнования максимально возможное число команд. Если способов несколько, то нужно выбрать такой, чтобы можно было доставить команды с максимальным числом участников.

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

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

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

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

В рейтинговом списке маркетологи располагают продукты по следующему алгоритму:
 – все 2N чисел, обозначающих срок хранения и срок годности к употреблению для N продуктов, упорядочивают по возрастанию;
 – если минимальное число в этом упорядоченном списке – срок хранения, то продукт в рейтинге занимает первое свободное место от
его начала;
 – если минимальное число – срок годности к употреблению, то продукт занимает первое свободное место от конца рейтинга;
 – если число обозначает срок хранения или срок годности к употреблению уже рассмотренного продукта, то его не принимают во внимание.
Этот алгоритм применяется последовательно для размещения всех N продуктов.
Определите номер последнего продукта, для которого будет определено его место в рейтинге, и количество продуктов, которые займут в рейтинге более низкие места.

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

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

На соревнованиях по спортивнориентированию каждый участник должен пройти маршрут, посещая контрольные точки. Все контрольные точки пронумерованы натуральными числами начиная с 1. В начале сезона соревнований каждому спортсмену присваивается уникальный номер — натуральное число, не превышающее 1 000 000. Жюри фиксирует факт прохождения спортсменом контрольной точки. На разных этапах соревнований спортсмен может посетить одну и ту же контрольную точку в произвольном порядке несколько раз или не посетить совсем.
Тренер в конце сезона анализирует результаты этапов соревнования, чтобы выявить контрольную точку, которую посетило наибольшее
число спортсменов с идущими подряд номерами. Определите максимальное число спортсменов с идущими подряд номерами и номер найденной контрольной точки. Если таких групп спортсменов несколько, укажите наименьший номер посещённой группой контрольной точки.

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

В первой строке входного файла находится число N (натуральное число, не превышающее 1 000 000) — количество посещений спортсменами контрольных точек в течение всего сезона соревнований. Каждая из следующих N строк содержит два натуральных числа, не превышающих 1 000 000: номер спортсмена и номер посещённой им контрольной точки.

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

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

Типовой пример организации входных данных
9
41 3
43 125
50 33
42 125
42 126
42 127
41 125
50 126
42 126
Для приведённого примера точку с номером 125 посетили три спортсмена с номерами 41, 42 и 43. Ответом является пара чисел: 3; 125.

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

Входной файл содержит информацию о заявках граждан, обращающихся во многофункциональный центр (МФЦ) в течение календарных суток. В заявке указаны время начала и время окончания приёма специалистом (в минутах от начала суток).
Рабочие места специалистов МФЦ (окна) пронумерованы натуральными числами начиная с 1. Приём одного гражданина ведёт свободный специалист в окне с минимальным номером. Новый посетитель может обратиться к освободившемуся специалисту начиная со следующей минуты после завершения приёма предыдущего. Если в момент обращения в МФЦ свободных специалистов нет, то гражданин уходит. Определите, сколько граждан смогут попасть на приём в МФЦ в течение 24 ч, и каков номер окна специалиста, который начнёт принимать посетителя последним. Если таких окон несколько, укажите наименьший номер окна.

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

В первой строке входного файла находится натуральное число К, не превышающее 1000, — количество окон в МФЦ. Во второй строке
натуральное число N (N ≤ 10 000), обозначающее количество граждан. Каждая из следующих N строк содержит два натуральных числа, каждое из которых не превышает 1440: указанные в заявке время начала и время окончания приёма (в минутах от начала суток).
Запишите в ответе два числа: количество граждан, которые смогут воспользоваться услугами МФЦ, и номер окна, в котором специалист примет последнего гражданина.

Типовой пример организации данных во входном файле
2
5
30 60
40 100
59 60
61 100
101 144
При таких исходных данных воспользоваться услугами МФЦ смогут первый, второй, четвёртый и пятый граждане. Наименьший номер окна, где последний из граждан будет принят специалистом, — 1, так как будут свободны окна 1 и 2.

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

На производстве штучных изделий N деталей должны быть отшлифованы и окрашены. Для каждой детали известно время её шлифовки и время окрашивания. Детали пронумерованы начиная с единицы. Параллельная обработка деталей не предусмотрена. На ленте транспортёра имеется N мест для каждой из N деталей.

На ленте транспортёра детали располагают по следующему алгоритму:

— все 2N чисел, обозначающих время окрашивания и шлифовки для N деталей, упорядочивают по возрастанию;
 — если минимальное число в этом упорядоченном списке — это время шлифовки конкретной детали, то деталь размещают на ленте транспортёра на первое свободное место от её начала;
 — если минимальное число — это время окрашивания, то деталь размещают на первое свободное место от конца ленты транспортёра
 — если число обозначает время окрашивания или шлифовки уже рассмотренной детали, то его не принимают во внимание.

Этот алгоритм применяется последовательно для размещения всех N деталей.

Определите номер последней детали, для которой будет определено её место на ленте транспортёра, и количество деталей, которые
будут отшлифованы до неё.

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

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

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

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

5
30 50
100 155
150 170
10 160
120 55

При таких исходных данных порядок расположения деталей на ленте транспортёра следующий: 4, 1, 2, 3, 5. Последней займёт своё место на ленте транспортёра деталь 3. При этом до неё будут отшлифованы три детали.

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

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

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

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

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

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

5
-20 120
90 20
147 43
150 30
120 20

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

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

Петя участвует в расширенной версии игры «Морской бой». В данной версии игры, в отличие от классической, допускается увеличение количества и длины кораблей, а игровое поле может быть прямоугольным, размером M x K, где M – количество горизонтальных рядов клеток на игровом поле (целое положительное число, не превышающее 100 000), K – количество вертикальных рядов клеток на игровом поле (целое положительное число, не превышающее 100 000). Нумерация горизонтальных рядов поля идёт сверху вниз с 1, а вертикальных – слева направо также с 1. Некоторые клетки поля уже заняты кораблями (n-палубный корабль занимает, соответственно, n подряд идущих клеток).

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

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

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

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

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

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

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

6 6 8
1 1
5 5
5 6
4 4
2 2
3 3

При таких исходных данные ответом является пара чисел 4 и 8. Условию задачи удовлетворяет расположение корабля в вертикальных рядах 6, 7 и 8 игрового поля в горизонтальном ряду 4.

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

Петя участвует в расширенной версии игры «Морской бой». В данной версии игры, в отличие от классической, допускается увеличение количества и длины кораблей, а игровое поле может быть прямоугольным, размером M x K, где M – количество горизонтальных рядов клеток на игровом поле (целое положительное число, не превышающее 100 000), K – количество вертикальных рядов клеток на игровом поле (целое положительное число, не превышающее 100 000). Нумерация горизонтальных рядов поля идёт сверху вниз с 1, а вертикальных – слева направо также с 1. Некоторые клетки поля уже заняты кораблями (n-палубный корабль занимает, соответственно, n подряд идущих клеток).

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

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

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

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

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

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

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

6 6 7
1 1
5 5
5 6
4 4
2 2
3 3

При таких исходных данные ответом является пара чисел 4 и 5. Условию задачи удовлетворяет расположение корабля в вертикальных рядах 5 и 6 игрового поля в горизонтальном ряду 4.

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

Илье необходимо перенести файлы с одного компьютера на другой при помощи внешнего жёсткого диска.

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

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

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

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

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

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

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

100 4
80
30
50
40

При таких исходных данных можно сохранить файлы максимум двух пользователей. Возможные объёмы этих двух файлов: 30 и 40, 30 и 50 или 40 и 50. Наибольший объём файла из перечисленных пар – 50, поэтому ответ для приведённого примера: 2, 50.

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