Портал обучения информатике. Подготовка к ЕГЭ, ОГЭ, олимпиадам

Красота фейерверка#33127

В лаборатории теоретической пиротехники изучают новые технологии организации

фейерверков. Фейерверк представляется как корневое дерево, а поскольку в мощном

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

операцию возведения корневого дерева в степень.

Корневое дерево содержит одну или несколько вершин. Одна из вершин выделена и

называется корнем дерева, для каждой из остальных вершин ровно одна другая вершина

является родителем. При этом от любой вершины можно добраться до корня,

последовательно переходя от вершины к ее родителю. Вершина, которая не является

родителем никакой другой вершины, называется листом. Если вершина x является

родителем вершины y, то вершина y является ребенком вершины x. Будем говорить, что

вершина и ее родитель соединены ребром.

На рис. 1 показан пример корневого дерева с корнем в вершине 1. Родителем вершин

2 и 3 является вершина 1, родителем вершины 4 является вершина 2. Вершины 2 и 3 — дети

вершины 1, а вершина 4 — ребенок вершины 2. Листьями являются вершины 3 и 4.

Рис. 1. Пример корневого дерева с корнем в вершине 1, листьями 3 и 4.

Фейерверк задается своим базовым деревом T и мощностью m. Фейерверк представляется деревом, которое получается в результате возведения дерева T в степень m. Операция возведения дерева в степень устроена следующим образом. Если m = 1, то результат T¹ — само дерево T. Для m > 1 рассмотрим дерево T^{m – 1} . Выполним следующую операцию: для каждого листа x дерева T^{m – 1} создадим копию дерева T и назначим лист x родителем корня соответствующей копии. Получившееся дерево будет деревом T^m .

На рис. 2 показано дерево, представленное на рис. 1, в степенях 1, 2 и 3.

Рис. 2. Пример возведения дерева в степени 1, 2 и 3

Путем в дереве называется последовательность вершин, в которой две соседние

вершины соединены ребром. Все вершины в пути должны быть различны.

Для того, чтобы оценить красоту фейерверка, необходимо определить, какое

максимальное количество вершин может содержать путь в дереве, которым представляется

фейерверк. На рис. 3 приведен путь в дереве T², содержащий максимальное количество

вершин. Таким образом, красота фейерверка с базовым деревом T и мощностью 2 равна 10.

Рис. 3. Путь в дереве T² , содержащий максимальное количество вершин.
Требуется написать программу, которая по описанию дерева T и натуральному числу m определяет красоту фейерверка с базовым деревом T и мощностью m.

Формат входных данных

Первая строка входных данных содержит два натуральных числа n и m — количество

вершин в базовом дереве фейерверка T и его мощность (3 ≤ n ≤ 200 000, 1 ≤ m ≤ 200 000).

Вторая строка описывает дерево T и содержит (n – 1) целых чисел: p2, p3, …, pn —

номера родителей вершин 2, 3, …, n, соответственно (1 ≤ pi ≤ i – 1).

Формат выходных данных

Требуется вывести одно целое число — красоту фейерверка, представляемого

деревом T^m.

Ввод	Вывод
4 2 1 1 2	10

✓ 3✗ 211 100средняяВойти и решать

Лифт#33123

В современном многоэтажном офисе крупной компании установлен новый лифт. В

компании работает n сотрудников. Для проверки эффективности системы управления

лифтом требуется провести моделирование его работы в конце рабочего дня, когда все

сотрудники должны покинуть здание и спуститься на первый этаж.

В здании m этажей, пронумерованных от 1 до m снизу-вверх. Известно, что i-й

сотрудник подходит к лифту в секунду ti на этаже ai, чтобы спуститься на первый этаж.

На каждом этаже могут находиться люди, ожидающие лифт. Когда очередной

сотрудник подходит к лифту, он вызывает лифт, если на этом этаже лифт еще не вызван,

либо присоединяется к ожидающим лифт. Таким образом, помимо вызвавшего лифт, вместе

с ним лифт могут ожидать и другие сотрудники.

В каждый момент времени не более одного вызова является активным.

Изначально лифт свободен и находится на первом этаже. Когда поступает первый

вызов, этот вызов становится активным и лифт отправляется на соответствующий этаж. Если

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

меньшим номером.

Лифт перемещается между этажами со скоростью один этаж в секунду. Когда лифт

оказывается на этаже, откуда был сделан активный вызов, в него заходят все, кто уже

ожидает лифт на этом этаже, и лифт отправляется вниз на первый этаж, со скоростью один

этаж в секунду.

При движении вниз лифт останавливается на тех этажах, в которых был сделан вызов

на момент проезда лифта мимо этого этажа. Все ожидающие лифт сотрудники заходят в него

и вызов на этом этаже сбрасывается. Когда лифт завершает движение на первом этаже, все

люди выходят из лифта, а лифт ожидает следующего вызова.

Если в момент, когда лифт освободился, есть хотя бы один необслуженный вызов,

активируется вызов, который поступил раньше других. Если несколько вызовов поступило

одновременно, активируется вызов от сотрудника с меньшим номером. Лифт продолжает

обслуживание описанным образом, пока все n сотрудников не окажутся на первом этаже.

Будем считать, что люди входят и выходят из лифта мгновенно. Каждую секунду

сначала люди подходят и вызывают лифт, а затем выполняются соответствующие действия

(лифт перемещается на соседний этаж, в него входят или из него выходят люди, принимается

решение, на какой вызов лифт должен отреагировать).

Требуется написать программу, которая по описанию вызовов лифта для каждого

сотрудника определяет, в какой момент этот сотрудник окажется на первом этаже.

Формат входных данных

Первая строка входных данных содержит целые числа n и m — количество людей,

вызывающих лифт, и количество этажей в здании (1 ≤ n ≤ 10⁵, 2 ≤ m ≤ 10⁹).

Следующие n строк описывают сотрудников, i-я из этих строк содержит два целых

числа ti и ai — секунду, в которую i-й сотрудник подходит к лифту, и номер этажа, на

котором это происходит (1 ≤ t1 ≤ t2 ≤ … ≤ tn ≤ 10⁹, 2 ≤ ai ≤ m)

Формат выходных данных

Выходные данные должны содержать n целых чисел, для каждого сотрудника

требуется вывести секунду, в которую он выйдет из лифта на первом этаже.

Ввод	Вывод
5 4 2 3 2 4 5 2 5 3 9 3	6 12 6 12 12

Пояснение к примеру

Пример работы лифта по шагам показан в следующей таблице.

Использованные в пояснении к примеру обозначения

Использование сортировки Множества Сортировка событий Структуры данных

✓ 0✗ 91 300средняяВойти и решать

Банды Фомина №2#30699

Банда Фомина состоит из n групп, в каждой из которых a_i человек. Планируется провести q рейдов. В i-ом рейде будет участвовать ровно один разбойник из каждой группы, номер которой лежит в отрезке \([l_i, r_i]\).

Мелехов тоскует, поэтому для каждого рейда он решил посчитать количество возможных отрядов по модулю \(10^9 + 7\). Однако Григорий постоянно находится в раздумьях о смысле жизни и поиске правды, поэтому он не может сконцентрироваться на расчетах и просит вас помочь.

Входные данные
В первой строке дано число n (\(1 <= n <= 10^5\)) – количество групп в банде Фомина.
Во второй строке дано n натуральных чисел a_i (\(1 <= a_i <= 10^6\)) – количество человек в i-ой группе.
В третьей строке дано число q – количество рейдов.
Далее дано q строк, в каждой из которых дано два числа – l_i и r_i (\(1 <= l_i <= r_i <= n\)) – номера групп, участвующих в i-ом рейде.

Выходные данные
Выведите q чисел, каждое в отдельной строке – ответ на задачу.

Примеры

№	Входные данные	Выходные данные
1	6 1 3 7 1 4 100 3 1 3 3 4 2 6	21 7 8400

Быстрое возведение в степень Малая теорема Ферма Остатки Префиксные суммы(минимумы, ...)

✓ 11✗ 821 100средняяВойти и решать

Circular Barn#29547

У Фермера Джона круглый амбар. Амбар состоит из кольца из n комнат, пронумерованных 1…n по периметру (3≤n≤1,000). Каждая комната имеет двери в две соседние комнаты и одну дверь во внешний мир.

ФД хочет разместить ровно ri коров в комнате i (1≤r_i≤1,000,000). Он планирует открыть k внешних дверей (1≤k≤7), через которые коровы будут входить в амбар. Каждая корова затем идёт по часовой стрелке, пока не добредёт до нужной комнаты. ФД хочет открыть двери так, чтобы все коровы вместе прошли как можно меньшее расстояние. Коровы предварительно могут собраться как им выгоднее перед этими незакрытыми дверями (эти перемещения не входят в общее расстояние, учитываемое в задаче). Определите минимальное суммарное расстояние, которое придётся пройти коровам, если ФД наилучшим образом выберет какие k открыть.

ФОРМАТ ВВОДА:

Первая строка ввода содержит n и k. Последующие n строк содержат r₁…r_n.

ФОРМАТ ВВОДА:

Выведите минимальное суммарное расстояние пройденное коровами.

Ввод	Вывод
6 2 2 5 4 2 6 2	14

ФД может открыть двери 2 и 5. 11 коров войдут в двери 2 и пройдут суммарное расстояние 8 чтобы попасть в комнаты 2,3,4. 10 коров войдут в дверь 5 и пройдут общее расстояние 6, чтобы попасть в комнаты 5,6,1.

Динамическое программирование Динамическое программирование: два параметра Задача на реализацию Рекурсия

✓ 1✗ 1—Войти и решать

Load Balancing#29545

Коровы Фермера Джона стоят в различных точках (x₁,y₁)…(x_n,y_n) его поля (1≤N≤100,000, все x_i и y_i - положительные нечётные целые числа, не превышающие 1,000,000. ФД хочет разделить своё поле изгородью бесконечной длины с севера на юг, описываемой уравнением x=a (a - чётное целое, так обеспечивается, что изгородь не пройдёт через позицию ни одной коровы). Также он хочет построить изгородь бесконечной длины с востока на запад, которая описывается уравнением y=b, где b - чётное целое. Эти две изгороди пересекаются в точке (a,b), и вместе делят поле на четыре региона.

ФД хочет выбрать a и b так, чтобы получить "сбалансированное" количество коров во всех регионах, т.е. чтобы не было региона, который содержит слишком много коров. Пусть M - максимальное количество коров в этих четырёх регионах, ФД хочет, чтобы M было как можно меньше. Помогите ФД определить это минимально возможное значение для M.

ФОРМАТ ВВОДА:

Первая строка ввода содержит одно целое число, N. Каждая из следующих n строк содержит местоположение одной коровы, указанное её координатами x и y.

ФОРМАТ ВЫВОДА:

Выведите минимально возможное значение M, которое может достичь ФД оптимальным расположением изгородей.

Ввод	Вывод
7 7 3 5 5 7 13 3 1 11 7 5 3 9 1	2

Дерево отрезков, RSQ, RMQ Дерево Фенвика Структуры данных Тернарный поиск

✓ 3✗ 251 100средняяВойти и решать

Trapped in the Haybales#27295

Фермер Джон получили груз из N больших стогов сена (1≤N≤100,000), и разметил их в различных положениях вдоль дороги, ведущей к амбару. К несчастью, он полностью забыл, что корова Беси пасётся вдоль дороги и может попасть в ловушку между стогами сена.

Каждый стог j имеет размер S_j и позицию Pj определяющую его положение вдоль дороги. Беси может двигаться вдоль дороги вплоть до позиции стога, но не может пересечь эту позицию. Исключение – если она прошла в этом направлении D единиц расстояния, тогда она набрала достаточно скорости, чтобы протаранить стог любого размера строго меньше чем D. Конечно после этого она может продолжить движение и таранить другие стога.

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

ФОРМАТ ВООДА:

Первая строка ввода содержит N. Каждая из последующих N строк описывает стог, и содержит два целых числа определяющих размер и позицию в диапазоне 1…10⁹. Все позиции различны.

ФОРМАТ ВЫВОДА:

Выведите одно целое число – размер области дороги, откуда Беси не сможет выбраться.

Ввод	Вывод
5 8 1 1 4 8 8 7 15 4 20	14

Дерево отрезков, RSQ, RMQ Динамическое программирование Динамическое программирование: один параметр Структуры данных

1 200средняяВойти и решать

Palindromic Paths#27294

Ферма Джона представлена решёткой N×N полей (1≤N≤500). Каждое поле представлено символом латинского алфавита. Например:

ABCD

BXZX

CDXB

WCBA

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

Пожалуйста, помогите Беси определить количество различных маршрутов которыми она может получить палиндромы. Различные пути, которыми получаются одинаковые палиндромы учитывать множество раз. Выведите свой ответ по модулю 1,000,000,007.

ФОРМАТ ВВОДА:

Первая строка ввода содержит N, и последующие N строк содержат N строк решётки, описывающей поля. Каждая строка содержит N символов в интервале A..Z.

ФОРМАТ ВЫВОДА:

Выведите количество различных путей Беси, формирующих палиндромы по модулю 1,000,000,007.

Ввод	Вывод
4 ABCD BXZX CDXB WCBA	12

Примечание:

Беси может сделать следующие палиндромы:

1 x "ABCDCBA"

1 x "ABCWCBA"

6 x "ABXZXBA"

4 x "ABXDXBA"

Динамическое программирование Динамическое программирование: два параметра Комбинаторика Строки

✓ 0✗ 41 200средняяВойти и решать

Воздушные потоки#24765

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

Представим воздушные потоки как массив h[1..n] из n натуральных чисел — высот потоков. Для каждого 1 ≤ i ≤ n посчитаем G[i] — индекс ближайшего элемента слева, строго большего h[i]. Более формально, g[i] = max{j | j < i и h[j] > h[i]}. Если i = 1 или до h[i] нет ни одного элемента больше него, то G[i] считается равным 0.

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

Чем меньше сумма, тем расположение оптимальнее. Всё, что может сейчас сделать Колобок — это увеличить высоту одного из воздушных потоков не более чем на m. После этого действия высота потока должна остаться целым числом, но может, если необходимо, стать и нечётной.

Помогите Колобку сделать оптимальное изменение, которое позволит добиться, чтобы сумма S(h), описанная выше, после проделанного действия была минимальна.

Формат входного файла
В первой строке входного файла даны числа n, m (1 ≤ n ≤ 10⁵ , 1 ≤ m ≤ 10⁹ ) — количество воздушных потоков и максимальное значение, на которое можно увеличить высоту одного из них. Во второй строке даны высоты воздушных потоков h[i] (1 ≤ h[i] ≤ 10⁹ ). Гарантируется, что все высоты — чётные числа.

Формат выходного файла
В единственной строке выходного файла выведите одно целое число — минимальную искомую сумму.

Ввод	Вывод
3 100 4 2 6	4
3 2 4 2 6	5
3 10 2 2 2	4

Деревья Наименьший общий предок Разреженные таблицы (sparse table)Структуры данных

✓ 2✗ 151 200средняяВойти и решать

Урок физкультуры#21998

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

Всего на урок пришло N детей, изначально построившихся таким образом, что рост стоящего на позиции i равен hi (используется нумерация c 1). Можно считать, что все числа hi различны и лежат в диапазоне от 1 до N. Шеренга считается упорядоченной, если на первой позиции стоит школьник ростом один, на второй позиции стоит школьник ростом два и так далее.

Феоктист Всеволодович получает большое удовольствие от процесса упорядочивания школьни- ков, поэтому он всегда выбирает наиболее длинную последовательность обменов. С другой стороны, он не хочет чтобы ученики догадались о том, что он умышленно затягивает построение, поэтому никогда не делает заведомо бессмысленных обменов. А именно, преподаватель никогда не меняет местами школьников на позициях i и j, если hi < h_j . Очевидно, что данное ограничение делает процесс сортировки шеренги по росту конечным.

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

Формат входных данных
В первой строке ввода содержится единственное число N — количество школьников на уроке (1 <= N <= 1 000 000). Во второй строке записано N различных целых чисел h_i (1 <= h_i <= N). i-е число соответствует росту школьника стоящего на i-й позиции.

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

Ввод	Вывод
5 2 4 3 5 1	2 5
4 1 2 3 4	-1 -1
10 2 3 7 1 5 10 4 6 9 8	3 7

Дерево отрезков, RSQ, RMQ Сканирующая прямая Словари Структуры данных

✓ 1✗ 391 200средняяВойти и решать

Выборы#21952

Скоро в Соединенных Штатах Берляндии пройдут выборы президента. На эту ответственную должность претендуют два кандидата: Дядя Сэм и Дядя Фродо. Вы работаете аналитиком в пред- выборном штабе Дяди Сэма, и вам поручено помочь ему победить конкурента. Раздуть газетный скандал из одержимости оппонента бросанием колец в жерла вулканов не получилось, так что при- дётся воспользоваться математикой.

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

Как вы знаете, Соединенные Штаты Берляндии разделены на несколько административных ре- гионов первого уровня — штатов. Сначала в каждом из штатов проходят местные выборы, по итогам которых каждый штат отдаёт свой голос за одного из кандидатов. Если не менее половины штатов выбрало Дядю Сэма, то выигрывает он (в случае равенства голосов Дядя Сэм имеет преимущество как действующий президент), иначе побеждает Дядя Фродо. Все штаты, в свою очередь, состоят из административных регионов второго уровня, каждый из которых представлен выборщиком из административных регионов третьего уровня и так далее. Последний уровень состоит из отдельных жителей Берляндии. Всего в Берляндии N жителей и K уровней административных единиц. Одним из ключевых принципов этой страны является равенство, так что любой регион i-го уровня делится на одинаковое число регионов следущего уровня (в том числе содержит одинаковое число граждан).

Так получилось, что делением на регионы поручили заняться именно вам, то есть в ваших руках назначить, на сколько именно административных единиц i-го уровня делится (i−1)-ая администра- тивная единица.

Также у вас есть сильный инструмент влияния на выбор людей — нефтяные бурли. Чтобы заста- вить одного избирателя отдать свой голос за Дядю Сэма, достаточно дать ему скромный подарок в размере одного нефтяного бурля.

К несчастью, изначально все N жителей Соединённых Штатов Берляндии собираются отдать свой голос за Дядю Фродо. Требуется определить минимальное количество нефтяных бурлей, ко- торое достаточно потратить для победы на выборах.

Формат входных данных

В единственной строке ввода находятся два целых числа N и K (1 <= N <= 10¹⁵ , 1 <= K <= 10).

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

Примеры

Ввод	Вывод
9 2	4
12 3	2

Замечание
Берляндские законы не запрещают, чтобы страна состояла из одного штата, а город — одного жителя. Аналогично с остальными типами регионов.

На рисунке 1 черным цветом отмечены те регионы, в которых победил Дядя Сэм. На нижнем уровне черными изображены вершины, соответствущие подкупленным конкретным жителям.

Алгоритмы на графах Динамическое программирование Динамическое программирование: один параметр Простые числа и разложение на множители

✓ 2✗ 771 200средняяВойти и решать

Река#21888

Во Флатландии протекает богатая рыбой река Большой Флат. Много лет назад река была поделена между n рыболовными предприятиями, каждое из которых получило непрерывный отрезок реки. При этом i-е предприятие, если рассматривать их по порядку, начиная от истока, изначально получило отрезок реки длиной ai .

С тех пор с рыболовными предприятиями во Флатландии k раз происходили различные события. Каждое из событий было одного из двух типов: банкротство некоторого предприятия или разделение некоторого предприятия на два.

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

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

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

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

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

Формат входного файла
Первая строка входного файла содержит два целых числа: n и p — исходное количество предприятий (2 ≤ n ≤ 100 000) и номер подзадачи (0 ≤ p ≤ 4). Вторая строка входного файла содержит n целых чисел a1, a2, …, an — длины исходных отрезков реки. Третья строка входного файла содержит целое число k — количество событий, происходивших с предприятиями (1 ≤ k ≤ 100 000). Последующие k строк содержат описания событий, i-я строка содержит два целых числа: ei и vi — тип события и номер предприятия, с которым оно произошло. Значение ei = 1 означает, что предприятие, которое после всех предыдущих событий является vi-м по порядку, если считать с единицы от истока реки, обанкротилось, а значение ei = 2 означает, что это предприятие разделилось на два. Гарантируется, что значение vi не превышает текущее количество предприятий. Гарантируется, что если отрезок предприятия при банкротстве или разделении требуется поделить на две части, то он имеет длину большую или равную 2. Гарантируется, что если на реке осталось единственное предприятие, оно не банкротится.

Формат выходного файла
Выходной файл должен содержать (k + 1) целых чисел, по одному в строке. Первая строка должна содержать исходную сумму квадратов длин отрезков реки, а каждая из последующих k строк — сумму квадратов длин отрезков реки после очередного события.

Пример
Ввод:
4 0
3 5 5 4
5
1 1
2 1
1 3
2 2
1 3
Вывод:
75
105
73
101
83
113

Пояснение к примеру
Распределение отрезков реки между предприятиями после каждого события, описанного в примере, приведено на рисунке ниже.

Двоичное дерево поиска Декартово дерево Корневая оптимизация Структуры данных

✓ 2✗ 41 200средняяВойти и решать

ОГЭ-2027 демо. Задание 13#98390

Выберите ОДНО из предложенных ниже заданий: 13.1 или 13.2.

13.1

Используя информацию и иллюстративный материал, содержащийся в каталоге DEMO-13, создайте презентацию из трёх слайдов на тему «Леопард». В презентации должны содержаться краткие иллюстрированные сведения о внешнем виде, местах обитания, образе жизни и рационе леопардов. Все слайды должны быть выполнены в едином стиле, каждый слайд должен быть озаглавлен.

Презентацию сохраните в файле, имя которого Вам сообщат организаторы экзамена. Файл ответа необходимо сохранить в формате *.odp.

Требования к оформлению работы

1. Ровно три слайда без анимации. Параметры страницы (слайда): экран (16:9), ориентация альбомная.

2. Содержание, структура, форматирование шрифта и размещение изображений на слайдах:

• первый слайд – титульный слайд с названием презентации, в подзаголовке титульного слайда в качестве информации об авторе презентации указывается идентификационный номер участника экзамена;

• второй слайд – основная информация в соответствии с заданием, размещённая по образцу на рисунке макета слайда 2:

· заголовок слайда;
· два изображения;
· два блока текста;

• третий слайд – дополнительная информация по теме презентации, размещённая по образцу на рисунке макета слайда 3:

· заголовок слайда;
· три изображения;
· три блока текста.

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

[Изображение]

В презентации должен использоваться единый тип шрифта (рубленый, с засечками или моноширинный).

Размер шрифта для названия презентации на титульном слайде – 40 пунктов, для подзаголовка на титульном слайде и заголовков слайдов – 24 пункта, для подзаголовков на втором и третьем слайдах и для основного текста – 20 пунктов.

Текст не должен перекрывать основные изображения и сливаться с фоном.

13.2

Создайте в текстовом редакторе документ и напишите в нём следующий текст, точно воспроизведя всё оформление текста, имеющееся в образце.

Данный текст должен быть набран шрифтом размером 14 пунктов обычного начертания. Отступ первой строки абзацев основного текста – 1 см. Расстояние между строками текста не менее одинарного, но не более полуторного междустрочного интервала. Основной текст выровнен по ширине; заголовок текста, текст в ячейках первой и седьмой строк таблицы, первого столбца таблицы – по центру; в ячейках второго столбца – выравнивание по левому краю. Во всех ячейках таблицы применено вертикальное выравнивание по центру. В основном тексте и таблице есть слова, выделенные полужирным шрифтом, курсивом или подчёркиванием. Таблица выровнена на странице по центру горизонтали. Ширина таблицы меньше ширины основного текста.

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

Интервал (расстояние) между заголовком текста и текстом, между абзацами текста, между текстом и таблицей не менее 12 пунктов (4 мм), но не более 24 пунктов (8,5 мм). Для установки интервала не допускается использование «пустого абзаца».

Текст сохраните в файле, имя которого Вам сообщат организаторы. Файл ответа необходимо сохранить в формате *.odt.

МОСКОВСКО-ПЕТРОГРАДСКАЯ ЛИНИЯ

Вторая линия Петербургского метрополитена, также известная как Московско-Петроградская (официальное название до 1993 г.) или синяя линия, соединяет через центр города южные и северные районы Санкт-Петербурга – от Московского района до северной части Выборгского.

Единственная в Петербургском метрополитене линия, обе конечные станции которой – наземные крытые.

Информация о линии
Открытие первого участка	29 апреля 1961 г.
Длина, км	30,1
Количество станций	18
Время поездки, мин.	47
Среднесуточная перевозка пассажиров, тыс. человек/сутки	772,4
Подвижной состав
Максимальное число вагонов в составе поезда	6
Тип	«Юбилейный»

ОГЭ ОГЭ-13.1 Презантация ОГЭ-13.2 Текст

—Войти и решать

4.3.5 Подбор K в методе ближайших соседей (уровень 3)#96036

Файл knn.txt содержит 1500 строк: координата метка (координата — вещественная, метка: 1 или 0). Первые 1000 строк — обучающая выборка, последние 500 — тестовая.

Тестовая точка классифицируется методом K ближайших соседей: берутся \( K \) обучающих точек, ближайших к ней по расстоянию \( |x_1 - x_2| \), и метка выбирается голосованием большинства. При равенстве голосов присваивается метка 0.

Переберите нечётные значения \( K \) от 1 до 21. Для каждого вычислите точность на тестовой выборке. Найдите \( K \) с максимальной точностью (при равенстве — наименьшее).

В ответе запишите два числа через пробел: оптимальное \( K \) и достигнутую точность в процентах (округлённую до целого).

Примечание

Голосование при нечётном \( K \) не даёт равенства, но правило «при равенстве — 0» оставлено на случай совпадающих расстояний.

Искусственный интеллект Машинное обучение Подбор параметров модели (обучение)

—Войти и решать

4.3.4 Подбор интервала-классификатора (уровень 3)#96035

Прибор считает измерение «нормальным», если его значение попадает в некоторый интервал. Файл measure.txt содержит 2400 строк: значение метка (значение — вещественное от 0 до 100, метка: 1 — норма, 0 — отклонение).

Правило-интервал: метка 1, если \( L \le значение \le H \).

Переберите обе границы: \( L \) от 0 до 100 с шагом 5 и \( H \) от \( L + 5 \) до 100 с шагом 5. Найдите пару границ с максимальным числом верных классификаций. При равенстве выберите наименьшее \( L \), затем наименьшее \( H \).

В ответе запишите три целых числа через пробел: \( L \), \( H \) и число верных классификаций.

Искусственный интеллект Машинное обучение Подбор параметров модели (обучение)

—Войти и решать

4.3.3 Точность на обучении и тесте (уровень 3)#96034

Файл signal.txt содержит 3000 строк: уровень_сигнала метка (уровень — вещественный, метка: 1 или 0). Первые 2000 строк — обучающая выборка, последние 1000 — тестовая.

Правило: метка 1, если уровень не меньше порога \( K \).

Подберите порог \( K \) с максимальной точностью на обучающей выборке, перебирая значения от 0 до 100 с шагом 0.1 (при равенстве — наименьший порог).

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

В ответе запишите два числа через пробел: точность на обучении и точность на тесте.

Искусственный интеллект Машинное обучение Подбор параметров модели (обучение)

—Войти и решать

4.3.2 Лучший признак, направление и порог (уровень 3)#96033

Банк ищет лучший одиночный признак для прогноза дефолта. Файл credit.txt содержит 2200 строк: доход долговая_нагрузка возраст метка (первые три поля — целые, метка: 1 — дефолт, 0 — нет).

Для каждого из трёх признаков рассматривается пороговое правило. Правило может быть направлено в любую сторону: «метка 1, если признак не меньше порога» или «метка 1, если признак меньше порога» — выбирается то направление и порог, что дают наибольшую точность. Пороги перебираются по всем целым от минимума до максимума значений признака.

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

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

Искусственный интеллект Машинное обучение Подбор параметров модели (обучение)

—Войти и решать

4.3.1 Два порога дерева решений (уровень 3)#96032

Файл iris.txt содержит 2500 строк с данными о цветках трёх видов: длина_лепестка ширина_лепестка вид (длина и ширина — вещественные, вид: 0, 1 или 2).

Классификатор — дерево решений с двумя порогами \( P_1 \) и \( P_2 \):

если длина лепестка меньше \( P_1 \) — вид 0;
иначе, если ширина лепестка меньше \( P_2 \) — вид 1;
иначе — вид 2.

Переберите \( P_1 \) от 1.0 до 5.0 с шагом 0.1 и \( P_2 \) от 0.5 до 3.0 с шагом 0.1. Найдите пару порогов с максимальным числом верно классифицированных цветков. При равенстве выберите наименьший \( P_1 \), затем наименьший \( P_2 \).

В ответе запишите три числа через пробел: \( P_1 \) (один знак после запятой), \( P_2 \) (один знак после запятой) и число верных классификаций.

Искусственный интеллект Машинное обучение Подбор параметров модели (обучение)

—Войти и решать

4.2.5 Дробный порог, ошибки на тесте (уровень 2)#96031

Ферма сортирует ягоды по содержанию сахара. Файл berries.txt содержит 3500 строк: сахар_процент метка (сахар — вещественное число, метка: 1 — спелая, 0 — неспелая).

Первые 2500 строк — обучающая выборка, последние 1000 — тестовая.

Правило: ягода спелая, если сахар не меньше порога \( K \).

Подберите порог \( K \) с максимальной точностью на обучающей выборке, перебирая значения от 0 до 30 с шагом 0.1 (при равенстве точности — наименьший порог). Затем примените найденный порог к тестовой выборке.

В ответе запишите число ошибок классификации на 1000 тестовых ягодах.

Искусственный интеллект Машинное обучение Подбор параметров модели (обучение)

—Войти и решать

4.2.4 Выбор лучшего признака (уровень 2)#96030

Сервис прогнозирует отток клиентов. Файл churn.txt содержит 3000 строк: дней_без_активности число_обращений_в_поддержку метка (первые два поля — целые, метка: 1 — клиент ушёл, 0 — остался).

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

Определите, какой признак даёт более высокую максимальную точность: 1 — «дней без активности», 2 — «число обращений». Укажите номер этого признака и достигнутую им точность в процентах (округлённую до целого).

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

Искусственный интеллект Машинное обучение Подбор параметров модели (обучение)

—Войти и решать

4.2.3 Порог по сумме двух признаков (уровень 2)#96029

Система оценивает заявки по двум показателям. Файл apps.txt содержит 2800 строк: показатель1 показатель2 класс (показатели — целые от 0 до 100, класс: 1 или 0).

Правило использует сумму двух показателей: объект относится к классу 1, если \( x_1 + x_2 \ge K \).

Переберите целые \( K \) от 0 до 200, для каждого вычислите точность на всей выборке и найдите оптимальный порог \( K \) (при равенстве — наименьший).

В ответе запишите одно целое число — оптимальный порог \( K \).

Искусственный интеллект Машинное обучение Подбор параметров модели (обучение)

—Войти и решать