Задачи районно-городских командных соревнований 2006

К гласным буквам в латинском алфавите относятся буквы A, E, I, O, U и Y. Остальные буквы считаются согласными. Напишите программу, считающую количество гласных букв в тексте.

Во входном файле содержатся одна строка текста, состоящая только из прописных латинских букв и пробелов. Длина строки не превышает 100 символов.

В выходной файл вывести одно целое число – количество гласных во входном тексте.

PROGRAMMING CONTEST

5

Любое натуральное число можно представить в виде суммы нескольких последовательных натуральных чисел. Например, число 25 можно представить в виде суммы из одного (25), двух (12+13) и пяти чисел (3+4+5+6+7). Напишите программу, которая определяет максимальное количество чисел в таком разложении.

В первой строке входного файла содержатся целое число `N` (`1\ ≤\ N\ ≤\ 10^9`).

В выходной файл вывести одно целое число – максимальное количество чисел в разложении числа `N` на последовательные натуральные числа.

25

5

Некоторое сообщение, состоящее только из строчных латинских букв, для уменьшения размера было упаковано. Восстановление исходного сообщения должно осуществляться следующим образом: если в упакованном сообщении встречается символ '$', то в результат добавляется часть ранее распакованного сообщения, начиная с позиции после последнего встретившегося символа '#', либо с самого начала, если такого символа еще не встречалось. Напишите программу, выполняющую распаковку сообщения.

В первой строке входного файла содержится упакованное сообщение длиной до 50 символов, состоящая только из строчных латинских букв и символов '#' и '$'. Количество символов '$' в упакованном сообщение не более 10.

В выходной файл вывести распакованное сообщение.

ab$c$d#mu$

ababcababcdmumu

Будем называть два числа дружественными, если они состоят из одних и тех же цифр. Например, числа 1132 и 32321 является дружественными, а 12 и 123 нет (в первом числе нет цифры 3). Напишите программу, определяющую являются ли два заданных числа дружественными.

В первой строке входного файла содержатся два целых числа `A` и `B`, разделенных одним пробелом, (`0\ <\ A\ <\ 10^9`, `0\ <\ B\ <\ 10^9`).

В выходной файл вывести сообщение "YES", если `A` и `B` являются дружественными, или "NO", если не являются.

1132 32321

YES

Слиянием двух строк называется строка, состоящая из всех букв исходных строк, взятых в порядке следования этих букв в сливаемых строках. Например, для двух строк «xx» и «yy» возможными слияниями являются «xxyy», «xyxy», «xyyx», «yxxy», «yxyx» и «yyxx». Палиндромом называется строка, читаемая одинаково слева направо и справа налево.

Напишите программу, вычисляющую максимальную длину палиндрома, являющегося подстрокой какого-нибудь слияния двух заданных строк. В рассмотренном выше случае в слияниях можно найти следующие палиндромы «x», «y», «xx», «yy», «xyx», «yxy», «xyyx» и «yxxy». Самыми длинными палиндромами являются «xyyx» и «yxxy», имеющие длину 4.

В первой строке содержится первая строка, во второй строке вторая строка. Обе строки имеют длину от 1 до 20 букв включительно и содержат только строчные латинские буквы.

Вывести одно целое число – максимальную длину палиндрома, являющегося подстрокой слияния двух заданных строк.

aab
zz

4

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

Напишите программу, определяющую минимальное число ходов, которое должны сделать лягушки, чтобы все лягушки, идущие налево, оказались на левом краю тропинки, а лягушки, идущие направо, – на правом краю тропинки. Ходом считается либо перемещение лягушки на соседнюю пустую кочку, либо последовательность прыжков одной лягушки через других лягушек. Прыжок возможен, если лягушка, через которую происходит прыжок, стоит на соседней кочке, а следующая за ней кочка пустая.

В первой строке входного файла содержится строка, состоящая из символов 'L', 'R' и '.', описывающая текущую ситуацию. Символ 'L' означает кочку с лягушкой, идущей налево, 'R' – кочку с лягушкой, идущей направо, '.' – пустую кочку на тропинке. Строка имеет длину от 2 до 9 символов и содержит как минимум один символ '.'.

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

R.LR.

3

Банки с красками нумеруются числами от 0 до 999999. Краски на склад поступают наборами, в каждом наборе содержится по одной банке для каждого номера краски от `a` до `b` включительно. Время от времени на склад приходит покупатель и забирает все банки с номерами большими или равными `k`. В начале дня склад пустой.

Напишите программу для кладовщика, которая вычисляет количество банок, взятых покупателями.

Во входном файле журнал действий кладовщика. Строка "ADD `a` `b`", где `a` и `b` – целые числа (`0\ ≤\ a\ ≤\ b\ ≤\ 999999`), означает, что на склад поступил набор с номерами банок от `a` до `b`. Строка "DEL `k`", где `k` – целое число (`0\ ≤\ k\ ≤\ 999999`), означает, что пришёл покупатель и забрал все банки с номерами большими или равными `k`. Строка ''END'' является последней строкой в файле и означает конец рабочего дня кладовщика. Количество записей в файле не превышает 2000.

В выходной файл для каждой записи "DEL `k`" в порядке их следования во входном файле вывести строку, содержащую одно число – количество банок, взятых этим покупателем.

ADD 10 20
ADD 5 15
DEL 7
ADD 3 7 
DEL 4
DEL 5
END

20
6
0

Археолог обнаружил документ с расчетами по вычислению поставок в войска Цезаря. Расчеты выглядели как выражения `A+B=C`, где `A`, `B` и `C` – некоторые числа, записанные римскими цифрами. К сожалению археолога, время не пощадило документ и некоторые символы невозможно разобрать. Напишите программу, которая поможет археологу выяснить, какие вычисления были сделаны римским интендантом.

Для записи числа римскими цифрами используются прописные латинские буквы: буква I обозначает 1, V – 5, X – 10, L – 50, C – 100, D – 500, M – 1000. Числа записываются при помощи повторения этих цифр. В правильной записи сначала пишется число тысяч, затем сотен, затем десятков и, наконец, единиц. Во избежание четырёхкратного повторения одной и той же цифры сначала пишется эта цифра, а затем цифра, при вычитании из которой этой цифры получается нужное число единиц, десятков или сотен. (например, IX означает 9, XL – 40). Число 1984 записывается римскими цифрами следующим образом MCMLXXXIV.

В первой строке входного файла содержатся одна строка длиной не более 50 символов, содержащая буквы I, V, X, L, C, D, M и символы '+', '=' и '?'. Символ '?' используется для замены тех символов и цифр, которые оказалось невозможно разобрать. Известно, что слагаемые в выражении были в диапазоне от 1 до 1000 включительно.

В первой строке выходного файла вывести любой вариант вычислений, который соответствует строке во входном файле. Если нет ни одного варианта – вывести сообщение "ERROR" (без кавычек).

XX?X????IV=L???I

XXIX+XXXIV=LXIII