Везде, где не указано — время работы \(O(n)\), а если есть конкретные числа, то TL 1 секунда.
Задачи идут в порядке вспоминания, то есть в весьма рандомном.
Вам нужно передать 64 байт некоторой информации. Для этого у вас есть 320 специально обученных попугаев, каждый из которых может запомнить число от 0 до 255. Все попугаи рано или поздно долетают до точки назначения и сообщают свой байт, но, возможно, не в том порядке, в котором были выпущены. Попугаи внешне неразличимы.
Даны 68 камней разного веса. Требуется за 100 операций взвешивания определить самый лёгкий и самый тяжелый.
Есть перестановка из 64 элементов. Вы можете спрашивать, какие элементы находятся на заданном множестве позиций (вам сообщается список элементов в произвольном порядке). Восстановите перестановку за 6 запросов.
Требуется отвечать на 2 типа запросов:
Обе операции онлайн за \(O(\log n)\).
Найдите способ посчитать \(\frac{1-a^n}{1-a}\) по произвольному модулю за \(O(\log n)\).
В турнире участвуют 1024 видов покемонов. Вы, будучи экспертом по покемонам, знаете, кто кого может победить. Иначе говоря, вам полностью известен граф-турнир из 1024 вершин и \(1023 \times 1022 : 2\) рёбер, в котором каждые две вершины соединены ровно одним ориентированным ребром, определяющим победителя в возможном поединке. Обратите внимание, что из \(a \to b\) и \(b \to c\) не следует, что \(a \to c\).
У вас есть 10 покеболов. Составьте команду из 10 покемонов такую, что для каждого из 1024 типов покемонов в вашей команде найдется покемон, побеждающий его. Считайте, что в битве одинаковых покемонов побеждает ваш.
Можно ли отсортировать * 5 камней за 8 взвешиваний? * 5 камней за 7 взвешиваний? * 20 камней за 60 взвешиваний?
Даны \(n\) точек, равномерно распределенных в единичном круге с центром в начале координат. Предложите алгоритм, который за \(O(n)\) в среднем сортирует их по удаленности от начала координат.
Даны две замкнутые несамопересекающиеся ломаные. Определите, можно ли перевести их друг в друга с помощью параллельного переноса, поворотов и гомотетии?
Дан массив из \(n\) целых чисел. Требуется за \(2n\) операций «прибавить к одному элементу любой другой» сделать его неубывающим.
Дан неориентированный граф. Определите, есть ли в нём простой цикл чётной длины.
Дан массив из \(n\) целых чисел. Найдите его \(k\)-й наименьший элемент за \(O(n)\).
Дан массив из \(n\) элементов. Требуется ответить на \(m\) запросов, есть ли на отрезке \([l, r]\) доминирующий элемент — тот, который встречается на нём хотя бы \(\frac{r-l}{2}\) раз. Время работы \(O((n+m) \log n)\).
Дано корневое дерево. Каждую итерацию выбирается вершина (равновероятно из всех оставшихся), и удаляется всё поддерево, соответствующее этой вершине. Найти, сколько ходов в среднем будет продолжаться этот процесс, то есть матожидание номера итерации, на которой будет удалён корень дерева.
Дан массив из \(n\) целых чисел. Требуется ответить на \(m\) запросов \(k\)-ой порядковой статистики на произвольном отрезке. Время работы \(O((n+m) \log n)\).
Дан массив из \(n\) целых чисел. Требуется ответить на \(m\) запросов количества различных элементов на произвольном отрезке. Время работы \(O(m\sqrt{n})\).
Зачёт по физкультуре в одном институте ставится по количеству посещений, поэтому важно знать, сколько учебных дней осталось до конца семестра (особенно когда напропускал пары). Семестр длится \(m\) дней. Деканат последовательно издает \(n\) приказов двух типов:
При этом приказ может частично отменить действие предыдущих приказов.
После каждого приказа нужно посчитать суммарное число учебных дней в семестре. Асимптотика \(O(n \log n)\).
Дано мультимножество из \(n\) целых чисел. Найдите любое его подмножество, сумма чисел которого делится на \(n\).
В задаче дана произвольная строка, по которой известным только авторам способом генерируется ответ yes/no. В задаче 100 тестов. У вас есть 20 попыток. В качестве фидбэка вам доступны вердикты на каждом тесте. Вердикта всего два: OK (ответ совпал) и WA. Попытки поделить на ноль, выделить терабайт памяти и подобное тоже считаются как WA. «Решите» задачу.
В плоскую доску вбили \(n\) гвоздей радиуса \(r\), причём так, что соответствующие точки на плоскости образуют вершины выпуклого многоугольника. На эти гвозди натянули ниточку, причём ниточка «огибает» по кругу гвозди. Найдите длину ниточки, то есть периметр этого многоугольника с учётом закругления.
Компания друзей захотела сделать заготовки для пельменей из огромного прямоугольного куска теста. Для этого в ход пошли всевозможные предметы округлой формы: стаканы, кружки, кострюли… В итоге тесто было разделено \(n\) возможно пересекающимися окружностями произвольных радиусов и центров. Нам интересно посчитать, сколько получилось заготовок, то есть на сколько кусков распалось тесто. Асимптотика \(O(n^2 \log n)\).
Дан следующий код:
x = 0
while x < 1:
x += random()Требуется посчитать матожидание x.
(random в питоне возвращает случайное действительное число от 0 до 1.)
Дан единичный квадрат и 100 кругов. Нужно посчитать площадь квадрата, которую покрывают эти круги, с ошибкой менее 1%.
Имеется окружность радиуса \(R\), назовём её внешней. Внутри неё лежит окружность радиуса \(r < R\) и соприкасается с ней. Дальше строятся бесконечное число окружностей по следующему правилу: \(k\)-я окружность должна
Найдите (выведите формулу за \(O(1)\)) радиус \(k\)-й такой окружности.
Катя и Серёжа играют в игру. У Кати есть \(n\) карт, у Серёжи — \(m\). Одна дополнительная карта лежит на столе рубашкой вверх. Назовём её особой. Цель игроков — её отгадать. Все \(n+m+1\) карт различны, игроки изначально знают только свои карты. Игроки ходят по очереди, начинает Катя. Игрок в свой ход может:
С какой вероятностью выиграет Катя при оптимальной игре обоих игроков? Асимптотика \(O(nm)\).
Дан ориентированный граф без кратных рёбер. Для всех пар вершин \(u\) и \(v\) определите, можно ли дойти из \(u\) в \(v\). Вершин меньше 2000.
Есть \(n\) жадных коллекционеров монет, которые согласны меняться, только если взамен монеты, которых у них более одной, они получают монету, которых у них нет вовсе. Всего есть \(k\) типов монет. Известно количество монет каждого типа у каждого коллекционера и у коллекционера Серёжи. Серёжа хочет максимизировать количество различных монет у него путем обмена с жадными коллекционерами. Считайте, что жадные коллекционеры не меняются между собой.
Придумайте любой полиномиальный алгоритм.
В некотором королевстве жила принцесса. Она была настольно прекрасна, что каждый юноша в королевстве хотел жениться на ней. Принцесса была привередлива, поэтому твердо решила выйти замуж только за самого красивого юношу в государстве.
Она составила список из \(n\) самых красивых юношей и вызывает их каждый день в случайном порядке. После того, как к ней приходит очередной юноша, она принимает решение: либо выйти за него замуж, либо нет. Если она выходит за него замуж, то она все равно просматривает всех остальных, чтобы убедиться, что он действительно самый красивый. Если это так, то они живут долго и счастливо. Если нет (если она вышла замуж не за самого красивого, либо не вышла замуж вообще), то принцесса покончит жизнь самоубийством.
У принцессы очень хорошая память, поэтому она может сравнивать красоту очередного юноши со всеми предыдущими, а также у неё тонкий вкус, поэтому никакие двое юношей не являются для неё одинаково красивыми.
Помогите принцессе разработать стратегую, которая максимизирует вероятность того, что она выйдет замуж за наиболее красивого юношу.
Асимптотика \(O(n^2)\).
Определим спираль \((2n+1) \times (2n+1)\) как матрицу следующего вида:
\[ \begin{matrix} 21 & 22 & 23 & 24 & 25 \\ 20 & 7 & 8 & 9 & 10 \\ 19 & 6 & 1 & 2 & 11 \\ 18 & 5 & 4 & 3 & 12 \\ 17 & 16 & 15 & 14 & 13 \\ \end{matrix} \]
Ваша задача — рассчитать ответы на \(q\) запросов суммы чисел в произвольной прямоугольной области (по модулю \(10^9+7\)).
\(q \leq 100\), \(n \leq 10^9\).
Группа из \(n\) туристов гуляет в бесконечном лабиринте. Лабиринт имеет форму треугольника Серпинского: клетка \((x, y)\) свободна, только если x & y == 0.
Туристы устали блуждать по лабиринту и хотят встретиться в какой-нибудь свободной клетке, сумма расстояний от всех туристов до которой наименьшая. Туристы за один ход могут передвигаться вверх, вниз, влево и вправо по свободным клеткам.
\(n \leq 10^5\), изначальные координаты туристов до \(10^9\).
Есть множество \(A\), состоящее из \(n\) чисел от 0 до \(2^{32}-1\). Требуется выбрать его подмножество \(B \subseteq A\) максимальной суммы такое, что нельзя выбрать его подмножество \(C \subseteq B\) такое, что ним на кучках соответствующего размера — проигрышный. Асимптотика \(O(n \log n)\).
Дан неориентированный граф. Требуется ориентировать каждое ребро так, чтобы максимизировать число вершин, у которых степень исхода равна степени захода.
Дан ориентированный граф. Найдите два непересекающихся по рёбрам пути из \(s\) в \(t\).
Пьяница стоит на числовой прямой в точке 0. Каждую секунду он делает единичный шаг вправо (в сторону увеличения координат) с вероятностью \(p\) и влево с вероятностью \(1-p\). С какой вероятностью он когда-либо окажется в точке с отрицательной координатой?
Дан массив из \(10^5\) целых чисел от \(0\) до \((2^{30}-1)\). Найти количество различных подпоследовательностей этого массива, xor-сумма которых равна заданному числу \(x\).
Польская армия хочет добраться из поселения \(s\) в поселение \(t\). Ей руководят два гетмана — Камиль и Матеуш.
Каждый гетман перед маршем спрашивает дорогу у Ивана Сусанина. Иван хочет задержать наступление польских войск.
Карта дорог известна Камилю. Аналогично, карта секретных троп известна Матеушу. Поэтому Ивану не удастся их так просто обмануть — он должен каждый раз выбрать переход так, что минимальное расстояние между поселением \(t\) и войском по соответствующей карте строго уменьшилось.
Вы знаете карту дорог и троп вместе с их длинами. Помогите Ивану как можно дольше (желательно, бесконечно) вести армию из \(s\) в \(t\).
В ряд стоят \(n\) пустых банок из-под варенья. Вместительность \(i\)-й банки равна \(v_i\) грамм.
Карлсон наполняет эти банки вареньем в \(m\) этапов. На каждом этапе он выбирает числа \(l\), \(r\), \(x\) и \(y\), а затем пролетает над банками с \(l\) по \(r\), выполняя следующие операции: в банку номер \(l\) он добавляет \(x\) грамм варенья, в банку номер \((l + 1)\) — \((x + y)\) грамм варенья, в банку номер \((l + 2)\) — \((x + 2y)\), и так далее до \(r\)-той банки, в которую он положит \(x + y(r - l)\) грамм варенья.
Малышу хочется определить для каждой банки наименьший номер операции, после которой она станет полной.
\(n, m \leq 10^5\)
Серёжа потерялся в лабиринте \(n \times m\). Каждая клетка либо свободна, либо стена. Все крайние клетки — стены. Вам известно, где находится выход из лабиринта, но не известно, где находится Серёжа. Составьте для него последовательность направлений (вверх, вниз, влево, вправо) такую, после которой он окажется в клетке с выходом, вне зависимости от его стартовой позиции. Если вы прикажете ему идти в стену, то просто ничего не произойдёт.
Придумайте любой полиномиальный алгоритм.
Дана строка из \(10^5\) символов латинского алфавита. Обезьяна нажимает случайные клавиши на клавиатуре (одну из 26 букв), пока не наберёт её целиком, то есть пока исходная подстрока не станет подстрокой набранной строки. Какое ожидание числа нажатых клавиш перед тем, как это произойдёт?
Даны \(n\) случайных величин, равномерно распределенных на отрезках \([l_i, r_i]\) — у каждой величины свой отрезок. Найдите математическое ожидание минимума этих случайных величин.
Придумайте любой точный полиномиальный алгоритм.
Загадано некое число \(x\). Вы можете делать запросы следующего типа: назвать число \(y\) и получить в ответ число единичных битов в ксор-сумме \(x\), \(y\) и \(m\), где \(m\) это случайно сгенерированная маска, в которой каждый бит имеет вероятность \(p = \frac15\) быть единичным, то есть каждый бит \(x \oplus y\) заменяется на противоположный с вероятностью \(y\), и вам возвращается количество единичных битов. Для ясности:
x = # ...
def mask(p=0.2):
r = 0
for i in range(32):
if random.random() < p:
r += 2**i
return r
def query(y):
return bin(x ^ y ^ mask()).count('1')Ваша задача — отгадать число, используя не более 10000 попыток.