ICPC 2025-2026 Northwestern Russia Regional Contest

St Petersburg, November 15, 2025

Problem A. Asynchronous Processor

Идея: Виталий Аксёнов
Разработка: Максим Туревский
Давайте для удобства добавим в начало операцию A := 0 (sync). Посмотрим, как в итоге меняется
величина A: она как-то меняется, потом происходит последняя операция присвоения, а потом к ней
что-то добавляется. Эта последняя операция присвоения — это либо последняя синхронная операция
присвоения, либо любая из асинхронных операций присвоения.
Давайте найдём все значения, которые в конце может принимать A, а в конце просто выведем их
количество.
Если мы переберём позицию p среди изначальных операций, на которую мы в итоге поставим по-
следнюю применяемую к A операцию присвоения, то мы знаем множество значений, которые мы
могли в этой операции присвоить. Теперь все операции прибавления после позиции p обязательно
должны примениться к A, а среди операций прибавления до позиции p — синхронные не применяют-
ся, а для каждой асинхронной мы можем выбрать, применять её или нет. С помощью динамического
программирования мы можем для фиксированной позиции p найти, какие суммы достижимы в та-
ком случае. Сложность решения тогда составит O(n3 v). Используя битовое сжатие (bitset), можно
3
получить решение за O( n64v ), но это всё ещё недостаточно эффективно.
Чтобы ускорить это решение, заметим следующее. Пусть последняя применяемая к A операция
присвоения — асинхронная. Будем рассматривать её возможные позиции p в порядке возрастания.
При увеличении этой позиции одна из операций прибавления переходит из состояния «после пози-
ции p» в состояние «до позиции p». Посмотрим на эту операцию и на то, как меняется множество
возможных итоговых значений A:

1. Если это операция “+ v sync”, то это значит, что раньше это прибавление входило во все суммы,
а теперь не входит ни в какие. Соответственно, все возможные суммы уменьшатся на v.

2. Если это операция “+ v async”, то раньше v входило во все суммы, а теперь у нас есть выбор
как применять эту операцию, так и не применять. Соответственно, для каждой возможной
суммы x, сумма x − v также становится возможной.

Случай, когда последняя применяемая к A операция присвоения — синхронная, обработаем отдель-

но.
Если поддерживать все допустимые значения с использованием битового множества (bitset), то это
множество имеет размер O(nv), и нужно совершить O(n) действий с ним. Все множества, получен-
ные в процессе выше, нужно объединить, чтобы получить итоговое множество. В итоге получим
2
решение за O( n64v ).

Problem B. Bounding Boxes

Идея: Георгий Корнеев
Разработка: Георгий Корнеев
Как проверить, что коробка w × h × d помещается в коробку w′ × h′ × d′ ? Отсортируем размерности
обеих коробок по неубыванию: w ≤ h ≤ d и w′ ≤ h′ ≤ d′ . Тогда первая коробка помещается во
вторую, если w ≤ w′ , h ≤ h′ и d ≤ d′ .
Из этого факта следует, что решение задачи следующее. Отсортируем по возрастанию размерности
каждой коробки: wi ≤ hi ≤ di . Тогда максимальная коробка, помещающаяся во все упаковочные
коробки, будет иметь размеры mini wi × mini hi × mini di .

Page 1 of 8
 ICPC 2025-2026 Northwestern Russia Regional Contest
St Petersburg, November 15, 2025

Problem C. Compact Encoding

Идея: Дмитрий Штукенберг
Разработка: Дмитрий Штукенберг
В задаче (если опустить подробности) требуется преобразовать значение в 128-ричную систему счис-
ления (7 битов как раз образуют одну 128-ричную цифру).
Это можно сделать стандартным образом, через печать остатков от последовательного деления на
128, но с двумя отличиями:

1. Ко всем результатам, кроме самого первого (младшие 7 бит), нужно прибавить 128.

2. Порядок байтов от старшего к младшему (“big-endian”) требует в какой-то момент развернуть

результат в обратном порядке (первый полученный остаток должен быть напечатан послед-
ним). Это можно сделать через векторы, а можно на уровне арифметики: сперва стандартным
образом вычислим длину 128-ричного представления числа, а затем будем печатать отдельные
значения в нужном порядке, тогда значение в 128-ричном разряде k будет равно ⌊ 2n7k ⌋ mod 128.

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

Problem D. Defense Distance

Идея: Артем Васильев
Разработка: Михаил Первеев
Для начала заметим, что расстояние Левенштейна является метрикой, а значит для него выпол-
няется неравенство треугольника. Поэтому, если a > b + c или b > a + c или c > a + b, построить
требуемые строки невозможно.
Во всех остальных случаях, когда неравенство треугольника выполняется, построить требуемые
строки возможно. Рассмотрим один из способов, как это можно сделать.
Для удобства будем строить строки s, t и u одинаковой длины. Разобьем каждую из трех строк
на блоки длины x, y и z. Для удобства пронумеруем эти блоки слева-направо числами от 1 до 3.
Таким образом, строки можно представить как конкатенации блоков: s = s1 + s2 + s3 , t = t1 + t2 + t3 ,
u = u1 + u2 + u3 , где |s1 | = |t1 | = |u1 | = x, |s2 | = |t2 | = |u2 | = y и |s3 | = |t3 | = |u3 | = z.
Теперь построим строки по следующим правилам:

• Строки s и t будут различаться в каждом символе блоков 1 и 2, но совпадать в каждом символе

блока 3;

• Строки s и u будут различаться в каждом символе блоков 1 и 3, но совпадать в каждом символе

блока 2;

• Строки t и u будут различаться в каждом символе блоков 2 и 3, но совпадать в каждом символе

блока 1.

Нетрудно заметить, что в таком случае dist(s, t) = x + y, dist(s, u) = x + z и dist(t, u) = y + z, где

dist — расстояние Левенштейна.
Таким образом, осталось выбрать числа x, y и z таким образом, чтобы получились требуемые рас-
стояния между строками. Для этого нужно решить систему из трех уравнений:

x + y = a

x+z =b (1)

y+z =c


Page 2 of 8
 ICPC 2025-2026 Northwestern Russia Regional Contest
St Petersburg, November 15, 2025

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

a+b−c


x=


 2
a+c−b

y= (2)

 2
z = b + c − a



2
Если сумма a + b + c четна, то x, y и z получатся целыми. В этом случае можно построить строки
следующим образом: s = ax by bz , t = bx ay bz , u = bx by az , где a и b — произвольные различные
символы, а запись cp означает строку, равную символу c, повторенному p раз.
Теперь рассмотрим случай, когда сумма a+b+c нечетна. В этом случае построим аналогичную кон-
струкцию, округлив x, y и z вниз. Заметим, что теперь каждое из трех расстояний Левенштейна на
1 меньше, чем требуемое. Исправим это, дописав в конец каждой строки произвольный уникальный
символ.
Также нужно не забыть о том, что строки должны быть непустыми, а x, y и z могут получиться
равными нулю при a = b = c = 0. В этом случае достаточно вывести произвольные три непустые
равные строки.

Problem E. Eight-Connected Figures

Идея: Захар Яковлев
Разработка: Захар Яковлев
Отметим, что максимальные ограничения в задаче t = 50, n = 300, а ограничение на количество
запросов 30 000, то есть ровно 2nt.
Первая идея, которая приходит в голову — поддерживать связную область одного цвета, но то-
гда только среднее число запросов будет 2nt, а разброс значений приведет к превышению числа
запросов.
Правильное решение — поддерживать одновременно связные области белого и черного цвета. При
этом нужно делать запросы в клетки, соседние с обеими областями. Тогда область нужного размера
получится меньше, чем за 2n запросов.
Отдельно надо аккуратно обработать специальные случаи: одна область может оказаться полно-
стью окруженной другой. В этом случае необходимо «выкинуть» внутреннюю область и начать
строить заново область такого цвета снаружи. За счет множественных тестов неудача в одном тесте
компенсируется запасом в других. Так, вероятность ошибки в авторском решении меньше 10−40 .
Также бывают особые случаи, когда у каждой из областей есть соседи, но нет общих соседей:
.......
.WWWWW.
.WBBBW.
.[Link].
.WBBBW.
.WWWWW.
.......
Но такие случаи крайне маловероятны и на практике практически не встречаются. Также можно
менять стартовую точку для обхода таких случаев.

Page 3 of 8
 ICPC 2025-2026 Northwestern Russia Regional Contest
St Petersburg, November 15, 2025

Problem F. Faulty Fraction

Идея: Николай Дубчук
Разработка: Николай Будин
Вам дана строка из цифр s и целое число c. Известно, что существуют два целых положительных
числа a и b, такие что a ÷ b = c и concat(a, b) = s. Требуется найти любые подходящие a и b.
Обозначим за l(x) длину числа x. Тогда 10l(x)−1 ≤ x < 10l(x) .

(
10l(b)−1 ≤ b < 10l(b)
=⇒
10l(c)−1 ≤ c < 10l(c)

=⇒ 10l(b)+l(c)−2 ≤ b · c < 10l(b)+l(c) =⇒

=⇒ l(b) + l(c) − 1 ≤ l(b · c) ≤ l(b) + l(c);

a ÷ b = c =⇒ a = b · c =⇒ l(a) = l(b · c) =⇒

=⇒ l(b) + l(c) − 1 ≤ l(a) ≤ l(b) + l(c) =⇒

=⇒ (l(s) − l(a)) + l(c) − 1 ≤ l(a) ≤ (l(s) − l(a)) + l(c) =⇒

=⇒ l(s) + l(c) − 1 ≤ 2 · l(a) ≤ l(s) + l(c)

Заметим, что 2 · l(a) — четное, поэтому оно может быть равно только одному из двух последова-
тельных значений l(s) + l(c) − 1 и l(s) + l(c). Таким образом, l(a) = ⌊ l(s)+l(c)
2 ⌋. Решение единственно.
А раз нам гарантируется, что такие a и b должны существовать, это именно они.

Problem G. Games of Chess

Идея: Фёдор Ушаков
Разработка: Фёдор Ушаков
Рассмотрим задачу в терминах теории графов. Нам дан неориентированный связный граф, и нужно
раскрасить его вершины в некоторое число цветов так, чтобы для каждой вершины u число вершин
v того же цвета, соединённых с u ребром, было нечётным.
При нечётном n ответа не существует. Действительно, предположим обратное: пусть существует
какая-то допустимая раскраска. Оставим в графе только те рёбра, концы которых имеют одина-
ковый цвет. После этой операции у каждой вершины степень нечётна, и так как вершин нечётное
число, сумма степеней всех вершин нечётна. А в неориентированном графе сумма степеней всех
вершин должна быть чётной, так как каждое ребро прибавляет к этой сумме 2. Противоречие.
Для чётного n ответ всегда существует, и его можно найти с помощью следующего алгоритма:

1. Построим дерево обхода в глубину (DFS).

2. Повторяем, пока есть вершины:
• Возьмём самый глубокий лист v. Посмотрим на его родителя u. У u есть k детей, все они
— листья.
• Если k нечётно, то покрасим поддерево u в один цвет и отрежем от остального дерева.
• Если k чётно, но есть хотя бы один лист, из которого есть хотя бы одно обратное ребро,
ведущее наверх в некоторого предка вершины u, то этот лист переподвесим к ближайшей
вершине, в которую из него есть ребро, а остальную часть поддерева отрежем так же, как
в предыдущем пункте.

Page 4 of 8
 ICPC 2025-2026 Northwestern Russia Regional Contest
St Petersburg, November 15, 2025

• Если k чётно, но рёбер наверх из листьев нет, то отрежем все эти листья и пометим, что
их в конце надо будет покрасить так же, как вершину u, а саму вершину u оставим в
дереве.

Можно показать, что раскраска графа по данному алгоритму является корректной. При аккуратной
реализации сложность этого решения составит O(n + m).

Problem H. High Score

Идея: Дмитрий Якутов
Разработка: Дмитрий Якутов
Посмотрим на состояние игры в произвольный момент времени. Пусть в мультисете в данный мо-
мент есть число a = 2t . Сколько очков получил игрок за создание этого числа с нуля? Если a = 2,
то игрок не получил очков. Иначе рассмотрим все числа, которые игрок добавлял в мультисет с
помощью операции Insert, которые внесли вклад в текущее число a:

• Если при операциях Insert игрок добавлял только числа со значением 2, то игрок получил
Q(t) = (t − 1) · 2t очков: при операциях Merge с x = 2 игрок суммарно получил 2t очков, с
x = 4 – тоже 2t очков, . . . , с x = a – тоже 2t очков;
• Аналогично, если при операциях Insert игрок добавлял только числа 4, то игрок суммарно
получил P (t) = (t − 2) · 2t очков;
• Если часть операций Insert выполнялась со значением 2, а остальные – со значением 4, то
игрок мог получить любое значение от P (t) до Q(t) с шагом 4 очка.

Из рассуждений выше есть одно исключение: если t = k + 1, то есть речь идет о максимальном
возможном значении числа в мультисете. В этом случае невозможно получить это число, добавляя
только 2 при Insert, так как для этого в какой-то момент на доске должны быть числа: 2, 2, 4, . . . 2k ,
то есть k + 1 число. Максимальное возможное число очков, полученное при создании 2k+1 – это
R(t) = Q(t) − 4 = (t − 1) · 2t − 4 очка.
Приведем алгоритм, с помощью которого можно брать любое число очков от 0 до
k+1
R(t), методом математической индукции по значению k.
P
M axScore(k) =
t=2
3
Если k = 2, то максимальный возможный счет ((t − 1) · 2t − 4) = (1 · 4 − 4) + (2 · 8 − 4) = 0 + 12 = 12.
P
t=2
Способ набрать 12 очков проиллюстрирован в пояснении к сэмплу.
При k ≥ 3. Пусть мы хотим набрать ровно h очков, где h mod 4 = 0:

• Если 4 ≤ h ≤ M axScore(k − 1), то наберем нужные очки, воспользовавшись индукционным

предположением. Кол-во чисел в мультисете в любой момент времени не будет превышать
k − 1, что нам подходит;
• Если M axScore(k − 1) + 4 ≤ h ≤ M axScore(k − 1) + Q(k), то сначала сделаем так, в муль-
тисете было только одно число 2k , набрав максимальный возможный для этого числа счет
Q(k) = (k − 1) · 2k при создании этого числа, а затем доберем оставшиеся очки, используя не
более k − 1 слотов в мультисете. Это можно сделать, так как M axScore(k − 1) + 4 ≥ Q(k);
• Если M axScore(k − 1) + Q(k) + 4 ≤ h ≤ M axScore(k − 1) + P (k + 1), то сначала сделаем число
2k+1 , набрав счет P (k +1), а затем доберем оставшиеся очки, воспользовавшись индукционным
предположением. Это мы можем сделать, так как M axScore(k − 1) + Q(k) + 4 ≥ P (k + 1).
• Если M axScore(k − 1) + P (k + 1) ≤ h ≤ M axScore(k − 1) + R(k + 1) = M axScore(k), то сначала
сделаем число 2k+1 , набрав ровно h1 = h − M axScore(k − 1) очков, а затем доберем оставшиеся
M axScore(k − 1) очков. Это мы можем сделать, так как P (k + 1) ≤ h1 ≤ R(k + 1).

Page 5 of 8
 ICPC 2025-2026 Northwestern Russia Regional Contest
St Petersburg, November 15, 2025

Таким образом мы можем набрать любое число очков от 0 до M axScore(k) с шагом 4 очка.
На практике следующий жадный алгоритм приводит к тому же результату. Пока мы не набрали
нужное число очков, будем находить максимальное t такое, что P (t) не превосходит оставшегося
числа очков, и создавать 2t , вычитая максимальное возможное число очков, правильно выбирая
между Q(t) и R(t).

Problem I. Infection Investigation

Идея: Фёдор Ушаков
Разработка: Леонид Данилевич
Будем отвечать на запросы оффлайн, применив принцип «разделяй и властвуй». А именно, напишем
рекурсивную функцию, принимающую 1 ≤ lf ≤ rg ≤ n, и получающую ответы для запросов (l, r) при
условии lf ≤ l ≤ r ≤ rg. Пусть m = ⌊ lf+rg
2 ⌋, тогда функция отвечает на запросы (l, r), не содержащие
m, рекурсивно. Осталось разобраться с запросами (l, r), такими, что lf ≤ l ≤ m ≤ r ≤ rg.
Для этого насчитаем стандартными методами (при помощи двоичного поиска или дерева отрез-
ков / дерева Фенвика) длины наибольшей возрастающей подпоследовательности на префиксах
[am , . . . , arg ] и суффиксах [alf , . . . , am−1 ]. Пусть отрезок (al , . . . , ar ) бьётся на два, и длины возраста-
ющей подпоследовательности в этих частях равны x, y ≥ 1. Ясно, что в таком случае ответ на этот
запрос заключён в отрезке [max(x, y), x + y]. Если x = y = 1, то необходимо проверить, является
ли подмассив al , . . . , ar строго убывающим, а во всех остальных случаях ⌊ max(x,y)+(x+y) 2 ⌋ является
достаточно хорошим приближением.
В самом деле, с одной стороны ⌊ max(x,y)+(x+y)
2 ⌋ ≤ max(x,y)+(x+y)
2 ≤ 32 max(x, y), а с другой стороны
при max(x, y) ≥ 3: ⌊ max(x,y)+(x+y)
2 ⌋ ≥ max(x,y)+(x+y)−1
2 ≥ 32 (x + y); перебор случаев показывает, что
при max(x, y) = 2 тоже ⌊ max(x,y)+(x+y)
2 ⌋ ≥ 23 (x + y).
Итого асимптотика высчитывается по формуле T (n) = 2T (n/2) + O(n log n), откуда алгоритм рабо-
тает за O(n log2 n).

Problem J. Judging Problem

Идея: Захар Яковлев, Геннадий Короткевич
Разработка: Никита Голиков
Рассмотрим две задачи, выбранные в годы i и i + 1. Если их названия похожи, то при выборе
названия в год i + 1 правило было выполнено.
В противном случае необходимо проверить, что на суффиксе, начинающемся с i + 1, нет задач, по-
хожих на i-ю. Для этого пройдем по задачам в обратном порядке, начиная с n-й. Во время итерации
мы будем хранить два множества слов: одно множество будет хранить все использованные первые
слова в суффиксе, а другое — все использованные вторые слова.
При проверке задачи i + 1, если названия i-й и (i + 1)-й не были похожи, мы проверим, содержит
ли какое-либо из множеств соответствующее слово из i-го названия. Если какое-либо из множеств
содержит это слово, это означает, что правило не было соблюдено в год i + 1.
Если все проверки прошли успешно, это означает, что судьи правильно следовали правилу. Время
работы решения O(n) или O(n log n), в зависимости от реализации используемой структуры данных
множества.

Problem K. Keys and Grates

Идея: Михаил Иванов
Разработка: Михаил Иванов
Не умаляя общности, пусть h > s. Давайте представим себе оптимальный маршрут Китнисс, как
он будет выглядеть? Китнисс будет чередовать хождение налево и хождение направо. Понятно, что
если она добралась до какой-то точки в конце хождения налево, то следующее хождение налево

Page 6 of 8
 ICPC 2025-2026 Northwestern Russia Regional Contest
St Petersburg, November 15, 2025

должно закончиться строго дальше. В самом деле, зачем иначе Китнисс потребовалось идти нале-
во? Если затем, чтобы подобрать ключ или выйти в люк, то она могла это же сделать и во время
предыдущего хождения. А других причин быть и не могло — вскрывать замки на этом отрезке
Китнисс не могла, они и так все были вскрыты ранее. Кроме того, понятно, что самое последнее
хождение закончится в h, и это будет хождение направо, иначе Китнисс могла покинуть тоннель
раньше. Формально, Китнисс выберет некоторый отрезок тоннеля [L; R], содержащий и h, и s, вы-
берет в нём несколько точек Lm , Rm , Lm−1 , Rm−1 , Lm−2 , Rm−2 , . . . , L0 , R0 и в этом порядке посе-
тит их, по пути открывая все замки и подбирая все ключи от замков из отрезка [L; R]. При этом
L = L0 < L1 < . . . < Lm ≤ s ≤ Rm < Rm−1 < Rm−2 < . . . < R0 = R = h.
Теперь остаётся лишь выбрать эти отрезки и эти точки. Давайте постепенно это делать с конца. R0
выбрать легко: это просто h. Как теперь выбрать L0 ? Для того, чтобы добраться до R0 , Китнисс
надо иметь на руках все ключи от замков из отрезка [s; R0 ]. Рассмотрим все из этих ключей, которые
находятся левее s, выберем самый левый такой ключ — его-то положение и будет точкой L0 . Далее
аналогично: чтобы добраться до L0 , надо, чтобы все замки в [L0 ; s], ключи от которых правее s,
можно было открыть; значит, в качестве R1 надо взять самый правый ключ, открывающий замок
из [L0 ; s]. Продолжаем так делать, пока не окажется, что на очередном отрезке вообще нет замков,
требующих ключей с другой половины тоннеля; тогда мы просто объявляем, что этот очередной
отрезок и будет первым отрезком, который мы будем проходить.
Может оказаться, что такого момента никогда не настанет. Это окажется так, если мы обнаружим
для какого-то j, что Lj ≥ Lj+1 или Rj ≤ Rj+1 — это точно значит, что есть циклическая зави-
симость. А именно, давайте про пару из замка и люка/ключа (возможно, открывающего другой
замок) будем говорить, что замок запирает этот люк/ключ, если замок находится между данным
люком/ключом и s. Тогда понятно, что Китнисс не сможет подобрать ключ до того, как откроет
все замки, запирающие этот ключ, и не сможет выйти в люк, пока не откроет все замки, запираю-
щие люк. Неравенство вроде Rj ≤ Rj+1 гарантированно означает, что есть пара i, j, что i-й замок
запирает j-й ключ, а j-й замок запирает i-й ключ, и при этом один из замков запирает люк. Тогда
Китнисс не сможет открыть ни один из замков, не вскрыв сначала другой — это мы и назвали ранее
циклической зависимостью. А, поскольку без вскрытия одного из этих замков Китнисс не добраться
до люка, то задача в этом случае неразрешима. Также заметим, что если хоть один нужный нам
замок запирает свой собственный ключ, то задачу тоже не решить.
Такое решение работает за O(n log n): сортируем все замки, потом для каждого ключа находим
ближайший к нему замок, который запирает этот ключ (или флаг, что ключ не заперт никаким
замком). Дальше для замков справа от s построим массив префиксных минимумов координат нуж-
ных для них ключей, а для замков слева от s — массив суффиксных максимумов координат нужных
для них ключей. Теперь, как описывалось ранее, построим L0 и R0 , переберём все замки на [L0 ; R0 ]
и проверим, что никакой из них не запирает свой собственный ключ. Наконец, построим R1 , L1 , . . .,
проверяя каждый раз, что не нарушается строгая монотонность Li и Ri . Чтобы, скажем, зная Ri ,
найти Li , найдём gj — ближайший к Ri замок, запирающий Ri (в точке Ri всегда будет либо люк,
либо ключ). Если gj не существует, то процесс окончен, Китнисс может беспрепятственно идти от
s к Ri . Если gj существует и правее s, то мы находим в массиве префиксных минимумов самый
левый ключ kq , требующийся для вскрытия всех замков в [s; gj ]. Если kq ≥ s, то опять же Китнисс
может просто идти к Ri , и все нужные для этого ключи будут лежать у неё на пути — другими
словами, процесс построения последовательностей Li , Ri окончен. В противном случае мы говорим,
что Li = kq , и продолжаем процесс.
Наконец, чтобы найти ответ, вычислим (s − Lm ) + m
Pm−1
i=0 (Ri − Li+1 ) — длину пути
P
i=0 (Ri − Li ) +
Китнисс.

Page 7 of 8
 ICPC 2025-2026 Northwestern Russia Regional Contest
St Petersburg, November 15, 2025

Problem L. Lucky Number Theory

Идея: Артем Васильев
Разработка: Артем Васильев
Начнем решать задачу со случая d = 1. Заметим, что стратегия зависит только от дробной части S
(обозначается {S}): все действия для S и S + 1 можно делать одинаково, и результат всегда будет
отличаться на единицу.
Важное наблюдение: вне зависимости от текущего распределения S, после броска, новое значение
{S ′ } будет иметь равномерное распределение от 0 до 1.
Благодаря этому наблюдению, мы можем предполагать, что на каждом шаге значение {S} равномер-
но распределено от 0 до 1, что позволяет использовать динамическое программирование. Обозначим
за fn,k матожидание оптимальной стратегии, если осталось n бросков, k возможностей вывести, в
предположении, что в начале {S} распределено равномерно от 0 до 1.
Обозначим {S} = x. В зависимости от x, есть два случая: бросить еще раз, либо вывести билеты и
бросить еще раз. В первом случае матожидание числа билетов равно x + fn−1,k : вероятность того,
что после броска целая часть S увеличится, равна S, и мы переходим в состояние с n − 1 броском.
Во втором случае матожидание равно 1 + fn−1,k−1 : мы гарантированно получаем один билет сейчас,
и переходим в состояние (n − 1, k − 1). Все переходы корректны из-за наблюдения выше: несмотря
на то, что мы используем x для принятия решения, после броска, {S} все еще будет распределено
равномерно от 0 до 1.
Так как x распределено равномерно от 0 до 1, нужно взять максимум из двух случаев, и проин-
R1
тегрировать по x от 0 до 1: fn,k = max(x + fn−1,k , 1 + fn−1,k−1 )dx. Если обозначить A = fn−1,k ,
0
B = 1 + fn−1,k−1 , то для x ≥ B − A максимум достигается в первом случае, а для x < B − A — во
втором. Опустив промежуточные вычисления, получаем формулу для ДП: fn,k = A + 12 + 21 (B − A)2 ,
которую можно вычислить за O(n2 ) сразу для всех возможных пар (n, k). Итоговый ответ на задачу
равен fn−1,k−1 + 1, учитывая первый бросок и последний вывод, который дает +1 к ответу.
Наконец, случай d > 1. Заметим, что сгенерировать случайное вещественное число в интервале (0, d)
это то же самое, что сгенерировать случайное вещественное число от 0 до 1, а заметим прибавить слу-
чайное целое число от 0 до d−1 включительно. Добавление случайного целого числа никак не влияет
на стратегию, только на ответ: на каждый бросок в среднем прибавится d1 (0 + 1 + . . . + d − 1) = d−1
2
билетов. Ответ на задачу равен решению для d = 1 плюс d−1 2 n.

Page 8 of 8