Банк заданий ЕГЭ по информатике - страница 43
Вопросы
Петя участвует в расширенной версии игры «Морской бой». В данной версии игры, в отличие от классической, допускается увеличение количества и длины кораблей, а игровое поле может быть прямоугольным, размером М х К, где М — количество горизонтальных рядов клеток на игровом поле (целое положительное число, не превышающее 100000), K — количество вертикальных рядов клеток на игровом поле (целое положительное число, не превышающее 100 000). Нумерация горизонтальных рядов поля идёт сверху вниз с 1, а вертикальных — слева направо также с 1. Некоторые клетки поля уже заняты кораблями (n-палубный корабль занимает, соответственно, n подряд идущих клеток).
Пете необходимо разместить 1-палубный корабль, расположив его на свободной клетке игрового поля так, чтобы до ближайшего по направлению вверх препятствия (корабля, части многопалубного корабля или края игрового поля) было как можно больше свободных клеток. Допускается ставить корабли вплотную друг к другу.
Если горизонтальных рядов для удовлетворяющего условию размещения корабля несколько, то необходимо указать горизонтальный ряд с наименьшим номером. В ответе запишите два целых числа: номер горизонтального ряда и количество свободных клеток до ближайшего по направлению вверх препятствия. Гарантируется, что хотя бы одно удовлетворяющее условию место для корабля есть.
Входные данные.
В первой строке входного файла находятся три числа: N - количество клеток игрового поля, в которых расположены однопалубные корабли или части многопалубных кораблей (N - целое положительное число, не превышающее 100 000), М - количество горизонтальных рядов игрового поля и К - количество вертикальных рядов игрового поля. В следующих N строках соответственно находятся пары натуральных чисел: номер горизонтального ряда и номер вертикального ряда игрового поля, в которых расположены корабли или их части (первое число не превышает значения М, а второе - K).
Входные данные.
Два целых положительных числа: соответственно искомые номера горизонтального ряда и вертикального ряда.
Типовой пример организации данных во входном файле
7 6 6
2 1
2 4
4 2
5 3
6 1
4 5
5 6
При таких исходных данных ответом является пара чисел 4 и 3.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.
В ответ запишите два искомых числа через пробел
Входной файл содержит сведения о мероприятиях, в которых приглашен участвовать директор фирмы. Для каждого мероприятия указаны время начала и длительность его проведения (в минутах от начала суток). Если время начала одного мероприятия меньше времени окончания другого, то руководитель может принять участие только в одном из них. Если время окончания одного мероприятия совпадает со временем начала другого, то руководитель может принять участие в обоих мероприятиях (очно или дистанционно). Определите, в каком максимальном количестве мероприятий может принять участие руководитель и каков при этом максимально возможный перерыв между двумя последними мероприятиями.
Входные данные.
В первой строке входного файла находится натуральное число N (N ≤ 1000) - количество заявок на проведение мероприятий. Следующие N строк содержат пары чисел, обозначающих время начала и длительность мероприятия. Каждое из чисел натуральное, не превосходящее 1440. Запишите в ответе два числа: максимальное количество мероприятий и самый длинный перерыв между двумя последними мероприятиями (в минутах).
Типовой пример организации данных во входном файле
5
20 120
90 20
147 43
150 30
120 20
При таких исходных данных можно провести максимум три мероприятия, например, мероприятия по заявкам 2, 3 и 5. Максимальный перерыв между двумя последними мероприятиями составит 10 мин., если состоятся мероприятия по заявкам 2, 4 и 5.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.
В ответ запишите два искомых числа через пробел
Входной файл содержит сведения о мероприятиях, в которых приглашен участвовать директор фирмы. Для каждого мероприятия указаны время начала и длительность его проведения (в минутах от начала суток). Если время начала одного мероприятия меньше времени окончания другого, то руководитель может принять участие только в одном из них. Если время окончания одного мероприятия совпадает со временем начала другого, то руководитель может принять участие в обоих мероприятиях (очно или дистанционно). Определите, в каком максимальном количестве мероприятий может принять участие руководитель и каков при этом максимально возможный перерыв между двумя последними мероприятиями.
Входные данные.
В первой строке входного файла находится натуральное число N (N ≤ 1000) - количество заявок на проведение мероприятий. Следующие N строк содержат пары чисел, обозначающих время начала и длительность мероприятия. Каждое из чисел натуральное, не превосходящее 1440. Запишите в ответе два числа: максимальное количество мероприятий и самый длинный перерыв между двумя последними мероприятиями (в минутах).
Типовой пример организации данных во входном файле
5
20 120
90 20
147 43
150 30
120 20
При таких исходных данных можно провести максимум три мероприятия, например, мероприятия по заявкам 2, 3 и 5. Максимальный перерыв между двумя последними мероприятиями составит 10 мин., если состоятся мероприятия по заявкам 2, 4 и 5.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.
В ответ запишите два искомых числа через пробел
Дети играют в следующую игру. На бесконечном разлинованном на клетки листе введена декартова система координат, при этом клетки таковы, что их вершины находятся во всех точках плоскости, для которых обе координаты целочисленные. Есть некоторое количество бумажных квадратов, стороны которых имеют целочисленные длины. Дети помещают на плоскость эти квадраты (возможно, не все) так, что нижний левый угол каждого квадрата находится на биссектрисе координатного угла, идущей из третьей четверти в первую, и стороны квадратов параллельны осям координат. При этом положение каждого квадрата заранее определено.
Входной файл содержит сведения о размерах квадратов и их возможных положениях на плоскости. Для каждого квадрата указана целочисленная абсцисса положения его нижнего левого угла и длина стороны. Если при размещении на плоскости один квадрат накрывает другой, то дети должны оставить только один из них. Если стороны квадратов касаются, то можно оставить на плоскости оба квадрата. Определите максимальное количество квадратов, которое могут разместить на плоскости дети, и какова при этом максимально возможная величина модуля разности абсцисс положений левых нижних
углов двух квадратов, наиболее удалённых от начала координат.
Входные данные.
В первой строке входного файла находится натуральное число N (N ≤ 1000) — количество квадратов. Следующие N строк содержат пары чисел, обозначающих абсциссу положения левого нижнего угла квадрата на плоскости и длину его стороны. Каждое из чисел целое, не превосходящее 10000. Запишите в ответе два числа: максимальное количество квадратов и максимальную величину модуля разности абсцисс положений левых нижних углов двух квадратов, наиболее удалённых от начала координат.
Типовой пример организации данных во входном файле
5
-20 120
90 20
147 43
150 30
120 20
При таких исходных данных можно поместить на плоскость максимум три квадрата, например, квадраты, описанные в файле под номерами 2, 3 и 5. Максимальная величина модуля разности абсцисс положений левых нижних углов двух квадратов, наиболее удалённых от начала координат, составит 30, если на плоскость помещены квадраты 2, 4 и 5.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.
В ответ запишите два искомых числа через пробел
Дети играют в следующую игру. На бесконечном разлинованном на клетки листе введена декартова система координат, при этом клетки таковы, что их вершины находятся во всех точках плоскости, для которых обе координаты целочисленные. Есть некоторое количество бумажных прямоугольников, стороны которых имеют целочисленные длины. Дети помещают на плоскость эти прямоугольники (возможно, не все) так, что нижний левый угол каждого прямоугольника находится на биссектрисе координатного угла, идущей из третьей четверти в первую, и стороны прямоугольников параллельны осям координат. При этом положение каждого прямоугольника заранее определено.
Входной файл содержит сведения о размерах прямоугольников и их возможных положениях на плоскости. Для каждого прямоугольника указана целочисленная
абсцисса положения его нижнего левого угла, длина горизонтальной стороны, длина вертикальной стороны. Если при размещении на плоскости один прямоугольник накрывает другой, то дети должны оставить только один из них. Если стороны прямоугольников касаются, то можно оставить на плоскости оба прямоугольника.
Определите максимальное количество прямоугольников, которое могут разместить на плоскости дети, и какова при этом максимально возможная величина модуля разности абсцисс положений левых нижних углов двух прямоугольников, наиболее удалённых от начала координат.
Входные данные.
В первой строке входного файла находится натуральное число N (N ≤ 1000) - количество прямоугольников. Следующие N строк содержат тройки чисел; обозначающих абсциссу положения левого нижнего угла прямоугольника на плоскости, длину его горизонтальной стороны, длину его вертикальной стороны. Каждое из чисел целое, не превосходящее 10000. Запишите в ответе два числа: максимальное количество прямоугольников и максимальную величину модуля разности абсцисс положений левых нижних углов двух прямоугольников, наиболее удалённых от начала координат.
Типовой пример организации данных во входном файле
5
-20 120 140
90 200 20
147 43 44
150 30 50
120 60 20
При таких исходных данных можно поместить на плоскость максимум три прямоугольника, например, прямоугольники, описанные в файле под номерами 2, 3 и 5. Максимальная величина модуля разности абсцисс положений левых нижних углов двух прямоугольников, наиболее удалённых от начала координат, составит 30, если на плоскость помещены прямоугольники 2, 4 и 5.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.
В ответ запишите два искомых числа через пробел
В тематическом парке для строительства арт-объектов используются однородные прямые круговые цилиндры с одинаковыми высотами; таких цилиндров заготовлено N штук. Руководством парка рабочим поставлена задача создать максимальной высоты пирамиду из поставленных друг на друга цилиндров, такую, чтобы каждый следующий цилиндр имел радиус основания не менее чем на 7 единиц меньше, чем предыдущий, чтобы у посетителей парка была возможность на образовавшиеся уступы помещать различные мелкие предметы. Определите количество цилиндров, которое нужно использовать для создания такой пирамиды, и максимально возможный радиус основания цилиндра, который будет находиться на вершине такой пирамиды.
Входные данные.
В первой строке входного файла находится число N - количество цилиндров (натуральное число, не превышающее 10 000). В следующих N строках находятся значения длин радиусов имеющихся цилиндров (все числа натуральные, не превышающие 10 000), каждое — в отдельной строке.
Запишите в ответе два целых числа: сначала количество цилиндров, которое необходимо использовать для строительства пирамиды максимальной высоты, затем максимально возможную длину радиуса цилиндра, который можно поместить на вершину такой пирамиды.
Типовой пример организации данных во входном файле
5
53
50
42
50
40
Пример входного файла приведён для пяти цилиндров и случая, когда минимальная допустимая разница между длинами радиусов двух последовательно идущих в пирамиде цилиндров составляет 3 единицы.
При таких исходных данных условию задачи удовлетворяют цилиндры с длинами радиусов оснований 40, 50 и 53 или 42, 50 и 53 соответственно, т. е. количество цилиндров равно 3, а радиус верхнего цилиндра составляет 42.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.
В ответ запишите два искомых числа через пробел
На прямолинейном участке пути для обеспечения связи необходимо разместить радиопередатчики. Установка каждого такого передатчика возможна на любом из N объектов, включённых в перечень разрешённых. Известно расстояние от нулевой отметки на этом участке до каждого объекта из данного перечня, кроме того по техническим нормативам для работы без помех два соседних передатчика должны находиться на расстоянии не менее 6 единиц друг от друга. На данном участке пути необходимо разместить максимальное количество передатчиков, не нарушая технические нормативы. Определите количество передатчиков при таком размещении и максимально возможное расстояние от нулевой отметки до ближайшего к ней передатчика.
Входные данные.
В первой строке входного файла находится число N (натуральное число, не превышающее 10 000) - количество объектов, на которых можно устанавливать передатчики. В следующих N строках находятся значения расстояний от нулевой отметки до каждого из этих объектов (все числа натуральные, не превышающие 10 000), каждое - в отдельной строке.
Запишите в ответе два целых числа: сначала максимальное количество передатчиков, которое можно разметить на данном участке пути, не нарушая технические нормативы, затем максимально возможное расстояние от нулевой отметки до ближайшего к ней передатчика при таком размещении.
Типовой пример организации данных во входном файле
5
63
60
52
60
50
Пример входного файла приведён для пяти объектов установки и случая, когда минимальное допустимое расстояние между двумя соседними передатчиками составляет 3 единицы.
При таких исходных данных условию задачи удовлетворяют объекты, расположенные на расстоянии 50, 60 и 63 или 52, 60 и 63 соответственно от нулевой отметки, т.е. количество передатчиков равно 3, а расстояние от нулевой отметки до ближайшего к ней передатчика составляет 52.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.
В ответ запишите два искомых числа через пробел
В магазине для упаковки подарков есть N кубических коробок и М декоративных замочков к ним (М < N). Самой интересной считается упаковка подарка по принципу матрёшки - подарок упаковывается в одну из коробок, та в свою очередь в другую коробку и т. д., при этом к каждой коробке подбирается подходящий замочек. Одну коробку можно поместить в другую, если длина её стороны хотя бы на 6 единиц меньше длины стороны другой коробки. Замочек подходит к коробке, если маркировка замочка совпадает с длиной стороны коробки. Определите наибольшее количество коробок, которое можно использовать для упаковки одного подарка, и максимально возможную длину стороны самой маленькой коробки, где будет находиться подарок. Размер подарка позволяет поместить его в самую маленькую коробку.
Входные данные.
В первой строке входного файла находятся число N - количество коробок в магазине (натуральное число, не превышающее 10 000) и через пробел число М - количество декоративных замочков в магазине (натуральное число, не превышающее 10 000). В следующих N строках находятся значения длин сторон коробок (все числа натуральные, не превышающие 10 000) и через знак табуляции значения, указанные как маркировки на замочках (все числа натуральные, не превышающие 10 000), каждая пара таких значений — в отдельной строке; в последних N - М строках второе число, соответствующее маркировке замочка, опускается, и числа, соответствующие длинам сторон коробок, идут каждое в отдельной строке.
Запишите в ответе два целых числа: сначала наибольшее количество коробок, которое можно использовать для упаковки одного подарка, затем максимально возможную длину стороны самой маленькой коробки в таком наборе.
Типовой пример организации данных во входном файле
54
43 40
31 30
32 43
40 31
30
Пример входного файла приведён для случая пяти коробок и четырёх замочков, когда минимальная допустимая разница между длинами сторон коробок, подходящих для упаковки «матрёшкой», составляет 3 единицы.
При таких исходных данных условию задачи удовлетворяют наборы коробок с длинами сторон 30, 40 и 43 или 31, 40 и 43 или 32, 40 и 43 соответственно, т. е. количество коробок равно 3, а длина стороны самой маленькой коробки равна 31 (поскольку замочка для коробки с длиной стороны 32 в магазине нет).
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.
В ответ запишите два искомых числа через пробел
В магазине для упаковки подарков есть N кубических коробок красного цвета и М кубических коробок синего цвета (N > М). Самой интересной считается упаковка подарка по принципу матрёшки - подарок упаковывается в одну из коробок, та в свою очередь в другую коробку и т. д., при этом цвет коробок чередуется. Одну коробку можно поместить в другую, если длина её стороны хотя бы на 5 единиц меньше длины стороны другой коробки. Определите наибольшее количество коробок, которое можно использовать для упаковки одного подарка, и максимально возможную длину стороны самой маленькой коробки, где будет находиться подарок. Размер подарка позволяет поместить его в самую маленькую коробку.
Входные данные.
В первой строке входного файла находятся число N - количество коробок красного цвета в магазине (натуральное число, не превышающее 10 000) и через пробел число М - количество коробок синего цвета в магазине (натуральное число, не превышающее 10 000). В следующих N строках находятся значения длин сторон коробок красного цвета (все числа натуральные, не превышающие 10 000) и через знак табуляции значения длин сторон коробок синего цвета (все числа натуральные, не превышающие 10 000), каждая пара таких значений - в отдельной строке; в последних N - М строках второе число опускается, и числа, соответствующие длинам сторон коробок красного цвета, идут каждое в отдельной строке.
Запишите в ответе два целых числа: сначала наибольшее количество коробок, которое можно использовать для упаковки одного подарка, затем максимально возможную длину стороны самой маленькой коробки в таком наборе.
Типовой пример организации данных во входном файле
5
39 55
40 42
44 44
40 55
50
Пример входного файла приведён для случая пяти коробок красного цвета и четырёх коробок синего цвета, когда минимальная допустимая разница между длинами сторон коробок, подходящих для упаковки «матрёшкой», составляет 3 единицы. При таких исходных данных условию задачи удовлетворяют наборы коробок с длинами сторон 39, 42, 50 и 55 или 40, 44, 50 и 55 соответственно, т. е. количество коробок равно 4, а длина стороны самой маленькой коробки равна 40.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.
В ответ запишите два искомых числа через пробел
Для хранения двумерного цифрового растрового чёрно-белого изображения Петя сохранил в текстовом файле информацию о позициях всех пикселей чёрного цвета на изображении (номера рядов пикселей и номера чёрных пикселей в ряду). Для редактирования изображения Пете нужно изменить цвет с белого на чёрный всем имеющимся двум соседним белым пикселям, таким что слева и справа от них в том же ряду пиксели чёрные.
Найдите ряд с наибольшим номером, в котором есть два соседних пикселя, удовлетворяющих требованию Пети. Гарантируется, что есть хотя бы один ряд, удовлетворяющий этому условию. В ответе запишите два целых числа: номер ряда и наименьший номер пикселя в ряду из найденных в этом ряду подходящих пар белых пикселей.
Входные данные.
В первой строке входного файла находится число N - количество рядов пикселей (натуральное число, не превышающее 10000). Каждая из следующих N строк содержит два натуральных числа, не превышающих 100 000: номер ряда и номер чёрного пикселя в ряду.
Выходные данные
Два целых неотрицательных числа: номер ряда и наименьший номер пикселя в выбранной паре.
Пример входного файла:
7
20 10
20 13
30 45
10 17
10 20
10 30
10 33
Условию задачи удовлетворяют три пары чисел: 20 и 11, 40 и 18, 40 и 31. Ответ для приведённого примера:
40 18
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.
В ответ запишите два искомых числа через пробел
