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

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

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

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

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

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

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

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

В первой строке входного файла находится натуральное число 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.

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

В магазине для упаковки подарков есть N кубических коробок красного цвета и M кубических коробок синего цвета (N>M). Самой интересной считается упаковка подарка по принципу матрёшки – подарок упаковывается в одну из коробок, та, в свою очередь, в другую коробку и т.д, при этом цвет коробок чередуется. Одну коробку можно поместить в другую, если длина её стороны хотя бы на 5 единиц меньше длины стороны другой коробки. Определите наибольшее количество коробок, которое можно использовать для упаковки одного подарка, и максимально возможную длину стороны самой маленькой из этих коробок. Размер подарка позволяет поместить его в самую маленькую коробку.

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

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

Типовой пример организации данных во входном файле
5             4
39          55
40          42
44          44
40          55
50

Пример входного файла приведён для пяти коробок красного цвета и четырёх коробок синего цвета, когда минимальная допустимая разница между длинами сторон коробок, подходящих для упаковки «матрёшкой», составляет 3 единицы.
При таких исходных данных условию задачи удовлетворяют наборы коробок с длинами сторон 39, 42, 50 и 55 или 40, 44, 50 и 55 соответственно, т.е. количество коробок равно 4, а длина стороны самой маленькой коробки равна 40.

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