Задача A. Слово из кубиков

Автор:A. Klenin
Входной файл: input.txt   Ограничение времени:8 сек
Выходной файл: output.txt   Ограничение памяти:4 Мб

Условие

Имеется N кубиков, на гранях которых написаны буквы. Требуется определить, можно ли из этих кубиков составить данное слово длиной K символов, и если да, то вывести номера использованных кубиков. При этом каждый кубик можно использовать только один раз. Если решений несколько, выдать любое из них.

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

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

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

Выходной файл должен содержать последовательность из K различных целых чисел от 1 до N, задающих номера кубиков для каждой буквы слова, начиная с первой. Если решения нет, выходной файл должен содержать единственное число 0.

Ограничения

1 ≤ N, K ≤ 12.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
5
TEST
ABCDAB
TTTTTT
STSTST
CREATE
ERRORS
2 5 3 4

Задача B. Барбара

Автор:A. Klenin
Входной файл: input.txt   Ограничение времени:1 сек
Выходной файл: output.txt   Ограничение памяти:4 Мб

Условие

На некотором языке все слова записываются заглавными латинскими буквами, и состоят из слогов. Слогом называется непустая последовательность согласных, заканчивающаяся гласной. Все остальные последовательности букв словами этого языка не являются. Например, слово BARBARA состоит из трех слогов — BA, RBA и RA. Последовательности букв ААХ, Е, К, АНА словами не являются. Осмысленными считаются слова, в которых все согласные различны.

По данной последовательности из N заглавных латинских букв определить, является ли она осмысленным словом и, если да, то сколько различных слогов можно составить из букв этого слова. Например, из слова BARAKA можно составить 15 слогов — BA, KA, RA, BKA, KBA, BRA, RBA, KRA, RKA, BKRA, BRKA, RBKA, RKBA, KBRA, KRBA.

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

Входной файл содержит единственную строку — исходную последовательность букв.

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

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

Ограничения

1 ≤ N ≤ 20

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

Входной файл (input.txt) Выходной файл (output.txt)
1
BARAKA
15

Задача C. Квадратное озеро

Автор:А. Кленин
Входной файл: input.txt   Ограничение времени:4 сек
Выходной файл: output.txt   Ограничение памяти:4 Мб

Условие

Квадратное озеро, покрытое многочисленными мелкими островками, задается матрицей размером NxN. Каждый элемент матрицы содержит либо символ '@', обозначающий островок, либо символ '.' (точка), обозначающий участок свободной воды. В левом верхнем углу озера находится квадратный плот размером MxM клеток. За один шаг плот может сдвигаться на одну клетку по горизонтали или вертикали. Требуется определить минимальное число шагов, необходимых для того, чтобы плот достиг правого нижнего угла озера.

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

В первой строке входного файла содержатся числа N и M, разделенные пробелами. В следующих N строках находится матрица, представляющая озеро, по N подряд идущих символов в строке. Подматрица размером MxM, находящаяся в левом верхнем углу, не содержит островов (т.е. начальное положение плота всегда допустимо).

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

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

Ограничения

1 <= M <= N <= 100

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

Входной файл (input.txt) Выходной файл (output.txt)
1
7 2
.......
...@...
.......
..@....
.......
.......
....@..
10

0.029s 0.004s 11