Система телефонных номеров в России устроена следующим образом. Все телефонные номера имеют одну и ту же длину — M цифр. Номер состоит из двух частей: несколько первых цифр номера составляют код города, остальные цифры определяют номер абонента в пределах этого города.

В процессе развития сети коды городов регулярно меняются, при этом, коды различных городов обязательно различны. В остальном коды могут быть совершенно произвольными, в том числе код одного города может быть началом кода другого (например, код Нижнего Новгорода — 831, а код Сарова — 83130) и т. п. Если коды нескольких городов являются началом M-значного номера абонента, кодом города этого номера считается наидлиннейший из таких кодов. Так, если есть всего четыре города: Нижний Новгород, Балахна, Дзержинск и Саров с кодами, соответственно, 831, 83144, 8313 и 83130, и M = 9, то: телефоны 831123456 и 831412345 — телефоны Нижнего Новгорода, 831312345 — телефон Дзержинска, 831301234 — Сарова, а 831441234 — Балахны.

В этой задаче мы не будем учитывать различные другие ограничения на телефонные номера, существующие в реальности (например, в реальности никакой номер абонента в городе не может начинаться на 03, т. к. 03 — это телефон скорой помощи). Мы будем считать, что любой из 10^M возможных M-значных номеров является допустимым телефонным номером.

Нетривиальной задачей становится задача определения, сколько всего телефонных номеров может быть выдано в каждом городе. Например, в приведённом выше примере в Балахне и Сарове могут быть выданы 10 000 телефонных номеров (все четырёхзначные номера), в Дзержинске могут быть выданы 90000 телефонных номеров — все пятизначные телефонные номера, кроме начинающихся на ноль, а в Нижнем Новгороде могут быть выданы 890 000 номеров — все шестизначные номера, кроме тех, которые начинаются на цифру 3, а также на последовательность 44.

Напишите программу, которая решит эту задачу для произвольного набора кодов городов.

Рассмотрим произвольную последовательность целых чисел. Между числами можно расставить знаки арифметических операций + или – , и таким образом получать некоторые выражения, которые принимают различные значения. Например, если взять последовательность: 17, 5,  - 21, 15, то можно получить восемь различных выражений:

Назовем последовательность делящейся на натуральное K, если + и – могут быть расставлены так, что итоговое значение выражения будет делиться на K. В приведенном примере последовательность делится на 7  (17 + 5 +  - 21 - 15 =  - 14), но не делится на 5.

Ваша задача — написать программу, определяющую делимость последовательности на целое число.

Новый Мытищинский театр «Фэст» украшен гигантской гирляндой, управляемой компьютером, в которой используются тысячи лампочек. Каждый ряд лампочек в гирлянде управляется набором переключателей, которые контролируются с использованием специальной компьютерной программы. К сожалению, электрики установили неверный набор переключателей, а сегодня вечером состоится открытие театра. Ваша задача — написать программу, которая бы заставила переключатели работать корректно. Ряд лампочек в гирлянде состоит из n лампочек и контролируется n переключателями. Лампочки и переключатели занумерованы слева направо от 1 до n. Каждая лампочка может быть либо включена, либо выключена. Каждый тестовый пример в этой задаче будет содержать начальную и желаемую конечную конфигурации лампочек. Исходно предполагалось, что каждый переключатель будет контролировать одну лампочку. Однако ошибка в электронике привела к тому, что каждый переключатель помимо своей лампочки также изменяет состояние двух (или одной, если основная лампочка находится c краю) соседних с ней. Так, самый левый переключатель (i = 1) изменяет состояние двух самых левых лампочек (1 и 2), а самый правый (i = n) — двух самых правых (n - 1 и n). Каждый из оставшихся переключателей (1 ≤ i ≤ n) изменяет состояние трех лампочек с номерами i - 1, i и i + 1. Исключение составляет единственный случай, когда имеется ровно одна лампочка и один переключатель. В этом случае этот переключатель контролирует эту лампочку. Таким образом, если, к примеру, лампочка 1 включена, а лампочка 2 выключена, то при нажатии на переключатель 1 лампочка 1 выключится, а лампочка 2 включится. Определим минимальную стоимость перехода из одной конфигурации к другой как минимальное количество переключателей, которое требуется нажать, чтобы получить из начальной конфигурации конечную.

Можно представить состояние ряда лампочек как двоичное число, где 0 означает, что лампочка выключена, а 1 — что лампочка включена. Так, в частности, двоичное число 01100 представляет собой ряд из пяти лампочек, среди которых вторая и третья включены, а остальные выключены. Можно превратить эту конфигурацию в конфигурацию 10000, нажав последовательно на переключатели 1, 4 и 5, но дешевле сделать это, просто изменив состояние переключателя 2. Напишите программу, которая определит, на какие переключатели следует нажать, чтобы перевести начальную конфигурацию лампочек в конченую за минимальной стоимость. В некоторых случаях подобное может оказаться невозможным. Отметим, что для компактности представления двоичные числа записываются как десятичные, то есть вместо 01100 и 10000 используются числа 12 и 16 соответственно.

В телеигре "The Price is Right" игроки (обычно четверо) соревнуются в угадывании стоимости того или иного предмета. Побеждает тот, кто назвал наиболее близкое число, не превосходящее ответа. Ввиду популярности телеигры "Кто Хочет Стать Миллионером", в которой участвует один игрок, American Contest Management (ACM) решило выпустить свою версию игры «The Price is Right» для одного игрока. В этой версии каждому участнику даётся G (1 ≤ G ≤ 30) попыток и L (0 ≤ L ≤ 30) жизней. Игроку требуется точно угадать стоимость предмета. Если очередная попытка верна, то игрок выигрывает. В противном случае он теряет попытку. Помимо того, если он называет число, большее ответа, то также теряет одну жизнь. Игрок проигрывает, если у него не остаётся попыток или он называет большую стоимость, не имея ни одной жизни. Все цены положительные целые числа. Оказывается, что для некоторых значений G и L при условии, что искомая стоимость лежит в интервале от 1 до N включительно, можно избрать заведомо выигрышную стратегию. ACM не хочет, чтобы выигрывал каждый участник, поэтому организаторы хотят быть уверены, что настоящая стоимость превосходит N. Но в то же время нельзя делать игру слишком сложной, поскольку в противном случае победителей будет слишком мало, и игра быстро потеряет популярность. Поэтому организаторы хотят подобрать значения G и L в зависимости от искомой стоимости. В связи с этим ACM попросило вас решить следующую задачу: по заданным значениям G и L найти максимальное значение N, при котором игрок может воспользоваться заведомо выигрышной стратегией.

Будем называть пару строк (α, β) подпарой строки γ если γ = γ₁α γ₂β γ₃ для некоторых (возможно пустых) строк γ₁, γ₂, γ₃. Длиной пары строк будем называть сумму длин составляющих ее строк: |(α, β)| = |α| + |β|.

По заданным двум строкам ξ и η найдите их длиннейшую общую подпару, то есть такую пару строк (α, β), что она является подпарой как ξ, так и η, и ее длина максимальна.