Сборник заданий ЕГЭ по информатике

Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на 𝑁 непересекающихся непустых подмножеств (кластеров), таких что точки каждого подмножества лежат внутри прямоугольника со сторонами длиной 𝐻 и 𝑊, причём эти прямоугольники между собой не пересекаются. Стороны прямоугольников не обязательно параллельны координатным осям.

Гарантируется, что такое разбиение существует и единственно для заданных размеров прямоугольников.

Будем называть центром кластера точку этого кластера, сумма расстояний от которой до всех остальных точек кластера минимальна. Для каждого кластера гарантируется единственность его центра. Расстояние между двумя точками на плоскости 𝐴⁡(𝑥1, 𝑦1) и 𝐵⁡(𝑥2, 𝑦2) вычисляется по формуле:

В файле А 27_A.txt хранятся данные о звёздах двух кластеров, где 𝐻 = 6,5, 𝑊 = 4,5 для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата 𝑥, затем координата 𝑦. Значения даны в условных единицах. Известно, что количество звёзд не превышает 1000.

В файле В 27_B.txt хранятся данные о звёздах трёх кластеров, где 𝐻 = 6,5, 𝑊 = 4,5 для каждого кластера. Известно, что количество звёзд не превышает 10 000. Структура хранения информации о звездах в файле В аналогична файлу А.

Для файла А определите координаты центра каждого кластера, затем найдите два числа: 𝐴1 — в кластере с наименьшим количеством точек число точек, абсцисса которых не больше абсциссы центра этого кластера, и 𝐴2 — расстояние между центрами кластеров.

Для файла B определите координаты центра каждого кластера, затем найдите два числа: 𝐵1 — в среднем по количеству точек кластере число точек, находящихся внутри квадрата с центром в центре этого же кластера, сторонами, параллельными координатным осям и длиной 2,0, и 𝐵2 — расстояние по оси ординат между центрами кластеров с наименьшим и наибольшим количеством точек.

Гарантируется, что во всех кластерах количество точек различно.

В ответе запишите четыре числа: в первой строке — сначала 𝐴1, затем целую часть произведения 𝐴2 ×10 000; во второй строке — сначала 𝐵1, затем целую часть произведения 𝐵2 ×10 000.

Менеджеры интернет-магазина составляют рейтинговый список новых моделей смартфонов по данным о продолжительности автономной работы устройства в режиме ожидания и в активном режиме использования. У каждой модели известны оба показателя. Для объективности бренды и марки устройств скрыты, в списке все смартфоны пронумерованы начиная с единицы.

Алгоритм формирования рейтинга выглядит следующим образом:

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

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

26.txt

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

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

На грузовом космическом корабле необходимо перевезти на МКС контейнеры, имеющие одинаковые габариты и разные массы. Общая масса всех этих контейнеров превышает грузоподъёмность космического корабля. Количество грузовых мест на космическом корабле не меньше числа контейнеров, назначенных к перевозке.

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

26.txt

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

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

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

Два целых неотрицательных числа: минимальное количество контейнеров, которые нельзя перевезти на МКС за один рейс, и максимальная суммарная масса оставшихся на космодроме грузов.

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

100  4
80
30
50
40

При таких исходных данных можно транспортировать за один раз максимум два контейнера. Возможные массы этих двух контейнеров — 30 и 40, 30 и 50 или 40 и 50. Контейнеры с массами 50 и 80 могут быть не перевезены. Ответом для приведённого примера является пара чисел 2 и 130.

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

В магазине продаётся 𝑁 товаров нескольких артикулов. Товары одного артикула имеют одинаковую цену. Учёт товаров ведётся поштучно, для каждой единицы товара известен её текущий статус (продана или нет). Товары разделены на две категории: дорогие и дешёвые. Дорогими считаются товары, цена на которые превышает среднюю цену (среднее арифметическое) всех товаров в базе данных магазина без учёта их текущего статуса, остальные товары считаются дешёвыми.

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

Найдите суммарную выручку магазина от реализации товара — лидера продаж, а также оставшееся количество товара этого артикула.

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

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

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

Два числа: сумма выручки от реализации товара — лидера продаж, а также количество товара этого артикула, оставшееся в наличии.

26.txt

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

8
10  100  1
3  10  0
10  100  0
2  10  1
10  100  0
3  10  1
11  100  0
1  200  0

При таких исходных данных дорогими являются товары стоимостью 100 и 200 рублей. Больше всего было продано товара вида 10. В продаже остался один такой товар. Условию задачи удовлетворяет ответ 200;  1.

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

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

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

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

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

Первая строка входного файла содержит целое число 𝑁 (𝑁 ⩽2000) — количество заявок на уборку снега. Следующие 𝑁 строк содержат пары чисел, обозначающих начало участка (в метрах от начала дороги) и его протяжённость. Каждое из чисел натуральное, не превосходящее 10 000. Гарантируется, что конец участка не выходит за пределы дороги.

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

26.txt

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

5
1  1000
1001  1000
2001  2500
4501  500
4501  1500

При таких исходных данных будет выполнено не более 4 заявок. Могут быть выполнены заявки с номерами 1, 2, 3 и 4 или заявки с номерами 1, 2, 3 и 5. Ответ: 4  3999.

Напишите программу, которая перебирает целые числа, бо́льшие 700 000, в порядке возрастания и ищет среди них такие, у которых есть натуральный делитель, оканчивающийся на цифру 7 и не равный ни самому числу, ни числу 7.

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

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

символ «?» означает ровно одну произвольную цифру;
символ «∗» означает любую последовательность цифр произвольной длины; в том числе «∗» может задавать и пустую последовательность.
Например, маске 123 ∗4?5 соответствуют числа 123405 и 12300405.

Среди натуральных чисел, не превышающих 108, найдите все числа, соответствующие маске 1 ∗23??56, делящиеся на 171 без остатка.

В ответе запишите все найденные числа в порядке возрастания

На ленте в соседних ячейках записано двоичное представление числа 2047 без ведущих нулей. Ячейки справа и слева от последовательности заполнены пустыми символами «𝜆». В начальный момент времени головка расположена в ближайшей ячейке справа от последовательности.

Программа работы исполнителя:

 
Определите результат выполнения программы. В ответе запишите получившееся число в десятичной системе счисления.

На ленте в соседних ячейках записано двоичное представление числа 2027 без ведущих нулей. Ячейки справа и слева от последовательности заполнены пустыми символами «𝜆». В начальный момент времени головка расположена в ближайшей ячейке слева от последовательности.

Программа работы исполнителя:

Определите результат выполнения программы. В ответе запишите получившееся число в десятичной системе счисления.

На ленте в соседних ячейках записано двоичное представление числа 800 без ведущих нулей. Ячейки справа и слева от последовательности заполнены пустыми символами «𝜆». В начальный момент времени головка расположена в ближайшей ячейке справа от последовательности.

Программа работы исполнителя:

Определите результат выполнения программы. В ответе запишите получившееся число в десятичной системе счисления.