Всем Привет!↵
↵
↵
↵
Меня зовут Максим и я очень давно хочу достичь рейтинга 3000. Я верю, что для этого мне надо научиться мыслить, как человек, у которого уже есть 3000 рейтинга. Очень часто в разборах пишут фразы "заметим, что..." или "докажем вот такой факт..." и дальше идет долгое доказательство этого факта. А то, каким образом я должен к этому факту прийти, как эта мысль должна зародиться у меня в голове, никто нигде не пишет. Я думаю, что не только у меня есть эта проблема, поэтому вместо того, чтобы ждать понятный разбор, я решил начать с себя. Именно поэтому, я решил написать свой первый пошаговый разбор, где я буду описывать ход своих мыслей и действий, которые позволяют мне придумать эти самые идеи.↵
↵
Также, я создал группу по прокачке навыков спортивного программирования для людей с рейтингом 1200- , чтобы помочь им стать лучше и достигнуть рейтинга 1500+. Если хотите больше об этом узнать, рекомендую прочитать [ЭТОТ ПОСТ](https://mirror.codeforces.com/blog/entry/153213) или заполнить [ФОРМУ](https://forms.yandex.ru/u/69ea4ba0493639794fd019d8). Эту группу я назвал **Polaris** в честь путеводной звезды. В Polaris ребята решают специально подобранные контесты под их уровень, дорешивают их с помощью пошаговых разборов, изучают новую теорию, решают специально подготовленные для них подводящие упражения, а также получают подробные рекомендации на основе их участия в тренировочных контестах. Более того, специально для участников группы я делаю пошаговые разборы тех задач, которые интересны самим участникам. Также, в группе регулярно ведется обсуждение прошедших контестов, а в ближайшем будущем мы будем готовиться к предстоящим олимпиадам (как школьным, так и студенческим). Присоединяйтесь, я буду вам очень рад!↵
↵
А теперь перейдем к самому разбору контеста. Но перед этим, я бы хотел ввести несколько правил чтения разбора для того, чтобы вы смогли получить максимум пользы от него.↵
↵
1. Перед чтением разбора задачи, убедитесь, что вы прочитали задачу, подумали над ней, извлекли из свой головы и записали/нарисовали максимальное количество идей и больше уже ниечго не можете придумать.↵
2. Во время чтения разбора, если в какой-то момент, какое-то предложение в разборе навело вас на новую мысль, перестаньте читать разбор и вернитесь к пункту (1), а именно продолжите с этого места генерровать новые идеи. Это очень важно.↵
3. Если вы дочитали текст разбора до конца и не поняли, как решать задачу или остались вопросы, то их нужно обязательно задать в комментариях или спросить в Polaris. Там вам помогут я и ребята, кто справился с этой задачей. Также в этом случае, полезно прочитать код, который будет прикреплен в разбору.↵
4. После того, как вы решили задачу, обязательно посмотрите код других участников и код с разбора. Возможно, он наведет вас на мысль о том, как можно было проще и быстрее реализовать решение задачи.↵
↵
A. Сходимость↵
===================↵
↵
<spoiler summary="Шаг 1">↵
Первое, на что я обратил внимание, что финальная позиция — это одна из позиций в исходном маасиве. Почему? Потому, что если это не так, и финальная позиция оказалась в точке $x$, тогда мы можем ее подвинуть в ближайшую точку в массиве $a_i$.↵
</spoiler>↵
↵
<spoiler summary="Шаг 2">↵
Следующее, на что я обратил внимание -- это ограничения задачи, они позволяют перебрать точку $x=a_j$ и посчитать для нее ответ.↵
</spoiler>↵
↵
<spoiler summary="Шаг 3">↵
Как посчитать ответ. Два человека идут к точке между ними, значит нам нужно разделить всех людей на три группы, какие?↵
</spoiler>↵
↵
<spoiler summary="Шаг 4">↵
1. $a_i=x$, пусть их $M$↵
2. $a_i<x$, пусть их $L$↵
3. $a_i>x$, пусть их $R$↵
Тогда как посчитать ответ?↵
</spoiler>↵
↵
<spoiler summary="Шаг 5">↵
Нам не нужно учитывать людей из первой группы, т.к. они уже стоят в финальной точке. Как подвинуть остальных людей? Каким парам людей не имеет смысла звонить?↵
</spoiler>↵
↵
<spoiler summary="Шаг 6">↵
Тем парам людей, которые находятся в одной группе. Еще если мы позвоним людям из разных групп, то мы всегда можем назначить точку $x$. Тогда чему равен ответ?↵
</spoiler>↵
↵
<spoiler summary="Шаг 7">↵
Ответ равен $\max(L, R)$↵
</spoiler>↵
↵
Решение: [submission:376629392]↵
↵
B. Выравнивание тортика↵
===================↵
↵
<spoiler summary="Шаг 1">↵
Пусть мы знаем ответ $h$ для префикса $0\ldots i$. Как нам проверить, правильный ли он или нет? Какие есть условия?↵
</spoiler>↵
↵
<spoiler summary="Шаг 2">↵
Самое простое условие -- это $a_0 \ge h$, тогда мы можем к себе в запас положить $a_0-h$ лишней глазури. Какое будет условие для $a_1$?↵
</spoiler>↵
↵
<spoiler summary="Шаг 3">↵
Условие такое: $a_1 + (a_0-h) \ge h$. Так как мы можем сложить глазурь $a_1$ и остатки глазури с прошлого шага $a_0-h$. Перепишем это условие: (a_0+a_1) \ge 2h. Тогда у нас останется $(a_0+a_1)-2h$ лишней глазури. Тогда какое условие в общем виде для префикса $i$?↵
</spoiler>↵
↵
<spoiler summary="Шаг 4">↵
Такое: $a_0+a_1+\ldots+a_i\ge (i+1)h$. Тогда получается, что $h \le \frac{A_i}{i+1}$, где $A_i$ — префиксная сумма массива $a: A_i=A_{i-1}+a_i$.↵
</spoiler>↵
↵
Решение: [submission:376640529]↵
↵
C1. Рассадка за столами (простая версия)↵
===================↵
↵
<spoiler summary="Шаг 1">↵
Первое, на что я обратил внимание -- это ограничения задачи, которые позволяют ее решать за, например, $O(n^2)$. То есть мы можем что-то перебрать, а потом при фиксированном чем-то можем сделать еще что-нибудь за $O(n)$. Какую простую версию задачи можно решить?↵
</spoiler>↵
↵
<spoiler summary="Шаг 2">↵
Представим, что у нас нет людей типа A, тогда есть только I и E. Тогда как решить такую подзадачу?↵
</spoiler>↵
↵
<spoiler summary="Шаг 3">↵
Чтобы решить эту подзадачу, мы должны просто идти слева направо по строке. Если встретили I, то сажаем его за новый столик (если столики остались), а если E — то сажаем его за неполный столик с хотя бы одним человек (если такой есть).↵
Хорошо, теперь вернем A. По сути, A — это либо I, либо E. Пусть мы знаем, сколько из A людей перекрасятся в I, тогда как нам выгодно их красить?↵
</spoiler>↵
↵
<spoiler summary="Шаг 4">↵
Нам выгодно перекрашивать некоторый префикс людей типа A в тип I, потому что мы хотим, чтобы на момент рассмторения I было как можно больше свободных столов, а на момент рассмотрения E, было как можно больше непустых столов. Тогда как решать всю задачу?↵
</spoiler>↵
↵
<spoiler summary="Шаг 5">↵
Перебираем, сколько людей типа A мы перекрасим в тип I (остальные будут перекрашены в тип E), перекрашиваем, проверяем за линию. Итого $O(n^2)$.↵
</spoiler>↵
↵
Решение: [submission:376663490]↵
↵
C2. Рассадка за столами (сложная версия)↵
===================↵
↵
<spoiler summary="Шаг 1">↵
Попробуем решить жадно. Основная проблема — как работать с A. Пусть мы встретили A. Что мы можем с ним сделать?↵
</spoiler>↵
↵
<spoiler summary="Шаг 2">↵
Мы можем посадить его за пустой столик, но тогда мы заблокируем место для одного из будущих I. А если посадим его за непустой столик? Тогда мы займем место для какого-то из E. Можем ли мы как-то исправить ситуацию для I? Непонятно. А для E?↵
</spoiler>↵
↵
<spoiler summary="Шаг 3">↵
Мы можем попытаться пересадить E, который был посажен за непустой столик за новый столик, а затем посадить E. Отлично, тогда давайте хранить количество пустых столов, количество мест за непустыми столами, а также количество A, которые мы посадили за непустые столы (именно их мы можем пересаживать за пустые столы). Если встретили E или I, то решаем как обычно, а если A, то сначала пытаемся посадить его за непустой стол, а если не получилось, то пытаемся посавдить за пустой стол.↵
</spoiler>↵
↵
Решение: [submission:376859618 ]↵
↵
D. Магический многоярусный тортик↵
===================↵
↵
<spoiler summary="Шаг 1">↵
Первое, на что я обратил внимание, что если все $a_i=0$, то это задача о Ханойских Башнях. Обычно, в подобных задачах, ее решают так: рекурсивно переносят первые $(n-1)$ слоев из первого места во второе, затем переносят $n$-й слой из первого слоя в третий, а потом оставшиеся $(n-1)$ слоев переносят из второго места в третье. Но здесь бывают случаи, когда $a_i > 0$. Какой есть простой случай, когда ответа нет?↵
</spoiler>↵
↵
<spoiler summary="Шаг 2">↵
Когда есть $a_i>i$ (в 0-индексации), тогда ответа нет, потому что мы не сможем никогда переместить этот слой никуда, потому что максимальное количество слоев над ним не может быть больше $i$. Хорошо, осталось рассмотреть случай, когда $a_i \le i$. Можем ли мы по аналогии с Ханойскими башнями решить задачу?↵
</spoiler>↵
↵
<spoiler summary="Шаг 3">↵
Пусть $k=a_{n-1} < n$, тогда чтобы переместить последний слой, нам надо сделать так, чтобы над ним было ровно $k$ слоев. Что мы можем сделать?↵
</spoiler>↵
↵
<spoiler summary="Шаг 4">↵
Мы можем переместить $n-1-k$ первых слоев с первого места на второе. После этого на первом месте будет ровно $(k+1)$ слой, тогда мы можем переместить последний слой из первого места в третье. А что теперь?↵
</spoiler>↵
↵
<spoiler summary="Шаг 5">↵
Если $k=0$, то по аналогии с Ханойскими башнями осталось переместить оставшиеся $(n-1)$ слоев из второго места в третье. А если $k>0$? В таком случае, у нас есть три места, в каждом из которых есть сколько-то слоев. Причем, во втором месте лежат самые маленькие слои.↵
</spoiler>↵
↵
<spoiler summary="Шаг 3">↵
Мы можем попытаться переместить либо слои из первого места в третье, либо из второго места в первое. Можем ли мы сделать первый вариант? Не всегда. А второй вариант? Да, можем, тогда в конце нам останется опять переместить $(n-1)$ слой из первого места в третье. Сколько тогда мы сделаем операций?↵
</spoiler>↵
↵
<spoiler summary="Шаг 4">↵
Если $F(n)$ — количество операций при перемещении префикса длины $n$, тогда $F(1)=1$, а чему равно $F(n)$?↵
</spoiler>↵
↵
<spoiler summary="Шаг 5">↵
$F(n) = F(n-1-k) + 1 + F(n-1-k) + F(n-1) = 2F(n-1-k)+F(n-1)+1$, причем, если $k=0$, то $F(n)=F(n-1)+1+F(n-1)=2F(n-1)+1$. Верно ли, что $F(n) < 2^n$?↵
</spoiler>↵
↵
<spoiler summary="Шаг 6">↵
Да, верно, потому что $F(1)=1<2^1=2$. Далее, если $k=0$, то $F(n)=2F(n-1)+1\le 2\cdot(2^{n-1}-1)+1=2^n-2<2^n$. И если $k>0$, то $F(n)=2F(n-1-k)+F(n-1)+1\le 2\cdot (2^{n-1-k}-1)+2^{n-1}-1+1 \le 2\cdot (2^{n-2}-1)+2^{n-1}=2^n-2<2^n$↵
</spoiler>↵
↵
Решение: [submission:376860585]↵
↵
↵
E. Змеиное расположение↵
===================↵
↵
<spoiler summary="Шаг 1">↵
Посмотрим на самую длинную змею. Как она выглядит? Где начинается и где заканчивается?↵
</spoiler>↵
↵
<spoiler summary="Шаг 2">↵
Она начинается в самом верхнем левом углу и заканчивается в самом правом нижнем углу. Если это не так, то ее никак не уместить в поле $n\times n$.↵
</spoiler>↵
↵
<spoiler summary="Шаг 3">↵
Дальше, я смотрю на антидиагонали:↵
↵
↵
~~~~~↵
01234↵
12345↵
23456↵
34567↵
45678↵
~~~~~↵
↵
Здесь каждой цифрой обозначены диагонали. Сколько раз один путь вправо-вниз может проходить по одной диагонали?↵
↵
</spoiler>↵
↵
<spoiler summary="Шаг 4">↵
По каждой диагонали не более одного раза. Хорошо, раз мы знаем где начинается и где заканчивается самый длинный путь, то пойдем дальше, а именно расмотрим диагональ $1$. Что мы про нее знаем?↵
</spoiler>↵
↵
<spoiler summary="Шаг 5">↵
Мы знаем, что одна из клеток принадлежит самой длинной змее длины $2n-1$, а что мы можем сказать про вторую клетку?↵
</spoiler>↵
↵
<spoiler summary="Шаг 6">↵
Она принадлежит змее длины $2n-3$, потому что если нет, то мы не сможет расположить эту змею нигде больше. То есть мы нашли старт змеи $(2n-3)$, а где ее конец?↵
</spoiler>↵
↵
<spoiler summary="Шаг 7">↵
Ее конец где-то в предпоследней диагонали. Обозначим $X$ — змея длины $2n-1$, а $Y$ — змея длины $2n-3$, пусть мы знаем, что например картинка выглядит примерно так:↵
↵
↵
~~~~~↵
XX....↵
Y.....↵
.....?↵
....?X↵
~~~~~↵
↵
Тогда как может выглядеть правый нижний угол?↵
↵
</spoiler>↵
↵
<spoiler summary="Шаг 8">↵
Он может выглядеть только так:↵
↵
↵
~~~~~↵
XX....↵
Y.....↵
.....X↵
....YX↵
~~~~~↵
↵
Потому что иначе две змеи пересекутся.↵
↵
</spoiler>↵
↵
<spoiler summary="Шаг 9">↵
Продолжим процесс. Допустим, мы знаем про каждую клетку диагонали $i$, каким змеям они принадлежат. Тогда мы знаем, каким змеям принадлежат клетки симметричной диагонали (они там симметричны). Тогда мы по сути хотим итеративно найти стартовые клетки всех змеи. Они однозначно зададут все пути. Почему?↵
</spoiler>↵
↵
<spoiler summary="Шаг 10">↵
Мы все знаем про диагональ $i$ (в 0-индексации), а именно знаем про каждую из $(i+1)$ клеток, какой змее они принадлежат. Мы хотим понять это для диагонали $(i+1)$. Во-первых, мы должны продолжить каждый из $(i+1)$ путей либо вниз, либо вправо. Причем некоторый префикс путей мы можем продолжить вниз, а оставшийся суффикс — вправо. Тогда останется ровно одна клетка, которую займет новая змея.↵
</spoiler>↵
↵
<spoiler summary="Шаг 11">↵
Тогда на каждой диагонали мы хотим найти отрезок клеток, где мы можем начать новую змею исходя из уже нарисованных путей. Пусть на диагонали $i$ отрезок имеет длину $L_i$, тогда ответ равен $L_0\cdot L_1\cdot \ldots \cdot L_{n-1}$.↵
</spoiler>↵
↵
Решение: [submission:376863113]
↵
↵
↵
Меня зовут Максим и я очень давно хочу достичь рейтинга 3000. Я верю, что для этого мне надо научиться мыслить, как человек, у которого уже есть 3000 рейтинга. Очень часто в разборах пишут фразы "заметим, что..." или "докажем вот такой факт..." и дальше идет долгое доказательство этого факта. А то, каким образом я должен к этому факту прийти, как эта мысль должна зародиться у меня в голове, никто нигде не пишет. Я думаю, что не только у меня есть эта проблема, поэтому вместо того, чтобы ждать понятный разбор, я решил начать с себя. Именно поэтому, я решил написать свой первый пошаговый разбор, где я буду описывать ход своих мыслей и действий, которые позволяют мне придумать эти самые идеи.↵
↵
Также, я создал группу по прокачке навыков спортивного программирования для людей с рейтингом 1200- , чтобы помочь им стать лучше и достигнуть рейтинга 1500+. Если хотите больше об этом узнать, рекомендую прочитать [ЭТОТ ПОСТ](https://mirror.codeforces.com/blog/entry/153213) или заполнить [ФОРМУ](https://forms.yandex.ru/u/69ea4ba0493639794fd019d8). Эту группу я назвал **Polaris** в честь путеводной звезды. В Polaris ребята решают специально подобранные контесты под их уровень, дорешивают их с помощью пошаговых разборов, изучают новую теорию, решают специально подготовленные для них подводящие упражения, а также получают подробные рекомендации на основе их участия в тренировочных контестах. Более того, специально для участников группы я делаю пошаговые разборы тех задач, которые интересны самим участникам. Также, в группе регулярно ведется обсуждение прошедших контестов, а в ближайшем будущем мы будем готовиться к предстоящим олимпиадам (как школьным, так и студенческим). Присоединяйтесь, я буду вам очень рад!↵
↵
А теперь перейдем к самому разбору контеста. Но перед этим, я бы хотел ввести несколько правил чтения разбора для того, чтобы вы смогли получить максимум пользы от него.↵
↵
1. Перед чтением разбора задачи, убедитесь, что вы прочитали задачу, подумали над ней, извлекли из свой головы и записали/нарисовали максимальное количество идей и больше уже ниечго не можете придумать.↵
2. Во время чтения разбора, если в какой-то момент, какое-то предложение в разборе навело вас на новую мысль, перестаньте читать разбор и вернитесь к пункту (1), а именно продолжите с этого места генерровать новые идеи. Это очень важно.↵
3. Если вы дочитали текст разбора до конца и не поняли, как решать задачу или остались вопросы, то их нужно обязательно задать в комментариях или спросить в Polaris. Там вам помогут я и ребята, кто справился с этой задачей. Также в этом случае, полезно прочитать код, который будет прикреплен в разбору.↵
4. После того, как вы решили задачу, обязательно посмотрите код других участников и код с разбора. Возможно, он наведет вас на мысль о том, как можно было проще и быстрее реализовать решение задачи.↵
↵
A. Сходимость↵
===================↵
↵
<spoiler summary="Шаг 1">↵
Первое, на что я обратил внимание, что финальная позиция — это одна из позиций в исходном маасиве. Почему? Потому, что если это не так, и финальная позиция оказалась в точке $x$, тогда мы можем ее подвинуть в ближайшую точку в массиве $a_i$.↵
</spoiler>↵
↵
<spoiler summary="Шаг 2">↵
Следующее, на что я обратил внимание -- это ограничения задачи, они позволяют перебрать точку $x=a_j$ и посчитать для нее ответ.↵
</spoiler>↵
↵
<spoiler summary="Шаг 3">↵
Как посчитать ответ. Два человека идут к точке между ними, значит нам нужно разделить всех людей на три группы, какие?↵
</spoiler>↵
↵
<spoiler summary="Шаг 4">↵
1. $a_i=x$, пусть их $M$↵
2. $a_i<x$, пусть их $L$↵
3. $a_i>x$, пусть их $R$↵
Тогда как посчитать ответ?↵
</spoiler>↵
↵
<spoiler summary="Шаг 5">↵
Нам не нужно учитывать людей из первой группы, т.к. они уже стоят в финальной точке. Как подвинуть остальных людей? Каким парам людей не имеет смысла звонить?↵
</spoiler>↵
↵
<spoiler summary="Шаг 6">↵
Тем парам людей, которые находятся в одной группе. Еще если мы позвоним людям из разных групп, то мы всегда можем назначить точку $x$. Тогда чему равен ответ?↵
</spoiler>↵
↵
<spoiler summary="Шаг 7">↵
Ответ равен $\max(L, R)$↵
</spoiler>↵
↵
Решение: [submission:376629392]↵
↵
B. Выравнивание тортика↵
===================↵
↵
<spoiler summary="Шаг 1">↵
Пусть мы знаем ответ $h$ для префикса $0\ldots i$. Как нам проверить, правильный ли он или нет? Какие есть условия?↵
</spoiler>↵
↵
<spoiler summary="Шаг 2">↵
Самое простое условие -- это $a_0 \ge h$, тогда мы можем к себе в запас положить $a_0-h$ лишней глазури. Какое будет условие для $a_1$?↵
</spoiler>↵
↵
<spoiler summary="Шаг 3">↵
Условие такое: $a_1 + (a_0-h) \ge h$. Так как мы можем сложить глазурь $a_1$ и остатки глазури с прошлого шага $a_0-h$. Перепишем это условие: (a_0+a_1) \ge 2h. Тогда у нас останется $(a_0+a_1)-2h$ лишней глазури. Тогда какое условие в общем виде для префикса $i$?↵
</spoiler>↵
↵
<spoiler summary="Шаг 4">↵
Такое: $a_0+a_1+\ldots+a_i\ge (i+1)h$. Тогда получается, что $h \le \frac{A_i}{i+1}$, где $A_i$ — префиксная сумма массива $a: A_i=A_{i-1}+a_i$.↵
</spoiler>↵
↵
Решение: [submission:376640529]↵
↵
C1. Рассадка за столами (простая версия)↵
===================↵
↵
<spoiler summary="Шаг 1">↵
Первое, на что я обратил внимание -- это ограничения задачи, которые позволяют ее решать за, например, $O(n^2)$. То есть мы можем что-то перебрать, а потом при фиксированном чем-то можем сделать еще что-нибудь за $O(n)$. Какую простую версию задачи можно решить?↵
</spoiler>↵
↵
<spoiler summary="Шаг 2">↵
Представим, что у нас нет людей типа A, тогда есть только I и E. Тогда как решить такую подзадачу?↵
</spoiler>↵
↵
<spoiler summary="Шаг 3">↵
Чтобы решить эту подзадачу, мы должны просто идти слева направо по строке. Если встретили I, то сажаем его за новый столик (если столики остались), а если E — то сажаем его за неполный столик с хотя бы одним человек (если такой есть).↵
Хорошо, теперь вернем A. По сути, A — это либо I, либо E. Пусть мы знаем, сколько из A людей перекрасятся в I, тогда как нам выгодно их красить?↵
</spoiler>↵
↵
<spoiler summary="Шаг 4">↵
Нам выгодно перекрашивать некоторый префикс людей типа A в тип I, потому что мы хотим, чтобы на момент рассмторения I было как можно больше свободных столов, а на момент рассмотрения E, было как можно больше непустых столов. Тогда как решать всю задачу?↵
</spoiler>↵
↵
<spoiler summary="Шаг 5">↵
Перебираем, сколько людей типа A мы перекрасим в тип I (остальные будут перекрашены в тип E), перекрашиваем, проверяем за линию. Итого $O(n^2)$.↵
</spoiler>↵
↵
Решение: [submission:376663490]↵
↵
C2. Рассадка за столами (сложная версия)↵
===================↵
↵
<spoiler summary="Шаг 1">↵
Попробуем решить жадно. Основная проблема — как работать с A. Пусть мы встретили A. Что мы можем с ним сделать?↵
</spoiler>↵
↵
<spoiler summary="Шаг 2">↵
Мы можем посадить его за пустой столик, но тогда мы заблокируем место для одного из будущих I. А если посадим его за непустой столик? Тогда мы займем место для какого-то из E. Можем ли мы как-то исправить ситуацию для I? Непонятно. А для E?↵
</spoiler>↵
↵
<spoiler summary="Шаг 3">↵
Мы можем попытаться пересадить E, который был посажен за непустой столик за новый столик, а затем посадить E. Отлично, тогда давайте хранить количество пустых столов, количество мест за непустыми столами, а также количество A, которые мы посадили за непустые столы (именно их мы можем пересаживать за пустые столы). Если встретили E или I, то решаем как обычно, а если A, то сначала пытаемся посадить его за непустой стол, а если не получилось, то пытаемся посавдить за пустой стол.↵
</spoiler>↵
↵
Решение: [submission:376859618 ]↵
↵
D. Магический многоярусный тортик↵
===================↵
↵
<spoiler summary="Шаг 1">↵
Первое, на что я обратил внимание, что если все $a_i=0$, то это задача о Ханойских Башнях. Обычно, в подобных задачах, ее решают так: рекурсивно переносят первые $(n-1)$ слоев из первого места во второе, затем переносят $n$-й слой из первого слоя в третий, а потом оставшиеся $(n-1)$ слоев переносят из второго места в третье. Но здесь бывают случаи, когда $a_i > 0$. Какой есть простой случай, когда ответа нет?↵
</spoiler>↵
↵
<spoiler summary="Шаг 2">↵
Когда есть $a_i>i$ (в 0-индексации), тогда ответа нет, потому что мы не сможем никогда переместить этот слой никуда, потому что максимальное количество слоев над ним не может быть больше $i$. Хорошо, осталось рассмотреть случай, когда $a_i \le i$. Можем ли мы по аналогии с Ханойскими башнями решить задачу?↵
</spoiler>↵
↵
<spoiler summary="Шаг 3">↵
Пусть $k=a_{n-1} < n$, тогда чтобы переместить последний слой, нам надо сделать так, чтобы над ним было ровно $k$ слоев. Что мы можем сделать?↵
</spoiler>↵
↵
<spoiler summary="Шаг 4">↵
Мы можем переместить $n-1-k$ первых слоев с первого места на второе. После этого на первом месте будет ровно $(k+1)$ слой, тогда мы можем переместить последний слой из первого места в третье. А что теперь?↵
</spoiler>↵
↵
<spoiler summary="Шаг 5">↵
Если $k=0$, то по аналогии с Ханойскими башнями осталось переместить оставшиеся $(n-1)$ слоев из второго места в третье. А если $k>0$? В таком случае, у нас есть три места, в каждом из которых есть сколько-то слоев. Причем, во втором месте лежат самые маленькие слои.↵
</spoiler>↵
↵
<spoiler summary="Шаг 3">↵
Мы можем попытаться переместить либо слои из первого места в третье, либо из второго места в первое. Можем ли мы сделать первый вариант? Не всегда. А второй вариант? Да, можем, тогда в конце нам останется опять переместить $(n-1)$ слой из первого места в третье. Сколько тогда мы сделаем операций?↵
</spoiler>↵
↵
<spoiler summary="Шаг 4">↵
Если $F(n)$ — количество операций при перемещении префикса длины $n$, тогда $F(1)=1$, а чему равно $F(n)$?↵
</spoiler>↵
↵
<spoiler summary="Шаг 5">↵
$F(n) = F(n-1-k) + 1 + F(n-1-k) + F(n-1) = 2F(n-1-k)+F(n-1)+1$, причем, если $k=0$, то $F(n)=F(n-1)+1+F(n-1)=2F(n-1)+1$. Верно ли, что $F(n) < 2^n$?↵
</spoiler>↵
↵
<spoiler summary="Шаг 6">↵
Да, верно, потому что $F(1)=1<2^1=2$. Далее, если $k=0$, то $F(n)=2F(n-1)+1\le 2\cdot(2^{n-1}-1)+1=2^n-2<2^n$. И если $k>0$, то $F(n)=2F(n-1-k)+F(n-1)+1\le 2\cdot (2^{n-1-k}-1)+2^{n-1}-1+1 \le 2\cdot (2^{n-2}-1)+2^{n-1}=2^n-2<2^n$↵
</spoiler>↵
↵
Решение: [submission:376860585]↵
↵
↵
E. Змеиное расположение↵
===================↵
↵
<spoiler summary="Шаг 1">↵
Посмотрим на самую длинную змею. Как она выглядит? Где начинается и где заканчивается?↵
</spoiler>↵
↵
<spoiler summary="Шаг 2">↵
Она начинается в самом верхнем левом углу и заканчивается в самом правом нижнем углу. Если это не так, то ее никак не уместить в поле $n\times n$.↵
</spoiler>↵
↵
<spoiler summary="Шаг 3">↵
Дальше, я смотрю на антидиагонали:↵
↵
↵
~~~~~↵
01234↵
12345↵
23456↵
34567↵
45678↵
~~~~~↵
↵
Здесь каждой цифрой обозначены диагонали. Сколько раз один путь вправо-вниз может проходить по одной диагонали?↵
↵
</spoiler>↵
↵
<spoiler summary="Шаг 4">↵
По каждой диагонали не более одного раза. Хорошо, раз мы знаем где начинается и где заканчивается самый длинный путь, то пойдем дальше, а именно расмотрим диагональ $1$. Что мы про нее знаем?↵
</spoiler>↵
↵
<spoiler summary="Шаг 5">↵
Мы знаем, что одна из клеток принадлежит самой длинной змее длины $2n-1$, а что мы можем сказать про вторую клетку?↵
</spoiler>↵
↵
<spoiler summary="Шаг 6">↵
Она принадлежит змее длины $2n-3$, потому что если нет, то мы не сможет расположить эту змею нигде больше. То есть мы нашли старт змеи $(2n-3)$, а где ее конец?↵
</spoiler>↵
↵
<spoiler summary="Шаг 7">↵
Ее конец где-то в предпоследней диагонали. Обозначим $X$ — змея длины $2n-1$, а $Y$ — змея длины $2n-3$, пусть мы знаем, что например картинка выглядит примерно так:↵
↵
↵
~~~~~↵
XX....↵
Y.....↵
.....?↵
....?X↵
~~~~~↵
↵
Тогда как может выглядеть правый нижний угол?↵
↵
</spoiler>↵
↵
<spoiler summary="Шаг 8">↵
Он может выглядеть только так:↵
↵
↵
~~~~~↵
XX....↵
Y.....↵
.....X↵
....YX↵
~~~~~↵
↵
Потому что иначе две змеи пересекутся.↵
↵
</spoiler>↵
↵
<spoiler summary="Шаг 9">↵
Продолжим процесс. Допустим, мы знаем про каждую клетку диагонали $i$, каким змеям они принадлежат. Тогда мы знаем, каким змеям принадлежат клетки симметричной диагонали (они там симметричны). Тогда мы по сути хотим итеративно найти стартовые клетки всех змеи. Они однозначно зададут все пути. Почему?↵
</spoiler>↵
↵
<spoiler summary="Шаг 10">↵
Мы все знаем про диагональ $i$ (в 0-индексации), а именно знаем про каждую из $(i+1)$ клеток, какой змее они принадлежат. Мы хотим понять это для диагонали $(i+1)$. Во-первых, мы должны продолжить каждый из $(i+1)$ путей либо вниз, либо вправо. Причем некоторый префикс путей мы можем продолжить вниз, а оставшийся суффикс — вправо. Тогда останется ровно одна клетка, которую займет новая змея.↵
</spoiler>↵
↵
<spoiler summary="Шаг 11">↵
Тогда на каждой диагонали мы хотим найти отрезок клеток, где мы можем начать новую змею исходя из уже нарисованных путей. Пусть на диагонали $i$ отрезок имеет длину $L_i$, тогда ответ равен $L_0\cdot L_1\cdot \ldots \cdot L_{n-1}$.↵
</spoiler>↵
↵
Решение: [submission:376863113]
