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

В задаче $$$4$$$ подзадачи. Подзадача $$$0$$$ — тесты из условия, за неё баллы не начисляются. Тестирование подзадачи начинается, если пройдены все тесты в необходимых подзадачах. Система оценки «полная» означает, что решению будут начисляться баллы только при успешном прохождении всех тестов данной подзадачи.

Имеется набор карточек для игры. На каждой карточке написано число, причём числа на разных карточках могут совпадать. В игру играют два человека. В каждом раунде игроки вытаскивают наугад по одной карточке и оставляют её у себя. У кого число на карточке оказалось больше, тот и победил в этом раунде. А если числа совпали, то в этом раунде объявляется ничья. Игра продолжается, пока не закончатся все карточки.

Нельзя заранее предсказать, сколько за время игры будет «ничьих» и побед у каждого игрока. Если на карточках были написаны числа $$$1,1,2,3,4,5$$$, то можно, например, сыграть $$$3$$$ таких раунда: $$$(2,5), (4,3), (1,1)$$$. В этом случае первый раунд выиграл второй игрок, второй раунд выиграл первый игрок, а третий раунд закончился «ничьей».

Спрашивается, а сколько существует разных интересных вариантов сыграть состоящую из $$$N$$$ раундов игру, если известны числа, написанные на карточках? Вариант считается интересным, если количество «ничьих» максимально для данного набора карточек, а также первый игрок выиграл ровно $$$K$$$ раз. Два варианта, отличающиеся только порядком раундов, считаются одинаковыми. Карточки, на которых записаны одинаковые числа, не отличаются друг от друга.

В задаче $$$4$$$ подзадачи. Подзадача $$$0$$$ — тесты из условия, за неё баллы не начисляются. Тестирование подзадачи начинается, если пройдены все тесты в необходимых подзадачах. Система оценки «полная» означает, что решению будут начисляться баллы только при успешном прохождении всех тестов данной подзадачи.

В лесу неподалёку растёт очень много грибов и находится ещё большее количество опушечек. Для удобства ориентации в лесу грибники пронумеровали опушечки леса номерами от 1 до $$$n$$$. Также известно, что вход в лес находится на опушечке под номером $$$s$$$.

Грибники протоптали в лесу целую сеть тропинок. Любая тропинка соединяет между собой две опушечки в лесу. На каждой опушечке либо растёт ровно один гриб, либо не растёт ничего. Чтобы не теряться в лесу, грибники проложили лишь самые необходимые тропинки, поэтому между любыми двумя опушечками в лесу существует только одна связывающая их последовательность тропинок, в которой тропинки не повторяются. Кроме того, известно, что грибы растут на тех и только тех опушечках, которые не являются промежуточными ни на одном пути от входа в лес до другой опушечки.

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

В задаче $$$4$$$ подзадачи. Подзадача $$$0$$$ — тесты из условия, за неё баллы не начисляются. Тестирование подзадачи начинается, если пройдены все тесты в необходимых подзадачах. Система оценки «полная» означает, что решению будут начисляться баллы только при успешном прохождении всех тестов данной подзадачи.

Девочка Аня выписала на доске $$$N$$$ различных чисел в порядке возрастания, а затем задумалась, что с ними можно сделать интересного? Проходящий мимо мальчик Боря заметил раздумья Ани и предложил ей сыграть в следующую игру: надо выписать на доску все упорядоченные тройки чисел $$$(a, b, c)$$$ такие, что квадратное уравнение $$$ax^2 + bx + c = 0$$$ ($$$a \neq 0$$$) имеет по крайней мере один вещественный корень. Две тройки $$$(a_1, b_1, c_1)$$$ и $$$(a_2, b_2, c_2)$$$ считаются различными, если $$$a_1 \neq a_2$$$ или $$$b_1 \neq b_2$$$ или $$$c_1 \neq c_2$$$. Одно и то же число можно использовать больше одного раза. Школьники выписали какое-то количество троек и решили проверить себя. Помогите им посчитать, сколько всего таких упорядоченных троек должно быть выписано на доске.

В задаче $$$4$$$ подзадачи. Подзадача $$$0$$$ — тесты из условия, за неё баллы не начисляются. Тестирование подзадачи начинается, если пройдены все тесты в необходимых подзадачах. Система оценки «полная» означает, что решению будут начисляться баллы только при успешном прохождении всех тестов данной подзадачи.

Хромосома в вольной интерпретации программиста – это символьная строка, в которой каждый отдельный символ – это ген. При скрещивании двух родительских хромосом одинаковой длины получается новая хромосома такой же длины. Каждый её ген достаётся «по наследству» случайным образом от одной из двух родительских хромосом. Причём первый ген хромосомы потомка – это первый ген какого-либо из родителей, второй ген хромосомы потомка – это второй ген какого-либо из родителей и т.д. Из-за фактора «случайности» у пары родительских хромосом может получиться много разных потомков. А можно ли, имея много разных родительских хромосом, установить – какие из них действительно являются родителями заданной хромосомы?

В задаче $$$4$$$ подзадачи. Подзадача $$$0$$$ — тесты из условия, за неё баллы не начисляются. Тестирование подзадачи начинается, если пройдены все тесты в необходимых подзадачах. Система оценки «полная» означает, что решению будут начисляться баллы только при успешном прохождении всех тестов данной подзадачи.