Submission Хочется рассказать о логике, использованной при решении задачи Е (которую я не успел дописать за отведенное время и засабмитил на дорешивании).
Для этого пригодится знание того, что такое числа Каталана, а также как умение выводить их формулу. Подробно про числа Каталана можно прочитать, например, на вики: тык, Можно по разному дать определение, мы определим число $$$C_n$$$ как количество правильных скобочных последовательностей длины $$$2n.$$$ Нас интересует следующий довольно известный и изящный метод найти это число.
Рассмотрим координатную сетку, по которой нам нужно дойти из угла $$$(0,0)$$$ в угол $$$(n,n)$$$. Мы можем идти только вправо или вверх. Шаг вправо соответствует открывающейся скобке, шаг вверх — закрывающейся. Тогда существует взаимно однозначное соответствие между правильной скобочной последовательностью длины $$$2n$$$ и путем из $$$(0,0)$$$ в $$$(n,n)$$$, не пересекающим диагональ $$$y=x$$$, так как точка выше этой диагонали означала бы что на данном префиксе закрывающихся скобок больше чем открывающихся. Как найти количество таких путей?
Количество всех путей равно $$$\binom{2n}{n}.$$$ Из этого числа мы вычтем количество неправильных путей. Неправильные пути — те, что пересекают $$$y=x$$$, или, что эквивалентно, имеют хотя бы одну общую точку с прямой $$$y=x+1.$$$ Возьмем первую (с наименьшим $$$x$$$) общую точку $$$(a, a+1)$$$ и отразим участок пути от $$$(0,0)$$$ до $$$(a, a+1)$$$ относительно прямой $$$y=x+1.$$$ Получим некоторый путь из $$$(-1,1)$$$ в $$$(n,n)$$$. Это — взаимно однозначное соответствие. Действительно, любой путь из $$$(0,0)$$$ имеющего общие точки с $$$y=x+1$$$ можно отразить до первой такой точки. В то же время любой путь из $$$(-1,1)$$$ в $$$(n,n)$$$ обязан иметь общие точки с $$$y=x+1$$$, так как начало и конец пути расположены по разные стороны от прямой, а значит мы также можем отразить кусок пути до первой такой точки. Количество таких неправильных путей — $$$\binom{2n}{n+1}.$$$ (или. эквивалентно $$$\binom{2n}{n-1}.$$$) А значит количество правильных путей $$$C_n = $$$\binom{2n}{n} — $$$\binom{2n}{n+1}.$$$ Это и есть число Каталана. Подробнее на картинке.
