Яндекс.Блиц. 12 алгоритмических задач отборочного раунда и их разборы

в 7:30, , рубрики: Блог компании Яндекс, Занимательные задачки, конкурсы, конкурсы разработчиков, математика, Спортивное программирование, Яндекс.Блиц

В конце сентября мы рассказывали, что решили попробовать провести контест, где желающие могут потренироваться в решении задач, максимально приближенных к «боевым». Так участники могут понять, какого формата задания получают разработчики на собеседованиях в Яндексе (этим интересуются очень многие), а самое главное — с чем они сталкиваются, работая над Поиском. Типичная задача на собеседовании — составить алгоритм, доказать его корректность, предложить пути оптимизации. Если человек разбирается в алгоритмах, то он быстро сумеет их реализовывать на любом доступном ему языке.

В Блице можно использовать Java, C++, C# или Python. Кроме того, участие в контесте дает возможность проверить свои знания. Если в итоге вы понимаете, что их стоит подтянуть, — это тоже результат. Кстати, тогда вам может пригодиться специализация на курсере «Алгоритмы и структуры данных», в создании которой Яндекс участвовал.

image

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

«Игра»

Условие

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

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

Гарантируется, что для любого теста победителя можно будет определить однозначно.

Дополнительные параметры

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

В первой строке входных данных записано целое число $n$, кратное трем, — общее количество карточек $(3 leq n leq 999)$.

В следующей строке записаны $n$ различных целых положительных чисел $a_i$ — значения, написанные на карточках в том порядке, в котором Петя и Вася будут их раздавать $(1 leq a_i leq 1000)$.

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

В единственной строке выведите Petya, если в игре побеждает Петя, или Vasya, если в игре побеждает Вася.

Примеры

Ввод Вывод
3
1 2 3 
Petya
Ввод Вывод
3
1 4 2 
Vasya

Ограничение по времени: 2 секунды

Ограничение по памяти: 64 МБ

Решение

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

«Сложные числа»

Условие

Обозначим через $S(n)$ сумму цифр натурального числа $n$.

Будем говорить, что натуральное число $n$ сложное, если не существует такого натурального числа $k,$ что

$n=frac{3k}{S(k)^2}.$

Найдите наименьшее сложное число.

Решение

Здесь можно придумать математическое решение, однако от нас требуется лишь найти наименьшее число, удовлетворяющее условию задачи. При этом ни доказательство, ни код писать не нужно, а времени на остальные задачи у нас не так много. Поэтому можно вместо поиска обоснованного решения воспользоваться перебором. Вот один из вариантов перебора: посчитаем значение функции для всех $k$ от 1 до некоторого предела (например, до миллиона) и, если оно целое, запомним, что такое число $n$ точно не будет сложным. Затем выведем наименьшее натуральное число, которое мы не запоминали в процессе вычисления нашей функции. В нашем примере это будет число 61.

«Турнирная таблица»

Условие

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

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

Дополнительные параметры

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

Входные данные представляют собой набор строк, каждая строка описывает ровно один сыгранный матч. В каждой строке записаны названия играющих друг с другом команд и результат матча. Названия и результат разделяются знаком тире, отбитым с обеих сторон пробелами. Каждое название состоит только из латинских букв, начинается с заглавной буквы, все остальные буквы строчные, гарантируется что длина каждого названия не превосходит 30 символов. Счет записывается в виде A:B, где A — количество голов, забитых первой командой, а B — количество голов, забитых второй командой. Победившей считается команда, забившая больше голов. Если забито одинаковое количество голов, результатом матча считается ничья. За победу команде присуждается три очка, за ничью — одно, за поражение — ноль.

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

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

Вам нужно построить турнирную таблицу с результатами.

Каждая строка таблицы — представление результатов каждой из команд, команды должны быть упорядочены в лексикографическом порядке. В первом столбце содержится порядковый номер команды, во втором — название. Далее следуют $n$ столбцов, в каждом из которых содержится информация об играх с остальными командами: в случае победы в ячейке должна присутствовать буква W, в случае поражения — L, в случае ничьей — D, если участники не играли друг с другом — пробел, если заполняется ячейка матча игрока с самим собой, то туда следует поставить символ X.

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

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

Оформляя таблицу, ориентируйтесь на примеры.

Примеры

Ввод Вывод
Linux - Gentoo - 1:0
Gentoo - Windows - 2:1
Linux - Windows - 0:2
+-+--------+-+-+-+-+-+
|1|Gentoo  |X|L|W|3|1|
+-+--------+-+-+-+-+-+
|2|Linux   |W|X|L|3|1|
+-+--------+-+-+-+-+-+
|3|Windows |L|W|X|3|1|
+-+--------+-+-+-+-+-+

Ввод Вывод
Cplusplus - C - 1:0
Cplusplus - Php - 2:0
Java - Php - 1:0
Java - C - 2:2
Java - Perl - 1:1
Java - Haskell - 1:1
+-+----------+-+-+-+-+-+-+-+-+
|1|C         |X|L| |D| | |1|3|
+-+----------+-+-+-+-+-+-+-+-+
|2|Cplusplus |W|X| | | |W|6|1|
+-+----------+-+-+-+-+-+-+-+-+
|3|Haskell   | | |X|D| | |1|3|
+-+----------+-+-+-+-+-+-+-+-+
|4|Java      |D| |D|X|D|W|6|2|
+-+----------+-+-+-+-+-+-+-+-+
|5|Perl      | | | |D|X| |1|3|
+-+----------+-+-+-+-+-+-+-+-+
|6|Php       | |L| |L| |X|0| |
+-+----------+-+-+-+-+-+-+-+-+

Ограничение по времени: 2 секунды

Ограничение по памяти: 64 МБ

Решение

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

Из-за достаточно небольшого объема входных данных можно применять не сложные структуры, а стандартные механизмы любого из доступных языков. Например, при использовании C++ подойдет контейнер std::map. Ключом в контейнере будет название команды, а значением — информация о ней: количество набранных очков, число побед и результаты игр с другими командами. Результаты тоже можно хранить в std::map, где ключ — название оппонента, а значение — результат матча.

Разобьем на части каждую из строк входного потока и обновим информацию о каждом из участников. std::map, выбранный в качестве хранилища, позволяет нам хранить все названия в лексикографическом порядке, поэтому для формирования итоговой таблицы нам нужно всего лишь проитерироваться по элементам хранилища. Когда весь входной поток обработан, посчитаем итоговое место каждого из участников: выберем все пары вида «количество очков — число побед» и упорядочим их в порядке убывания, расставив соответствующие места для первых трех результатов. Кроме того, при пост-обработке мы можем посчитать необходимое количество символов для каждого из столбцов результирующей таблицы, а затем аккуратно реализовать вывод таблицы в выходной поток.

«Кошельки и монеты»

Условие

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

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

Дополнительные параметры

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

В первой строке выходных данных содержится натуральное число $n$ $(1 leq n leq 100)$ — количество кошельков у Пети.

Во второй строке через пробел записаны данные из восстановленного файла: $n$ натуральных чисел $a_i$, каждое из которых означает, сколько денег лежит в $i$-м кошельке у Пети $(1 leq a_i leq 100)$.

В третьей строке записано натуральное число $m$ $(1 leq m leq 10^4)$ — общая сумма денег, которая была у Пети до того, как он разложил ее по кошелькам.

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

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

Примеры

Ввод Вывод
2
2 3
5
Yes

Ввод Вывод
2
2 3
4
No

Ввод Вывод
2
2 3
3
Yes

Примечания

В первом примере у Пети есть два кошелька, в первом лежат две монеты, во втором — три. Конфигурации, приведенной во втором примере, не может существовать, поэтому файл восстановлен некорректно. В третьем примере предложенная конфигурация возможна: во втором кошельке лежит одна монета и первый кошелек, внутри которого лежат две монеты.

Ограничение по времени: 2 секунды

Ограничение по памяти: 64 МБ

Решение

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

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

«Хорошая последовательность»

Условие

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

Последовательность точек в трехмерном пространстве называется хорошей, если ни одна из последовательностей, полученных взятием проекции исходной на одну из базовых плоскостей $(Oxy,$ $Oyz$ и $Oxz),$ не является тривиальной.

Дана последовательность из $n$ точек с целочисленными координатами в трехмерном пространстве. Необходимо найти такую нечетную перестановку ее индексов, что после ее применения последовательность становится хорошей.

Гарантируется, что решение существует.

Дополнительные параметры

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

В первой строке входных данных записано целое число $n$ $(3 leq n leq 1000)$, в следующих $n$ строчках через пробел записаны по три целочисленных координаты $x_i, y_i, z_i$ $(-10^4 leq x_i, y_i, z_i leq 10^4)$ каждой из точек.

Гарантируется, что проекции всех точек на любую из базовых плоскостей различны.

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

Выведите $n$ чисел: искомая перестановка индексов от 1 до $n$. Если существует несколько решений, выведите любое из них. Числа в строке следует разделять пробелами.

Примеры

Ввод Вывод
4
1 1 1
2 4 16
3 9 81
4 16 256
1 2 4 3

Примечания

Инверсией в перестановке $p$ порядка $n$ называется всякая пара индексов $(i, j)$ такая, что $1 leq i < j leq n$ и $p_i > p_j$. Четность числа инверсий в перестановке определяет четность перестановки.

Ограничение по времени: 2 секунды

Ограничение по памяти: 64 МБ

Решение

Для корректного решения задачи нам вполне достаточно оценить, сколько существует тривиальных перестановок. В каждой из плоскостей их число пропорционально $O(n)$, где $n$ — общее количество точек. Значит, всего в пространстве их будет $O(n^3)$. При этом общее число перестановок, которое может послужить корректным ответом, равно $n!/2$ (деление происходит из-за того, что нам нужны только нечетные перестановки). Получается, что непригодных ответов гораздо меньше, чем тех, которые нас устраивают. Следовательно, мы можем просто осуществить перебор нечетных перестановок. Ответом будет первая перестановка, которая не является тривиальной при построении ее проекции ни на одну из трех плоскостей.

«Интересное путешествие»

Условие

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

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

Расстояние между двумя городами считается как сумма модулей разности по каждой из координат. Дороги есть между всеми парами городов.

Дополнительные параметры

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

В первой строке входных данных записано количество городов $n$ ($2 leq n leq 1000$). В следующих $n$ строках даны два целых числа: координаты каждого города, не превосходящие по модулю миллиарда. Все города пронумерованы числами от 1 до $n$ в порядке записи во входных данных.

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

В последней строке записаны два различных числа — номер города, откуда едет Петя, и номер города, куда он едет.

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

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

Примеры

Ввод Вывод
7
0 0
0 2
2 2
0 -2
2 -2
2 -1
2 1
2
1 3
2

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

Ввод Вывод
4
0 0
2 0
0 2
2 2
1
1 4
-1

Ограничение по времени: 1 секунда

Ограничение по памяти: 64 МБ

Решение

Вначале из имеющихся точек нужно построить граф. Для этого переберем все пары точек и, если расстояние между ними меньше заданного ограничения, добавим в граф ребро между вершинами. После построения графа запустим поиск в ширину из города, откуда Петя начинает свое путешествие. Как только он достигнет точки назначения, завершим наш алгоритм и выведем количество пройденных нами ребер. Если алгоритм завершился, а мы так и не достигли пункта назначения, то он недостижим из исходного города, поэтому следует вывести -1. Общая сложность описанного алгоритма — $O(n^2)$, где $n$ — число городов.

«Разделение числа»

Условие

Дано число $n$. Разбейте десятичную запись числа $n$ на максимальное возможное количество различных чисел.

Использовать числа с незначащими нулями не разрешается.

Дополнительные параметры

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

В единственной строке входных данных задано число $n$ ($0 leq n leq 10^{19}$).

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

Выведите разбиение числа $n$ на различные части. Между частями поставьте знак «-». Если есть несколько возможных разбиений, выведите любое.

Примеры

Ввод Вывод
0
0

Ввод Вывод
101
10-1

Ввод Вывод
102
1-0-2

Ввод Вывод
11
11

Ограничение по времени: 2 секунды

Ограничение по памяти: 64 МБ

Решение

Несмотря на то, что исходное число может быть очень большим, количество способов разбить его на части зависит не от значения, а от количества знаков в числе. В худшем случае число состоит из 18 десятичных знаков (вариант 1019 мы не рассматриваем — там только один вариант разбиения). Значит, знак «-» мы можем поставить только в 17 различных позициях. В каждой из этих позиций мы можем как поставить знак, так и опустить его. Другими словами, существует всего 217 способов выбрать разбиение для самых больших чисел. Это около 105 вариантов. Переберем их все, отсечем те, которые нас не устраивают (то есть при которых получаются одинаковые числа), и выберем вариант, содержащий наибольшее количество частей.

«Максимальный урон»

Условие

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

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

Дополнительные параметры

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

В единственной строке входных данных через пробел записаны натуральные числа $n$ и $a$ $(1 leq n, a leq 10^6, n neq a)$ — количество юнитов, которые есть у Игоря, и число юнитов в группе, которое Игорь считает несчастливым.

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

Выведите максимально возможный общий урон по модулю 109 + 7.

Примеры

Ввод Вывод
8 2
16

Ввод Вывод
9 3
20

Примечания

В первом примере для максимизации общего урона следует разбить юниты на две группы по 4 юнита в каждом, во втором примерe — на две группы: в первой 4 юнита, во второй — 5.

Ограничение по времени: 2 секунды

Ограничение по памяти: 64 МБ

Решение

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

Докажем, что такое разбиение корректно. Попробуем доказать это методом от противоположного. Предположим сначала, что в нашем разбиении есть числа $x$ ≥ 5. Но тогда мы можем заменить $x$ на два числа: $x$-3 и 3. На общую сумму замена никак не повлияет, а произведение чисел 3 и $x$-3 всегда больше чем $x$ при $x$ ≥ 5. Так что чисел, превосходящих или равных 5 в нашей последовательности существовать не может. Предположим, что в ней есть число 4, но мы можем заменить его на две двойки, никак не повлияв на значения суммы и произведения, поэтому давайте так и поступим. Далее, в нашей последовательности не может быть больше двух двоек, иначе мы могли бы заменить любые три из них на две тройки. Значение суммы от этого бы не поменялось, а значение произведения увеличилось бы (8 = 2⋅2⋅2 < 3⋅3 = 9). Следовательно, трех или большего числа двоек тоже не может быть. Ну и кроме того, у нас не может быть единиц (только если исходная сумма сама не равна единице). Таким образом, наша результирующая последовательность может состоять только из троек и не более чем двух двоек, что мы и показали выше.

Вернемся к ограничению на несчастливый размер группы. Если он превышает значение 3 — наше решение останется точно таким же. Если он равен 3, то, перебрав маленькие размеры групп вручную, будем разбивать последовательность на группы размером 2. Если изначально число юнитов нечетное, то дополнительно возьмем группу, состоящую из 5 юнитов (поскольку одна группа размера 5 обеспечит большее финальное значение, нежели 2 группы по 2 юнита и одна группа из одного юнита). Если же исключены размеры группы, равные 2, то используем алгоритм деления на группы по 3 юнита. Наконец, если их начальное число не делится на 3 нацело, возьмем в качестве размера дополнительных групп не 2, а 4 юнита.

«Красно-черные деревья»

Условие

Красно-черным деревом называется дерево, у которого все вершины покрашены в красный или черный цвет и есть еще дополнительные свойства:

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

Найдите число неизоморфных красно-черных деревьев с заданным числом вершин. Два красно-черных дерева $T_1$ и $T_2$ являются изоморфными, если существует биекция между вершинами деревьев $f: V(T_1) rightarrow V(T_2)$, удовлетворяющая условиям:

  • $f(root(T_1)=root(T_2))$, т. е. корень переходит в корень.
  • Если $f(v)=u$ и у вершины $v$ есть дети ($v_l$ и $v_r$), то и у вершины $u$ есть дети ($u_l$ и $u_r$), при этом или $f(v_l)=u_l$ и $f(v_r)=u_r$, или $f(v_l)=u_r$ и $f(v_r)=u_l$.
  • $f$ сохраняет цвет вершин, то есть $color (v)=color (f(v))$.

Дополнительные параметры

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

В первой строке задано число вершин дерева $n$ ($1 leq n leq 1000$).

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

Выведите число неизоморфных красно-черных деревьев с $n$ вершинами по модулю 109 + 7.

Примеры

Ввод Вывод
5
1

Ввод Вывод
7
2

Ввод Вывод
6
0

Ограничение по времени: 2 секунды

Ограничение по памяти: 256 МБ

Решение

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

Обозначим как $CountBlack[N][H]$ количество различных с точностью до изоморфизма красно-черных деревьев с черным корнем, которые состоят из $N$ вершин и у которых количество черных вершин от корня до листьев равно $H$. За $CountRed[N][H]$ мы обозначим такие же деревья с красным корнем. Это будет нарушать свойство черного корня у красно-черных деревьев, однако такое допущение нужно нам для вычисления результата.

Как вычислить значение $CountBlack[N][H]$? Корнем у него может быть любое число $i$ от 1 до $N$. Тогда в левом поддереве будет содержаться $i-1$ вершина, а в правом — $j=N-i$ вершин. Сколько поддеревьев может получиться в левом поддереве? Если его корень черный, то число поддеревьев равно $CountBlack[i-1][H-1]$, а если красный, то $CountRed[i-1][H-1]$. Аналогично для правого поддерева: $CountBlack[j][H-1]$, если корень поддерева черный, и $CountRed[j][H-1]$, если корень красный. Просуммируем числа, полученные для левого и правого поддеревьев: $CountLeft=CountBlack[i-1][H-1] + CountRed[i-1][H-1]$ и $CountRight=CountBlack[j][H-1] + CountRed[j][H-1].$ Получим общее количество поддеревьев, которые могут быть в нашем дереве с корнем в вершине $i$. Поскольку нам нужно вычислить количество деревьев с точностью до изоморфизма, достаточно посчитать ответ для $i-1 leq j$. Если $i-1 < j$, то прибавим к ответу $CountBlack[N][H]$ произведение числа поддеревьев слева и справа: $CountLeft⋅CountRight$. Если же мы строим оба поддерева из одинакового числа элементов ($i-1=j$), то к результату нужно прибавить $CountLeft⋅(CountLeft+1)/2$ вариантов.

При вычислении значения $CountRed[N][H]$ давайте действовать тем же способом, но с двумя замечаниями. Во-первых, число черных вершин во втором индексе не изменяется, поскольку наш корень красный. А во-вторых, раз у красного корня не может быть красных потомков, то слева и справа у нас могут быть только деревья с черными корнями. Следовательно, если мы выбрали число $i$ в качестве нашего красного корня, то количество деревьев слева равно $CountBlack[i-1][H]$, а количество деревьев справа — $CountBlack[j][H]$. Остальные вычисления аналогичны первому случаю.

Чтобы посчитать ответ для исходной задачи, нам нужно вычислить $CountBlack[N][H]$ для всех возможных $H$. Количество черных вершин от корня до любого из листьев пропорционально логарифму от количества элементов в дереве. Следовательно, достаточно рассмотреть черные высоты, не превосходящие $H=2⋅log(N) ≈ 20$. Переберем все $H$ от 1 до 20 и просуммируем все значения $CountBlack[N][H]$. Полученная сумма и будет ответом к задаче.

«Все кроме одной»

Условие

Даны $k$ перестановок из $n$ элементов, каждая из которых принадлежит к одному из $m$ типов.

Посчитайте позицию первого элемента, если последовательно применить эти $k$ перестановок, убрав одну из них.

Дополнительные параметры

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

В первой строке входных данных заданы числа $n$ и $m$ ($1 leq n leq 1000$, $1 leq m leq 100$).

В следующих $m$ строках записано по $n$ чисел. $i$-е число описывает позицию, на которую нужно переставить $i$-й элемент.

В следующей строке записано число $k$ ($1 leq k leq 5 cdot 10^4$). В следующей строке записаны $k$ чисел от 1 до $m$ — типы перестановок в начальном наборе.

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

Для каждой из $k$ перестановок выведите в отдельной строке позицию первого элемента, если последовательно применить все остальные перестановки.

Примеры

Ввод Вывод
3 2
1 3 2
2 3 1
3
1 2 1
3
1
2

Ввод Вывод
2 2
1 2
2 1
3
1 2 1
2
1
2

Ввод Вывод
1 1
1
1
1
1

Ограничение по времени: 2 секунды

Ограничение по памяти: 128 МБ

Решение

Обозначим за $prefix[i]$ перестановку, которая получается при последовательном выполнении всех перестановок от первой до $i$-й из нашего набора, содержащего $k$ перестановок. За $suffix[i]$, в свою очередь, обозначим перестановку, которая получается при последовательном выполнении всех перестановок от $i$-й до $k$-й. Легко увидеть, что, зная $prefix[i-1]$, мы можем получить $prefix[i]$, просто применив к $prefix[i-1]$ $i$-ю перестановку из нашего набора. При этом сложность такого вычисления — $O(n)$, где $n$ — количество элементов в перестановке. Значит, мы можем последовательно вычислить все перестановки $prefix[i]$ для $i$ от 1 до $k$ за время $O(n⋅k)$. Аналогично мы можем вычислить все перестановки $suffix[i]$, если увидим, что $suffix[i]$ получается применением $suffix[i+1]$ к $i$-й перестановке. Тогда чтобы вычислить, какой элемент будет на первой позиции, если мы исключим некую $j$-ю перестановку из нашего списка, нам достаточно применить к перестановке $prefix[j-1]$ перестановку $suffix[j+1]$. Обозначив за $prefix[0]$ и $suffix[k+1]$ тождественные перестановки и проверив все $j$ от 1 до $k$, мы получим ответ к задаче. Поскольку для каждого $j$ время применения одной перестановки к другой пропорционально $O(n)$, итоговая сложность алгоритма — $O(n⋅k)$.

«Вложенные прямоугольники»

Условие

На клетчатой плоскости отмечено $n$ клеток.

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

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

Дополнительные параметры

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

В первой строке входных данных задано число $n$ $(1 leq n leq 100000)$ — количество отмеченных клеток. В следующих $n$ строках заданы целые координаты $i$-й отмеченной клетки $x_i, y_i$ $(|x_i| leq 10^9, |y_i| leq 10^9)$. Все отмеченные клетки различны.

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

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

Примеры

Ввод Вывод
1
-1 -1
1

Ввод Вывод
3
-1 -1
0 0
1 1
2

Ввод Вывод
5
0 1
1 0
1 1
2 1
3 2
2

Ограничение по времени: 2 секунды

Ограничение по памяти: 64 МБ

Решение

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

«Игра с числами»

Условие

Дана последовательность $n$ положительных чисел $a_1, a_2, …, a_n$. Пока среди них есть различные, выполняется следующая операция: выбирается некоторое максимальное число и из него вычитается минимальное число.

Через сколько операций числа станут одинаковыми?

Дополнительные параметры

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

В первой строке входных данных задано число $n$ ($1 leq n leq 1000$). В следующей строке заданы $n$ чисел $a_i$ ($1 leq a_i leq 10^9$).

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

Количество операций, после которых все числа станут одинаковыми.

Примеры

Ввод Вывод
2
1 1
0

Ввод Вывод
3
9 6 3
3

Ввод Вывод
6
1000000000 1000000000 1000000000 1000000000 1000000000 1
4999999995

Ограничение по времени: 2 секунды

Ограничение по памяти: 64 МБ

Решение

Пусть $a$ — текущее минимальное число. Заметим, что пока максимальное число больше, чем $2cdot a$, минимальное число при наших операциях вычитания не изменяется. Давайте посчитаем, сколько нам понадобится операций до тех пор, пока максимальное число станет меньше, чем $2cdot a$. Поскольку при всех таких операциях всегда вычитается число a, то достаточно найти все числа, которые превышают $2cdot a$, и с помощью деления вычислить, после какого количества вычитаний эти числа впервые станут меньше, чем $2cdot a$. Как только максимум станет меньше, чем $2cdot a$, мы просто смоделируем одну операцию вычитания, после которой минимум гарантированно изменится. Затем будем повторять предыдущую процедуру до тех пор, пока максимум не совпадет с минимумом. Оценим число итераций. Обозначим сумму всех чисел за $S$. Тогда $S leq 2na$, а при каждой итерации сумма чисел уменьшается по крайней мере на $a geq S/(2n)$. Таким образом, сумма всех чисел уменьшается хотя бы в $1-1/(2n)$ раз. Поэтому нам понадобится не больше чем $O(ncdot log(Mn))$ итераций цикла, где $M$ — максимальное число в исходном наборе.

Автор: nkmakarov

Источник


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js