Тема: Загадочное число
Задача C. Загадочное число
Имя входного файла: enigmatic.in
Имя выходного файла: enigmatic.out
Ограничение по времени: 2 секунды
Ограничение по памяти: 256 мегабайт
{------------------------------------------------}
Толя — младший научный сотрудник в Отделе Изучения Смысла Жизни. Недавно он обнару-
жил, что в десятичной записи числа N скрыта важная истина, проливающая свет на некоторые
из вопросов жизни человечества. Однако по своей натуре Толя — человек эгоистичный и не хо-
чет с кем-либо делиться своим открытием. Поэтому он решил запомнить это число, а все записи,
связанные с ним, съесть.
К сожалению, Толя немного рассеян и забывчив, поэтому для запоминания числа N он выбрал
следующий путь. Есть некоторый набор из K чисел, так или иначе связанных с жизнью нашего
ученого, которые он помнит очень хорошо, даже лучше, чем дату своего рождения. Все эти числа
не более чем трехзначные.
Толя пытается представить число N в виде конкатенации чисел из этого набора (например,
конкатенация чисел 1 и 2 может дать 12 или 21, в зависимости от порядка). Никакое число нельзя
использовать дважды, с другой стороны все числа использовать необязательно. При этом Толя
хочет придумать (для упрощения запоминания) такое представление, в котором использовалось бы
как можно меньше чисел.
Напишите программу, которая будет находить такое представление.
Формат входного файла
Первая строка входного файла содержит число N (1 ? N < 10^45). Вторая строка содержит число
K — количество чисел в наборе (1 ? K ? 1000). Третья строка содержит K памятных Толе чисел
(0 ? ai < 1000). Все числа в наборе различны и не содержат ведущих нулей.
Гарантируется, что существует хотя бы одно требуемое представление числа N.
Формат выходного файла
В первой строке выходного файла выведите число M — количество чисел в искомом представ-
лении. В последующих M строках выведите числа в том порядке, в котором их необходимо кон-
катенировать для получения числа N. Если искомых представлений несколько, выведите любое из
них.
Примеры
enigmatic.in
123
4
1 3 12 23
enigmatic.out
2
12
3
enigmatic.in
123
4
1 2 3 123
enigmatic.out
1
123