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

Смогли прочитать текст выше? Теперь, руководствуясь описанными ниже правилами, напишите программу, которая моделирует чтение человеком текста.

Пусть человеку известен набор из n слов языка. Будем считать, что человек может прочитать слово s , если в его словаре имеется хотя бы одно такое слово w , что выполнены два условия:

• Существует способ переставить буквы слова w так, чтобы получилось слово s .
• Слова w и s начинаются с одной и той же буквы, а также заканчиваются одной и той же буквой.

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

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

При использовании простейшего варианта медианного сглаживания по последовательности чисел a ₁ , a ₂ , ..., a _n строится новая последовательность чисел b ₁ , b ₂ , ..., b _n по следующему алгоритму:

• b ₁ = a ₁ , b _n = a _n , то есть первое и последнее число новой последовательности совпадают с соответствующими числами исходной последовательности.
• При i = 2, ..., n - 1 значение b _i полагается равным медиане трёх значений a _{i - 1} , a _i и a _{i + 1} .

Напомним, что медианой набора из трех чисел называется число, которое окажется на втором месте, если три числа выписать в порядке неубывания. Например, медианой набора 5, 1, 2 является число 2, а медианой набора 1, 0, 1 — число 1.

Чтобы не усложнять себе задачу, Вася решил применять метод только к последовательностям, состоящим из нулей и единиц.

Проделав нехитрую процедуру один раз, Вася посмотрел на получившуюся последовательность и подумал: что будет, если снова применить к ней алгоритм, а потом применить его к следующему результату и так далее? Рассмотрев пару примеров, Вася обнаружил, что через несколько применений медианного сглаживания последовательность может перестать изменяться. Будем говорить, что последовательность стабильна , если она не изменяется при применении к ней медианного сглаживания.

Васе стало интересно, всегда ли последовательность рано или поздно становится стабильной. Он просит вас написать программу, которая по заданной последовательности нулей и единиц определит, становится ли она когда-нибудь стабильной, и если да, то сколько раз для этого нужно применить к ней метод медианного сглаживания.

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

Иерархия сотрудников завода описывается следующими простыми правилами:

• Всего на заводе n + 1 сотрудник. У каждого из них, кроме гендиректора, есть непосредственный начальник — один из других сотрудников. У гендиректора начальника нет.
• Все сотрудники завода так или иначе подчинены гендиректору, то есть любой сотрудник является либо гендиректором, либо непосредственным подчинённым гендиректора, либо непосредственным подчинённым непосредственного подчинённого гендиректора и так далее.

Гендиректор и его жена ходят по очереди, начинает гендиректор. За один ход необходимо выбрать одного произвольного сотрудника, чьим непосредственным начальником ещё не является гендиректор, и исправить эту оплошность, то есть назначить гендиректора непосредственным начальником выбранного сотрудника. Тот, кто не может сделать ход, проигрывает.

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

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

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

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

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