Задача A. Текст ≡

Условие

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

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

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

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

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

Первая строка входного файла содержит натуральное число k — максимально допустимая длина строки.

Вторая строка входного файла содержит текст, который необходимо вывести. Текст состоит из латинских букв, цифр, пробелов и символов "," (запятая), "." (точка), "!" (восклицательный знак) и "?" (вопросительный знак).

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

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

Ограничения

1 ≤ k ≤ 100. Размер входного файла не превышает 50000 байтов.

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

22
This     is a sample text!

This is a sample text!

12
This     is a sample text!

This is a
sample text!

Задача B. Укорачивание текста ≡

Условие

По заданному тексту длины N и образцу длины K определить длину минимальной подстроки в тексте, которая удовлетворяет данному образцу. Текст состоит только из маленьких латинских букв. Образец содержит маленькие латинские буквы и символ '*', заменяющий любое множество любых символов(в том числе пустое).

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

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

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

Ограничения

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

3 4
a*b
abab

2

Задача C. Однокоренные слова ≡

Условие

Слова марсианского языка записываются малыми латинскими буквами. При этом буквы a, e, i, o, u, y считаются гласными, а остальные — согласными.

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

Например, слово marsianin может быть записано в виде приставка(корень)суффикс как: m(arsianin), mar(sia)nin, (mar)sianin, и другими способами.

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

Требуется по данным двум марсианским словам определить, являются ли они однокоренными.

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

В первой строке входного файла содержится первое слово, во второй — второе слово.

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

Выходной файл должен содержать слово YES, если слова однокоренные, и NO в противном случае.

Ограничения

Слова имеют длину от 1 до 100 символов.

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

aceei
cee

NO

aceeidceef
cee

YES

y
y

YES