Информатика ЕГЭ - банк заданий - страница 267

На кондитерской фабрике имеется N коржей для приготовления тортов, которые накладываются в виде пирамиды. Клиент попросил приготовить на заказ торт-пирамиду максимальной высоты из поставленных друг на друга коржей, такую, чтобы каждый следующий корж имел диаметр не менее чем на 8 единиц меньше, чем предыдущий. 
Определите количество коржей, которое необходимо использовать для создания такого торта, и максимально возможный диаметр коржа, который будет находиться на вершине такого торта-пирамиды.
Входные данные
В первой строке входного файла находится число N - количество коржей для приготовления торта (натуральное число, не превышающее 10 000). В следующих N строках находятся значения диаметров коржей (все числа натуральные, не превышающие 10 000), каждое - в отдельной строке.
Запишите в ответе два целых числа через пробел: сначала наибольшее количество коржей, которое можно использовать для сборки необходимого торта, затем максимально возможный диаметр самого маленького коржа в таком торте.
Типовой пример организации данных во входном файле
5
43
40
32
40
30
Пример входного файла приведён для набора из пяти коржей и случая, когда минимальная допустимая разница между диаметрами коржей, подходящими для сборки торта-пирамиды, составляет 3 единицы.
При таких исходных данных условию задачи удовлетворяют наборы коржей с диаметрами 30, 40 и 43 или 32, 40 и 43 соответственно, т.е. количество коржей равно 3, а диаметр самого маленького коржа равен 32.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.

В магазине для упаковки подарков есть N кубических коробок. Самой интересной считается упаковка подарка по принципу матрёшки –
подарок упаковывается в одну из коробок, та в свою очередь в другую коробку и т.д. Одну коробку можно поместить в другую, если длина её стороны меньше длины стороны другой коробки не менее чем на 9 единиц. Определите наибольшее количество коробок, которое можно использовать для упаковки одного подарка, и максимально возможную длину стороны самой маленькой коробки, где будет находиться подарок. Размер подарка позволяет поместить его в самую маленькую коробку.
Входные данные
В первой строке входного файла находится число N – количество коробок в магазине (натуральное число, не превышающее 10 000).
В следующих N строках находятся значения длин сторон коробок (все числа натуральные, не превышающие 10 000), каждое – в отдельной строке.
Запишите в ответе два целых числа через пробел: сначала наибольшее количество коробок, которое можно использовать для упаковки одного подарка, затем максимально возможную длину стороны самой маленькой коробки в таком наборе.
Типовой пример организации данных во входном файле
5
43
40
32
40
30
Пример входного файла приведён для пяти коробок и случая, когда минимальная допустимая разница между длинами сторон коробок,
подходящих для упаковки «матрёшкой», не менее 3 единиц. При таких исходных данных условию задачи удовлетворяют наборы
коробок с длинами сторон 30, 40 и 43 или 32, 40 и 43 соответственно, т.е. количество коробок равно 3, а длина стороны самой маленькой коробки равна 32.

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

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

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

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

Цены товаров указаны в произвольном порядке.

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

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

4

80

30

50

40

При таких исходных данных, если «каждый второй товар в чеке за полцены», сумма в нескольких чеках и в одном будут:

160 и 165.

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

На соревнованиях по спортивнориентированию каждый участник должен пройти маршрут, посещая контрольные точки. Все контрольные точки пронумерованы натуральными числами начиная с 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.

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

В супермаркете проводится акция «каждый девятый товар бесплатно». Покупатель, чтобы максимально использовать условие акции, разделил все товары на ленте на группы, по девять товаров в каждой. За каждую группу он собирался заплатить отдельным чеком. В каждой группе из девяти товаров самый дорогой он поместил на девятое место. Однако выяснилось, что программа для кассового аппарата не учитывает расположения товаров на ленте и сортирует цены товаров в чеке таким образом, чтобы стоимость покупки была максимально возможной.

Тогда покупатель разместил товары по-другому.

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

Цены товаров указаны в произвольном порядке.

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

Типовой пример организации данных во входном файле
4
80
50
30
40

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

Для дачных участков СНТ необходимо закупить снегоуборщики. Для каждого из N участков будет куплен свой снегоуборщик. Известны минимальные требования к мощности этой техники для каждого из участков.
Для закупки доступно К моделей снегоуборщиков определённой мощности и стоимости. Количество экземпляров каждой модели не ограничено. Для каждого участка выбирается снегоуборщик минимальной стоимости, мощность которого не меньше требуемой; при одной и той же стоимости выбирается модель максимальной мощности.
Требуется определить общую стоимость закупки и максимальную мощность снегоуборщика, входящего в число купленных. В ответе запишите два числа: сначала суммарную стоимость всех купленных снегоуборщиков, затем максимальную мощность среди них.

Входные данные
Первая строка входного файла содержит два натуральных числа: N (1 < N < 1 000 000) - количество  участков CHT и К (1 < K < 100 000) - количество моделей снегоуборщиков соответственно.
Следующие N строк содержат по одному натуральному числу, не превышающему 1000, минимальные мощности снегоуборщиков, которые можно закупить для каждого из N участков. Далее в каждой из К строк содержится пара натуральных чисел -  мощность очередной модели снегоуборщика и её стоимость соответственно. Мощность снегоуборщиков не превосходит 1000, стоимость - 100 000. Гарантируется, что любые две модели снегоуборщиков различаются по мощности или по стоимости. Закупить подходящий набор снегоуборщиков всегда можно.
Выходные данные
В ответе укажите два искомых числа через пробел: суммарную стоимость всех купленных снегоуборщиков и максимальную мощность среди них.

Типовой пример организации данных во входном файле
3 4
1
2
3
10 7
1 5
3 7
2 3
При таких исходных данных для первого и второго участков оптимально закупить одинаковые снегоуборщики мощностью 2 и стоимостью 3, для третьего участка будет закуплен снегоуборщик мощностью 10. Стоимость закупки составит 3 + 3 + 7 = 13. Ответ: 13; 10.

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

Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на N непересекающихся непустых подмножеств (кластеров), таких что точки каждого подмножества лежат внутри прямоугольника со сторонами длиной H и W, причём эти прямоугольники между собой не пересекаются. Стороны прямоугольников не обязательно параллельны координатным осям.
Гарантируется, что такое разбиение существует и единственно для заданных размеров прямоугольников.
Будем называть центром кластера точку этого кластера, сумма расстояний от которой до всех остальных точек кластера минимальна. Для каждого кластера гарантируется единственность его центра. Расстояние между двумя точками на плоскости A(x1,y1) и B(x2,y2) вычисляется по формуле:

В файле A хранятся данные о звёздах двух кластеров, где H=11, W=11 для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата x, затем координата y. Значения даны в условных единицах. Известно, что количество звёзд не превышает 1000.
В файле B хранятся данные о звёздах трёх кластеров, где H=13, W=13 для каждого кластера. Известно, что количество звёзд не превышает 10 000. Структура хранения информации о звездах в файле B аналогична файлу А. 
Для каждого файла определите координаты центра каждого кластера, затем вычислите два числа:  Px – среднее арифметическое абсцисс центров кластеров, и  Py – среднее арифметическое ординат центров кластеров.
В ответе запишите четыре числа: в первой строке сначала целую часть произведения  Px×10000, затем целую часть произведения  Py×10000 для файла А, во второй строке – аналогичные данные для файла B.
Возможные данные одного из файлов иллюстрированы графиком. 
Внимание! График приведён в иллюстративных целях для произвольных значений, не имеющих отношения к заданию.
Для выполнения задания используйте данные из прилагаемого файла. 

Ответ записывайте сплошной строкой с пробелами.
Например, если вывод программы:
40644752241 5085557
4475147361 5375177
То ответ будет такой: 40644752241 5085557 4475147361 5375177

Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на N непересекающихся непустых подмножеств (кластеров), таких что точки каждого подмножества лежат внутри прямоугольника со сторонами длиной H и W, причём эти прямоугольники между собой не пересекаются. Стороны прямоугольников не обязательно параллельны координатным осям.
Гарантируется, что такое разбиение существует и единственно для заданных размеров прямоугольников.
Будем называть центром кластера точку этого кластера, сумма расстояний от которой до всех остальных точек кластера минимальна. Для каждого кластера гарантируется единственность его центра. Расстояние между двумя точками на плоскости A(x1,y1) и B(x2,y2) вычисляется по формуле:

В файле A хранятся данные о звёздах двух кластеров, где H=6, W=4,5 для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата x, затем координата y. Значения даны в условных единицах. Известно, что количество звёзд не превышает 1000.

В файле B хранятся данные о звёздах трёх кластеров, где H=6, W=5 для каждого кластера. Известно, что количество звёзд не превышает 1000. Структура хранения информации о звездах в файле B аналогична файлу А. 

Известно, что в файле Б имеются координаты ровно трёх «лишних» точек, являющихся аномалиями, возникшими в результате помех при передаче данных. Эти три точки не относятся ни к одному из кластеров, их учитывать не нужно.

Для файла А определите координаты центра каждого кластера, затем найдите два числа: Px - сумму абсцисс центров кластеров, и Py - сумму ординат центров кластеров. Для файла Б определите координаты центра каждого кластера, затем найдите два числа: Q1 - минимальное расстояние от центра кластера до начала координат, и Q2​ - максимальное расстояние от центра кластера до начала координат.

В ответе запишите четыре числа: в первой строке - сначала абсолютную величину целой части произведения Px × 10000, затем абсолютную величину целой части произведения Py × 10 000; во второй строке - сначала целую часть произведения Q1 × 10 000, затем целую часть произведения Q2 × 10 000.

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

Ответ записывайте сплошной строкой с пробелами.
Например, если вывод программы:
40644752241 5085557
4475147361 5375177
То ответ будет такой: 40644752241 5085557 4475147361 5375177

Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на N непересекающихся непустых подмножеств (кластеров), таких что точки каждого подмножества лежат внутри прямоугольника со сторонами длиной H и W, причём эти прямоугольники между собой не пересекаются. Стороны прямоугольников не обязательно параллельны координатным осям.
Гарантируется, что такое разбиение существует и единственно для заданных размеров прямоугольников.
Будем называть центром кластера точку этого кластера, сумма расстояний от которой до всех остальных точек кластера минимальна. Для каждого кластера гарантируется единственность его центра. Расстояние между двумя точками на плоскости A(x1,y1) и B(x2,y2) вычисляется по формуле:

В файле A хранятся данные о звёздах двух кластеров, где H=6, W=4,5 для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата x, затем координата y. Значения даны в условных единицах. Известно, что количество звёзд не превышает 1000.

В файле B хранятся данные о звёздах трёх кластеров, где H=6, W=5 для каждого кластера. Известно, что количество звёзд не превышает 1000. Структура хранения информации о звездах в файле B аналогична файлу А. 

Известно, что в файле Б имеются координаты ровно трёх «лишних» точек, являющихся аномалиями, возникшими в результате помех при передаче данных. Эти три точки не относятся ни к одному из кластеров, их учитывать не нужно.

Для файла А определите координаты центра каждого кластера, затем найдите два числа: Px - сумму абсцисс центров кластеров, и Py​ - сумму ординат центров кластеров. Для файла Б найдите два числа: Q1 - минимальное расстояние между точками, принадлежащими двум различным кластерам, и Q2 - максимальное расстояние между точками, принадлежащими двум различным кластерам.

В ответе запишите четыре числа: в первой строке - сначала абсолютную величину целой части произведения Px × 10000, затем абсолютную величину целой части произведения Py​ × 10 000; во второй строке - сначала целую часть произведения Q1​ × 10 000, затем целую часть произведения Q2​ × 10 000.

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

Ответ записывайте сплошной строкой с пробелами.
Например, если вывод программы:
40644752241 5085557
4475147361 5375177
То ответ будет такой: 40644752241 5085557 4475147361 5375177

В терминологии сетей TCP/IP маской сети называют двоичное число, которое показывает, какая часть IP-адреса узла сети относится к адресу сети, а какая – к адресу узла в этой сети. Адрес сети получается в результате применения поразрядной конъюнкции к заданному адресу узла и его маске.

Широковещательным адресом называется специализированный адрес, в котором на месте нулей в маске стоят единицы. Адрес сети и широковещательный адрес не могут быть использованы для адресации сетевых устройств.

Сеть задана IP-адресом одного из входящих в неё узлов 98.81.154.195 и сетевой маской 255.252.0.0.

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

Например, если бы найденный адрес был равен 111.22.3.44, то в ответе следовало бы записать 11122344.