Russian Code Cup 2013 – разбор задач отборочного раунда

В прошедшее воскресенье состоялся отборочный раунд Russian Code Cup. Это последний онлайн-раунд соревнования: решающая встреча финалистов пройдет в Москве. Для того чтобы участвовать в финале, нужно было приложить больше усилий, чем на предыдущих этапах. Участникам предлагалось шесть задач (в квалификационных раундах было на одну меньше), на их решение выделялось три часа (в квалификационных — два).

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

• Задача A: Две башни
• Задача B: Депозит
• Задача C: Кеплер
• Задача D: Тест
• Задача E: Лазеры
• Задача F: Колесо

За время раунда авторизовались 439 человек, из них хотя бы одно решение прислал 371 участник. Всего было отправлено 3334 решения.

Участники, первыми приславшие решения соответствующих задач, и время после начала раунда (мин: сек):

• Задача А: RAVEman (9:12)
• Задача B: ant.ermilov (16:58)
• Задача C: Zhukov_Dmitry (5:52)
• Задача D: e-maxx (33:05)
• Задача E: winger (37:50)
• Задача F: tourist (82:51)

Территориальное распределение участников в этом раунде было следующим:

Россия => 183
Украина => 53
Беларусь => 23
Соединенные Штаты Америки => 18
Казахстан => 5
Германия => 4
Швейцария => 3
Латвия => 2
Армения => 2
Болгария => 1
Исландия => 1
Венгрия => 1
Узбекистан => 1
Грузия => 1
Испания => 1
Литва => 1
Великобритания => 1
Австрия => 1
Кипр => 1
Польша => 1

Только к концу третьего часа стала складываться картина списка победителей. В финал вышли 50 человек. Первые 10 из них:

1. Владислав Исенбаев
2. Геннадий Короткевич
3. Дмитрий Джулгаков
4. Пётр Митричев
5. Владислав Епифанов
6. Артем Рахов
7. Михаил Кевер
8. Дмитрий Гозман
9. Дмитрий Жуков
10. Евгений Капун

И, наконец, перейдем непосредственно к разбору задач.

Задача A. Две башни
Идея: Федор Царев
Реализация: Павел Кротков, Андрей Станкевич
Разбор: Павел Кротков

Условие задачи

Ограничение по времени: 2 секунды
Ограничение по памяти: 256 мегабайт

Компания Mail.World недавно переехала в новый офис, который имеет вид двух башен-небоскребов по 10⁹ этажей каждая. На некоторых этажах башни соединены переходами, по которым можно перейти из одной в другую. Всего есть n переходов, они соединяют башни на этажах a₁, a₂, ..., a_n

Артем работает в башне b₁ на L₁-м этаже. Сегодня ему необходимо пообщаться со своим коллегой Дмитрием, который работает в башне b₂ на L₂-м этаже. Как ни странно, оказалось, что выбрать самый быстрый способ добраться от рабочего места Артема до рабочего места Дмитрия не так просто.

В каждой из башен установлен один лифт. Лифт в башне 1 проезжает один этаж за время u₁ секунд, а лифт в башне 2 — за u₂ секунд. На путь между башнями по переходу Артем тратит t секунд.

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

В первом примере Артему необходимо просто проехать на лифте первой башни.

Во втором примере лифт во второй башне ходит существенно быстрее, и Артему выгоднее перейти по переходу во вторую башню, проехать на лифте до 10 этажа, вернуться в первую башню и проехать еще один этаж на лифте в первой башне.

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

Первая строка содержит целое положительное число t — число тестовых примеров во входных данных. Далее следуют описания тестовых примеров.

Первая строка содержит n — число переходов между башнями (1 ≤ n ≤ 10⁵). Вторая строка содержит n различных целых чисел a₁, a₂, ...,a_n (1 ≤ a₁ < a₂ <… < a_n ≤ 10⁹). Следующая строка содержит три целых положительных числа: u₁, u₂ и t (каждое из них лежит в диапазоне от 1 до 10⁹). Наконец, следующие две строки содержат по два числа: b₁, L₁ и b₂, L₂, соответственно (каждое из b₁ и b₂ равно 1 или 2, 1 ≤ L₁, L₂ ≤ 10⁹).
Суммарное число переходов во всех тестовых примерах во входных данных не превосходит 10⁶.

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

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

Примеры

Входные данные	Выходные данные
2 1 5 3 3 2 1 1 1 10 2 1 10 5 3 2 1 1 1 11	27 36

Разбор задачи

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

Построим граф из интересных нам этажей. Интересными будем считать следующие этажи:

• Этаж, на котором работает Артем, в башне, в которой работает Артем
• Этаж, на котором работает Дмитрий, в башне, в которой работает Дмитрий
• Этажи, которые являются концами ближайших переходов к Артему (в сумме получаем 2 вершины от перехода, который выше, и 2 вершины от перехода, который ниже)
• Добавляем 4 вершины аналогично предыдущему пункту, но только для Дмитрия

Рёбра в нашем графе бывают двух типов:

• Рёбра, соединяющие вершины, между которыми есть переход. Веса у таких рёбер равны t
• Рёбра, соединяющие вершины из одной башни. Веса у таких рёбер равны расстоянию между соответствующими этажами, умноженному на скорость лифта в соответствующей башне

Заметим, что в нашем графе 10 вершин. Искать кратчайшие пути в этом графе можно любым методом, проще всего было реализовать алгоритм Флойда.

Задача B. Депозит
Идея: Борис Минаев
Реализация: Виталий Демьянюк
Разбор: Виталий Демьянюк

Условие задачи

Ограничение по времени: 2 секунды
Ограничение по памяти: 256 мегабайт

За много лет трудового стажа Василий Иванович заработал k рублей. Теперь Василий Иванович вышел на пенсию и хочет положить эти деньги на депозит на ближайшие m лет. В его родном городе работает n банков. Если у Василия Ивановича в банке с номером i на протяжении j-го года на счету лежат деньги, то в конце года их количество на этом счету увеличится на p_i,j процентов.

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

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

Найдите максимальное суммарное число рублей на всех счетах Василия Ивановича в конце m-го года.

В примере Василий Иванович сначала кладет деньги во второй банк. После первого года у него 115 рублей, он выбирает для перераспределения оба банка. Уплатив комиссию 2 рубля, он кладет все деньги в первый банк. В конце года у него 113×1.15=129.95 рублей на счету в банке.

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

В первой строке содержится натуральное число t — количество тестов. (1 ≤ t ≤ 50)

Описание каждого теста начинается со строки, содержащей три целых числа n, m и k — количество банков, лет и заработанных рублей соответственно. (1 ≤ n ≤ 10000, 1 ≤ m ≤ 20, 1 ≤ k ≤ 10⁹) В следующей строке содержится n целых чисел, где i-е число равно a_i — комиссии i-го банка (1 ≤ a_i ≤ 10⁹). В каждой из следующих n строк содержится по m целых чисел. В i-й строке j-е число равно p_i,j — процент дополнительных денег, получаемых Василием Ивановичем в j-м году на счет в i-м банке (0 ≤ p_i,j ≤ 100).

Суммарное количество банков во всех тестах не превышает 50000.

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

Для каждого теста в отдельной строке выведите максимальное суммарное количество денег на всех счетах Василия Ивановича в конце m-го года. Ваш ответ будет засчитан, если его относительная погрешность не превышает 10⁻⁶.

Примеры

Входные данные	Выходные данные
1 2 2 100 1 1 10 15 15 10	129.95

Разбор задачи

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

С учетом только что доказанного факта задача решается методом динамического программирования. Пусть dp_i,j равно максимальному количеству рублей на счетах Василия Ивановича через i лет, если на протяжении i-года все его деньги лежали в j-том банке. Переберем все банки, где деньги могли храниться в предыдущем году, тогда dp_i,j = (max(dp_i-1,k -a_k) — a_j) • p_j,i по всем k от 1 до n.

Отдельно рассмотрим случай, когда j = k, тогда dp_i,j = max(dp_i,j, dp_i,j-1 •p_j,i). Ответ равен максимальному dp_m,k по всем k. В итоге на первый взгляд решение работает за O(n2m). Однако заметим, что dp_i-1,k — a_k не зависит от j. Поэтому, если для всех i поддерживать max(dp_i-1,k — a_k), то получим решение за O(nm).

Задача C. Кеплер
Идея: Виталий Аксёнов
Реализация: Андрей Комаров
Разбор: Андрей Комаров

Условие задачи

Ограничение по времени: 2 секунды
Ограничение по памяти: 256 мегабайт

После выхода из строя второго гироскопа астрономический телескоп «Кеплер» стал непригоден для дальнейшей эксплуатации. NASA решило возместить эту потерю и запустить в космос другой телескоп. Для того чтобы обеспечить телескоп электричеством, решено было использовать солнечные батареи. Заготовка для солнечной батареи представляет собой прямоугольную панель размером n×m, состоящую из ячеек 1×1.

К сожалению, невозможно доставить батарею на орбиту в развёрнутом состоянии. Для облегчения транспортировки панель сделана из тонкого материала и может сгибаться вдоль любой границы ячеек. Учёные решили, что батарея полетит в космос сложенной до размера 1×1.

Для этого они поступают с заготовкой для батареи следующим образом: если одна из сторон текущей заготовки имеет чётную длину, то можно сложить заготовку вдоль неё пополам; получается панель вдвое меньшего размера (толщиной панели можно пренебречь). Если же какая-то из сторон имеет нечётную длину (панель имеет размер (2n+1)×m), то они могут сверхточным лазером за время m отрезать от неё кусок размера 1×m, а затем сложить пополам вдоль стороны длиной 2n. Отрезанный кусок панели выбрасывается. В итоге у учёных получается панель 1×1, которая полетит на орбиту и там развернётся.

Лазер работает намного дольше, чем происходят все складывания. Помогите им определить, какого наименьшего времени работы лазера они могут добиться, чтобы свернуть указанным образом исходную заготовку в квадрат размером 1×1.

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

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

Первая строка содержит целое число t (1 ≤ t ≤ 1000) — число тестовых запросов. Следующие t строк содержат сами запросы. Каждый запрос состоит из двух целых чисел n и m (1 ≤ n, m ≤ 10⁹) — начальный размер заготовки для солнечной батареи.

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

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

Примеры

Входные данные	Выходные данные
3 1 1 4 4 3 2	0 0 1

Разбор задачи

Изучим, какого размера может получаться панель при всех возможных складываниях. Зафиксируем одну из сторон и посмотрим, как будет со временем изменяться её длина. Рассмотрим на примере стороны, соответствующей первому измерению. Пусть изначально панель имела размер n×m. Интересующая сторона имеет длину n. Далее возможны два случая:

• Складываем вдоль стороны длины n. В этом случае новая длина равна ⌊n/2⌋
• Складываем вдоль стороны длины m. В этом случае длина не изменится и останется равной n

Значит, сторона может иметь только длину n, ⌊n/2⌋, ⌊⌊n/2⌋/2⌋, ..., 1. Их всего N=⌊log₂ n⌋+1. Проведя аналогичные рассуждения для второй стороны, получим, что её длина может принимать M=⌊log₂ m⌋+1 значений.

Для решения задачи воспользуемся идеей динамического программирования. Обозначим за a_i, i∈[1..N] длины, которые может иметь первая сторона, упорядоченные по убыванию. Аналогично для b_i.

Посчитаем следующую величину: dp[i, j] = «наименьшее время, за которое можно получить из панели n×m панель a_i×b_j». Тогда, так как a и b упорядочены по убыванию, a_N=1, b_M=1, а значит, ответ на задачу равен dp[N, M]. dp[i, j] можно посчитать по правилам:

1. dp[i, j]=∞
2. dp[i, j]=min(dp[i, j], dp[i-1, j] + ((ai-1 mod 2) • bj), если i>1
3. dp[i, j]=min(dp[i, j], dp[i, j-1] + ((bj-1 mod 2) • ai), если j>1
4. dp[1, 1]=0

Задача D. Тест
Идея: Артем Васильев
Реализация: Артем Васильев
Разбор: Артем Васильев

Условие задачи

Ограничение по времени: 2 секунды
Ограничение по памяти: 256 мегабайт

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

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

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

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

В первой строке содержится целое число n (1 ≤ n ≤ 16).

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

Выведите 2ⁿ строк. В i-й строке выведите n символов 0 или 1 — состояние каждого из флажков для i-го варианта ответа, 1 для установленного флажка и 0 для неустановленного. Количество единиц в вариантах не должно возрастать. Количество позиций, в которых различаются две соседние строки, не должно превосходить двух.

Примеры

Входные данные	Выходные данные
2	11 10 01 00

Разбор задачи

В данной задаче требовалось перечислить все строки из 0 и 1 длиной n так, чтобы выполнялись два свойства: во-первых, количество единиц не убывает, во-вторых, две соседние строки отличаются не более чем в двух позициях.

Напишем процедуру solve(n, k), которая возвращает список всех битовых строк длины n, удовлетворяющий нашему свойству. В каждой из строк ровно k единиц. Опишем рекурсивный алгоритм для solve(n, k):

1. Если k равно 0 или n, то вернем список из единственной строки 0ⁿ или 1ⁿ
2. В ином случае вызовем рекурсивно solve(n — 1, k) и solve(n — 1, k — 1)
3. Ко всем битовым строкам из первого списка припишем в конец 0, ко всем элементам из второго списка припишем в конец 1
4. Вернем конкатенацию первого списка и развернутого второго

Теперь решение заключается в том, чтобы для всех k от n до 0 вывести все битовые строки из списка solve(n, k). Докажем корректность этого решения. Рассмотрим свойства списка, который возвращает процедура solve.

1. Первый элемент списка solve(n, k) равен 1^k0^{n — k}
2. Если k > 0, то последний элемент списка solve(n, k) равен 1^{k — 1}0^{n — k}1
3. Если k = 0, то последний элемент списка solve(n, k) равен 0ⁿ

Несложно доказать все эти свойства по индукции. В итоге получаем, что процедура solve(n, k) действительно работает корректно. Осталось убедиться, что последний элемент solve(n, k + 1) и первый элемент solve(n, k) различаются не более чем в двух позициях. Последний элемент solve(n, k + 1): 1^k0^{n — k — 1}1, первый элемент solve(n, k): 1^k0^{n — k}. Легко видеть, что для этих двух строк свойство тоже выполняется. Таким образом мы получили алгоритм, который перечисляет все битовые строки длины n и удовлетворяет необходимым свойствам.

Задача E. Лазеры
Идея: Анна Малова
Реализация: Артем Васильев
Разбор: Артем Васильев

Условие задачи

Ограничение по времени: 2 секунды
Ограничение по памяти: 256 мегабайт

Ученые из Лаборатории Лазеров тестируют новый вид лазера. Для этого они используют специальный лабораторный стол, на котором имеется n точек крепления.

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

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

Ученые хотят знать, для какого минимального напряжения a можно реализовать запланированный эксперимент.

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

Первая строка содержит целое число n (2 ≤ n ≤ 150) — количество точек крепления на лабораторном столе. Следующие n строк содержат по два целых числа xi, yi — координаты i-й точки. (−20000 ≤ x_i, y_i ≤ 20000 для всех i от 1 до n, все точки различны). Первая точка соответствует лазеру, все остальные — преломителям.

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

Выведите одно вещественное число — минимальное напряжение, которое нужно подать на преломители. Абсолютная или относительная погрешность ответа не должна превосходить 10^-8.

Примеры

Входные данные	Выходные данные
4 0 0 0 1 1 1 1 0	90.0

Разбор задачи

Основная идея решения — двоичный поиск по ответу. Зафиксируем максимальный угол отклонения α и проверим существование решения с таким ответом. Для этого сведем задачу к поиску пути в графе.

Обозначим точки, заданные в условии, как P₁, P₂, ..., P_n. Построим граф из n(n — 1) вершин, где каждая вершина – это упорядоченная пара различных точек. Проведем ребра из пары (i, j) в пару (j, k) в том случае, если угол между векторами P_iP_j и P_jP_k не превосходит α. В построенном графе не более чем n³ ребер. Теперь, если в таком графе существует путь из вершины вида (1, i) в вершину вида (j, 1), то при таком α эксперимент осуществить можно. Проверять существование пути можно с помощью любого алгоритма поиска пути в графе.

Таким образом, одна итерация двоичного поиска работает за O(n³), а значит, весь алгоритм можно реализовать за O(n³ log(1/ε)) или, если заметить, что пространство поиска на самом деле дискретно (нас интересуют лишь не более чем n³ углов), то этот алгоритм можно реализовать за O(n³ log(n³)).

Задача F. Колесо
Идея: Борис Минаев
Реализация: Борис Минаев
Разбор: Борис Минаев.

Условие задачи

Ограничение по времени: 2 секунды
Ограничение по памяти: 256 мегабайт

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

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

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

Например, пусть есть три обычных города. Тогда все четыре города (три обычных и столица) попарно соединены дорогами. Тогда с вероятностью 1/8 все города захватит одна и та же партия. В этом случае максимальный размер армии равен 4. С вероятностью 3/8 два города будут захвачены одной партией и два — другой. В этом случае максимальный размер армии равен 2. Наконец, с вероятностью 1/2 в одном городе власть захватит одна партия, а в трех других — другая. В этом случае максимальный размер армии будет равен 3. Математическое ожидание ответа в этом случае 4×1/8+2×3/8+3×1/2=2.75.

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

Первая строка содержит целое положительное число t — количество тестовых примеров. Следующие t строк содержат по одному целому числу n (3 ≤ n ≤ 500) — количество обычных городов в стране. Гарантируется, что суммарное количество обычных городов во всех тестовых примерах не превышает 1000.

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

Для каждого тестового примера выведите одно число — математическое ожидание наибольшего количества взводов, которые могут оказаться в одном городе. Ответ считается правильным, если он отличается от правильного не более чем на 10^-9.

Примеры

Входные данные	Выходные данные
2 3 4	2.75 3.4375

Разбор задачи

Формализуем условие задачи. Без ограничения общности будем считать, что столицу захватила первая оппозиционная партия. Всем остальным городам сопоставим одно число. Это будет 0, если столицу и город захватила одна партия, и 1 в противном случае. Тогда всю информацию о захваченных городах можно представить в виде битовой маски длиной n. Все возможные битовые маски равновероятны. Для конкретной битовой маски ответ находится очевидным образом — максимум из (количества нулей + 1) и (максимального количества единиц, которые идут подряд в маске). При этом следует учитывать, что маска зациклена: следующий бит после последнего – первый.

Для того чтобы получить полиномиальное решение, будем использовать динамическое программирование. Его параметрами будут:

1. количество цифр в маске
2. количество нулей в маске
3. максимальное количество единиц подряд
4. текущее количество единиц подряд

Однако чтобы учитывать зацикленность маски, необходимо также хранить количество единиц, которые находятся в самом начале маски. Это решение работает за O(n⁵).

Для того чтобы избавится от последнего параметра, воспользуемся следующим соображением. Маску, которая состоит из одних единиц, обработаем отдельно. Рассмотрим все оставшиеся маски. В каждой из них есть хотя бы один ноль. Сдвинем биты маски по циклу так, чтобы на первом месте оказался первый ноль. Теперь обрежем первый бит. Сейчас некоторые маски повторяются несколько раз. Несложно заметить, что маска повторяется (количество единиц, на которые она заканчивается + 1) раз. Значит, мы можем перебирать все маски длиной n — 1, дописывать слева от маски ноль, а вероятность ее появления умножать на (количество единиц, на которые она заканчивается + 1). Заметим, что число, на которое надо умножить вероятность, мы уже храним в динамическом программировании. Избавившись от одного параметра, получаем решение за O(n⁴).

Рассмотрим, что происходит с ответом при увеличении количества городов. С очень большой вероятностью максимальной компонентой связности является компонента, в которую входит столица. А, значит, асимптотически ответ стремится к (n + 2) / 2. Несложно показать, что уже при n = 150 отклонение от асимптотического ответа составляет около 10^-12. Также можно доказать, что при увеличении n отклонение от асимптотического ответа будет только уменьшаться.

Таким образом, получаем следующее решение. С помощью динамического программирования за O(n⁴) находим ответы для первых 150 значений n. Для больших n используем формулу (n + 2) / 2.

Разбор всех задач олимпиады также доступен на сайте Russian Code Cup. Следующий этап — финал; о нем мы тоже обязательно расскажем на Хабре.

Автор: Dmitry21

Источник