Задача A. Карточки ≡

Условие

При подготовке пакета были использованы материалы сайта школьных олимпиад по информатике.

Вова очень тихий мальчик, он очень любит тихонько сидеть и что-нибудь делать. Недавно родители подарили Вове набор карточек, на которых написаны различные слова из латинских букв. Причем слова, написанные на карточках, выбраны таким образом, что никакое слово не является cуффиксом другого. Этот момент стал настоящим праздником для мальчика. Что он только с карточками не делал! Помимо этого, у родителей Вовы есть копировальная машина, и поэтому Вова в любой момент может делать копии любой из своих карточек.

Сегодня Вова затеял с родителями такую игру: родители называют Вове какое-то слово t, а он выкладывает на стол несколько карточек в ряд, образуя длинную строку s. При этом названное родителями слово t содержится в строке s как подстрока. Карточки накладывать друг на друга нельзя. В процессе этой игры Вова может использовать копировальную машину, то есть копировать имеющиеся у него карточки в любых количествах.

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

Решения, работающие при сумме длин слов на карточках не превосходящей 1000, N ≤ 100 и длине строки t не более 1000 символов будут оцениваться из 20 баллов.

Решения, работающие при сумме длин слов на карточках не превосходящей 10⁵, N ≤ 1000 и длине строки t не более 10000 символов будут оцениваться из 60 баллов.

Формат входного файла

В первой строке входного файла содержится слово t, названное родителями. Длина этого слова не превышает 10⁵.

В следующей строке задано число n (1 ≤ n ≤ 10⁵) — количество имеющихся различных карточек у Вовы. Далее следует n строк, каждая из которых содержит слово, написанное на карточке. Сумма длин всех слов на карточках не превосходит 10⁵.

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

Формат выходного файла

В первой строке выходного файла необходимо вывести единственное число k — количество использованных карточек (в том числе и полученных с помощью копировальной машины). Во второй строке необходимо вывести слово s, сложенное из k Вовиных карточек и содержащее слово t как подстроку. Если ответов несколько, выведите любой.

Если невозможно выложить карточки заданным образом, выведите в выходной файл единственную строку "No solution".

Примеры тестов

abacaba
4
zyx
aba
b
c

3
abacaba

torneo
3
qwertorn
neco
eopass

2
qwertorneopass

torneo
3
qwerty
neco
eopass

No solution

Задача B. Кубики ≡

Условие

При подготовке пакета были использованы материалы сайта школьных олимпиад по информатике.

Когда Вова был маленьким, родители подарили ему набор из n кубиков, на каждом из которых написано некоторое натуральное число. В этом наборе нет двух кубиков, на которых написаны одинаковые числа.

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

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

Зайдя в комнату, Вова сразу почуял неладное. Допросив Олю, он узнал как получилось так, что кубики перемешались. И тут Вову заинтересовало — может ли он выяснить каким количеством кубиков играл Петя (при этом Оля играла оставшимися)? Он поручил вам решить эту задачу!

Решения, работающие при n ≤ 1000 будут оцениваться из 40 баллов.

Формат входного файла

Первая строка входного файла содержит единственное число n (1 ≤ n ≤ 300000) — количество кубиков у Вовы.

Вторая строка содержит n целых чисел a_i (1 ≤ a_i ≤ 10⁹) — числа, написанные на кубиках, выложенных в порядке слева направо в тот момент, когда Вова вернулся домой. Все a_i различны.

Формат выходного файла

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

Примеры тестов

3
1 2 3

2
1 2 

5
2 1 5 9 6

2
2 3 

Задача C. Интересные числа ≡

Условие

При подготовке пакета были использованы материалы сайта школьных олимпиад по информатике.

Вася — юный математик. Папа часто рассказывает ему истории связанные с папиным детством, особенно то, что он, как и многие его сверстники, любил коллекционировать марки. У каждой марки была своя история, и папа Васи все эти истории помнил до последних мелочей. Особенными были истории о том, как были добыты марки из серии "Раритетные автомобили". Васе очень нравились рассказы его отца. Он тоже решил попробовать себя в этом деле. Так как Вася любил не раритетные автомобили, а математику, он решил собирать марки с различными числами.

Вася был очень упорным во всех своих начинаниях и часто добивался своей цели. Поэтому за небольшой отрезок времени он смог собрать марки со всеми числами от a до b. При этом на каждой марке написано ровно одно число. Вы конечно же понимаете, что марок с одинаковыми числами он не оставлял в своей коллекции, поэтому на всех марках были записаны различные числа.

Вася так же хорошо, как и его папа, запомнил все истории, связанные с каждой маркой. Особенно интересные истории были связаны с марками, на которых было написано такое число, у которого в десятичной записи есть хотя бы k одинаковых цифр подряд. Такие марки он назвал интересными. Например, если k = 2, то марки с числами 22, 111, 100, 556 являются интересными, а с числами 2, 121, 1212 не являются.

Вам заданы числа a, b и k. Требуется посчитать количество интересных марок с числами от a до b.

Решения, работающие при 1 ≤ a ≤ b ≤ 10⁶ будут оцениваться из 40 баллов.

В первом примере интересными являются марки с числами 11, 22, 33, 44, 55, 66, 77, 88, 99 и 100.

Во втором примере интересными являются марки с числами 111, 112, 113, 114, 115, 116, 117, 118, 119, 122 и 133.

Формат входного файла

Во входном файле заданы три целых числа a, b (1 ≤ a ≤ b ≤ 4 ⋅ 10¹⁸) и k (1 ≤ k ≤ 20).

Формат выходного файла

В выходной файл выведите единственное целое число — ответ на задачу.

Примеры тестов

1 100 2

10

111 133 2

11

Задача D. Стаканчики ≡

Условие

При подготовке пакета были использованы материалы сайта школьных олимпиад по информатике.

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

Использованные стаканчики Маша собирает следующим образом. Если пассажир не допил напиток, то Маша ставит его стаканчик в новую отдельную стопку. Если же стаканчик пуст, она ставит его в низ самой маленькой стопки (просто вкладывая эту стопку в пустой стаканчик), так как слишком высокую стопку легко уронить (пустой стаканчик ставится в отдельную стопку, только если поднос пуст).

Перед началом сбора использованной посуды Маша знает, сколько напитка в стакане осталось у каждого пассажира. Теперь ее интересует вопрос — сможет ли она донести поднос со стаканчиками, не уронив его. Для этого ей необходимо знать высоту самой большой стопки. Но так как пассажиров очень много, она не может посчитать это сама, поэтому просит вас помочь ей!

Решения, корректно работающие для n ≤ 1000 будут оцениваться из 40 баллов.

В примере в итоге получится одна стопка из первых трех стаканчиков и стопка из последних двух.

Формат входного файла

В первой строке входного файла задано единственное целое число n — количество пассажиров (1 ≤ n ≤ 10⁶).

В следующей строке через пробел заданы n целых чисел a_i — количество оставшегося напитка в стаканчиках (0 ≤ a_i ≤ 10⁹) в том порядке, в котором Маша будет их собирать. Пустому i-ому стакачику соответствует a_i = 0.

Формат выходного файла

В выходной файл выведите единственное целое число — количество стаканчиков в самой большой стопке.

Примеры тестов

5
1 0 0 2 0

3