Личное первенство университета по программированию.
Осень 2002 года.
Во всех задачах ввод данных
производится из файла INPUT.TXT, а вывод результатов - в файл OUTPUT.TXT.
Формат входного файла соответствует спецификации, дополнительные проверки не нужны.
Все строки, в том числе последняя, оканчиваются символом перехода на новую
строку.
1. Снежный ком (10 сек на тест)
Фраза,
которая начинается со слова из одной буквы, и в которой каждое слово на одну
букву длиннее предыдущего, называется “снежным комом”. Вот великолепный пример снежного кома из 20 английских слов: “I do
not know where family doctors acquired illegibly perplexing handwriting;
nevertheless, extraordinary pharmaceutical intellectuality, counterbalancing
indecipherability, transcendentalizes intercommunications’
incomprehensibleness.”
Для
получения случайного осмысленного текста можно использовать следующий алгоритм.
Возьмем произвольный большой текст. Взяв в качестве первого слова любое слово
из этого текста, следующим ставим слово, которое расположено где-нибудь в
исходном тексте непосредственно после выбранного слова. Если есть несколько
кандидатов, случайно выбираем любого из них. Аналогично третьим ставим слово,
которое расположено в исходном тексте непосредственно после второго выбранного
слова. И так далее.
Напишите
программу, которая выделяет максимально длинный “снежный ком” из большого
текста по указанному выше алгоритму.
Во входном файле содержится одна или более строк длиной не более 200 символов, в которых содержится текст, состоящий не более чем из 30000 слов. Количество различных слов в тесте не превышает 5000. Максимальная длина слов не превышает 20 букв. Текст состоит из латинских букв и знаков препинания. Регистр букв при составлении снежного кома игнорируется.
Словом будем называть последовательность прописных и строчных латинских букв
(“x-ray” состоит из 2 слов X и RAY, “Mary's” состоит из 2 слов MARY и S, “It's words” состоит из 3 слов IT, S и WORDS).
В выходной
файл вывести самый длинный снежный ком,
найденный в тексте. Снежный ком не должен содержать знаков препинания, а слова,
напечатанные строчными буквами, должны
отделяться друг от друга одним пробелом. Если существует несколько подходящих
вариантов, вывести один (любой) из них.
Пример INPUT.TXT:
Where family doctors study? I do not know where.
Doctors acquired illegibly drugs from gypsies.
You received F mark for illegibly perplexing handwriting.
OUTPUT.TXT для
примера:
i do not know where family doctors acquired illegibly perplexing
handwriting
2. HTML (10 сек на тест)
Для
опубликования текста задач этих соревнований в сети необходимо преобразовать
текст в HTML-формат.
Использование стандартного конвертера пакета MS Word привело
бы к сложным и большим по объему страницам, но которые в точности соответствуют
исходным документам. Если не требовать точного соответствия исходному
документу, то следующие простые правила для преобразования текста позволят
получить более компактные страницы.
·
Тексты задач состоят из нескольких абзацев, каждый из
которых записан на отдельной строке. Каждый абзац должен быть также записан на
отдельной строке и окружен тегами <p> и
</p>.
·
В тексте могут встречаться обозначения, которые необходимо
преобразовать в специальные HTML-коды.
Символ “<” нужно записать в выходном файле как “<”, символ “>” – как “>”, а символ “&” – как “&”. Последовательность символов “<=” – как “≤”, “>=” – как “≥”, а “/=” – как “≠”.
·
В тексте могут встретиться имена параметров задачи, которые
обычно выделяются курсивом. Однобуквенные имена, например, “n” нужно записать в выходной файл как “<i>n</i>”, а состоящие из нескольких букв, например, “aij” – как “<i>a<sub>ij</sub></i>”.
Напишите
программу для преобразования текста в HTML-формат.
Во входном
файле в первой строке находится целое число n (0<=n<=50). Далее следует n строк с именами параметров задачи, которые будут
выделяться в тексте курсивом. Имена состоят из 1-3 латинских букв. Регистр букв
является существенным, символы слева и справа от имен в тексте не являются
латинскими буквами. Далее следует одна или более строк с текстом. В тексте
могут встречаться русские и латинские буквы, знаки препинания и другие символы.
В выходной
файл вывести преобразованный текст.
Пример INPUT.TXT:
3
M
S
n
The first line of the input contains two integers M and S, separated by space.
The following M lines contain a single integer n
in a line (0<=n<=10000).
OUTPUT.TXT для
примера:
<p>The first line of the input contains two integers
<i>M</i> and <i>S</i>, separated by space.</p>
<p>The following <i>M</i> lines contain a single integer <i>n</i> in a line
(0≤<i>n</i>≤10000).</p>
3. Упрощение номеров (10 сек на тест)
Как, Вы не
можете запомнить 6 или 7-значный номер телефона, появившийся на секунду на
экране телевизора?! С помощью специальной методики, описываемой далее, Вы
превратитесь в ходячий телефонный справочник!
Очевидно,
что число 402 запомнить легче, чем число 110010010, а число 337377 запомнить
легче, чем число 957472. Значит, нужно чтобы запоминаемое число, с одной
стороны, содержало как можно меньше цифр, а с другой стороны, желательно, чтобы
в числе было как можно больше повторяющихся цифр. В качестве критерия сложности
запоминания примем сумму количества цифр в числе и количества различных цифр в
числе. Запоминаемое число можно записать в другой системе исчисления, возможно,
тогда его окажется легче запомнить. Например, число 65535 в шестнадцатеричной
системе исчисления выглядит как FFFF. Таким
образом, нужно подобрать основание системы исчисления для минимизации критерия
сложности. Основание системы исчисления нужно выбирать в диапазоне от 2 до 36,
тогда для представления числа можно использовать цифры 0-9 и латинские буквы A-Z.
Во входном
файле в первой строке содержится целое число n (1<=n<=1000).
Далее следует n строк,
каждая строка содержит целое число от 1 до 999999999.
В выходной
файл для каждого числа вывести на отдельной строке основание системы исчисления
(от 2 до 36), минимизирующее критерий сложности запоминания, и число в
выбранной системе исчисления, разделенные одним пробелом. Если несколько оснований
дают одинаковое значение критерия, то выбрать наименьшее среди них.
Пример INPUT.TXT:
2
2
65535
OUTPUT.TXT для
примера:
3 2
16 FFFF
4. Secret Research (10 сек на тест)
At a
certain laboratory results of secret research are thoroughly encrypted. A
result of a single experiment is stored as an information of its completion:
`positive result', `negative result', `experiment failed' or `experiment not
completed'.
The
encrypted result constitutes a string of digits S, which may take one of the
following forms:
positive result S = 1 or S = 23 or S = 2S3
negative result S = 51S
experiment failed S = 5S
(A
sample result 51S means that if we add digits 51 from the left hand side to a
digit sequence then we shall get the digit sequence corresponding to a failed
experiment)
You
are to write a program which decrypts given sequences of digits.
Input
A integer n stating the
number of encrypted results and then consecutive n lines, each
containing a sequence of digits given as ASCII strings.
Output
For each analysed sequence of
digits the following lines should be sent to output (in separate lines):
+ for a positive result - for a negative result * for a failed experiment ? for a not completed experiment
Sample
INPUT.TXT:
4235123222331523
Sample
OUTPUT.TXT:
+-?*