1. Сосчитай (составитель — Гладков В.П., оппонент — Еремин Е.А.). 10 баллов.
Требуется написать программу, находящую все возможные различные упорядоченные пары A и B по исходным данным C и D, такие, что A + B = C, A * B = D. A, B, C, D — целые числа, не превосходящие по модулю 30000.
Технические требования:
Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT
Ограничение по времени: 5 секунд.
Формат входных данных:
В единственной строке задано через пробел два числа — C и D.
Формат выходных данных:
Каждая строка представляет собой пару чисел A и B, разделенных одним пробелом. Строки упорядочены в порядке возрастания первого числа пары. В последней строке выводится одно число — количество найденных решений.
Пример файла входных данных:
–3 2
Пример файла выходных данных:
–2 –1 –1 –2 2
2. Цифровой корень (составитель — Брызгалов Е.В., оппонент — Еремин Е.А.). 20 баллов.
Рассмотрим произвольное натуральное число и найдем сумму его цифр, затем сумму цифр полученного числа и так далее, пока не получим однозначное число. Назовем это число цифровым корнем.
Требуется написать программу, которая для заданного N (N<10100) находит его цифровой корень.
Технические требования:
Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT
Ограничение времени: 5 секунд.
Формат входных данных:
одна строка, содержащая натуральное число N.
Формат выходных данных:
одна строка, содержащая цифровой корень числа N.
Пример файла входных данных:
247
Пример файла входных данных:
4
3. Вращение слова (составитель — Гладков В.П., оппонент — Деменев А.Г.). 35 баллов.
Требуется написать программу, которая должна напечатать слово, полученное из исходного циклическим сдвигом его на N символов влево. Будем называть словом любую последовательность букв латинского алфавита A-Z, a-z. На входе программы задаётся слово длины L < 80 и натуральное число N < 10100. При циклическом сдвиге на каждом шагу буква слова, стоящая на первом месте, перемещается в конец.
Технические требования:
Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT
Ограничение по времени: 5 секунд.
Формат входных данных:
В первой строке входного файла задано число N. Во второй — исходное слово.
Формат выходных данных:
В выходном файле одна строка, содержащая полученное слово.
Пример файла входных данных:
3 Computer
Пример файла выходных данных:
puterCom
4. Маршрут кузнечика (составитель — Брызгалов Е.В., оппонент — Гладков В.П.). 35 баллов.
На левом конце линейки (деление ноль) длиной N сантиметров сидит кузнечик, который хочет добраться до ее правого конца (деление N). Кузнечик может совершать прыжки только определенной длины, не превосходящие N, и только вперед.
Требуется написать программу, которая подсчитывает число различных маршрутов кузнечика из начального положения в конечное.
Примечания:
Технические требования:
Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT
Ограничение времени: 5 секунд.
Формат входных данных:
первая строка — числа N и M, разделенные пробелом;
вторая строка — M натуральных чисел, разделённых пробелом, каждое из которых показывает длину возможного прыжка. Ни одно из чисел не превосходит N.
Формат выходных данных:
единственная строка содержит число различных маршрутов S.
Пример файла входных данных:
3 2 1 2
Пример файла выходных данных:
3
5. Восстановление последовательности (составитель — Гладков В.П., оппонент — Брызгалов Е.В.). 40 баллов.
Назовём фотографией последовательности чисел a1, a2, ..., an последовательность чисел b1, b2, ..., bn, bi = |{j|j < i, aj > ai}|, т.е. каждое число bi из новой последовательности равно количеству чисел старой последовательности, которые больше чем ai, но имеют меньший номер (стоят перед ai).
Требуется написать программу, которая по заданной фотографии последовательности чисел восстановит исходную последовательность, являющуюся некоторой перестановкой отрезка натурального ряда чисел от 1 до N (1 <= N <= 15).
Примечания:
Технические требования:
Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT
Ограничение по времени: 5 секунд.
Формат входных данных:
в первой строке входного файла содержится N, в следующей строке содержатся N чисел, являющихся фотографией последовательности чисел. Числа во входном файле разделены пробелами.
Формат выходных данных:
в выходном файле одна строка, содержащая исходную последовательность чисел. Числа разделены пробелами.
Пример файла входных данных:
0 1 2 0 1
Пример файла выходных данных:
3 2 1 5 4
6. Инверсии в ДНК (составитель — Брызгалов Е.В., оппонент — Каганов И.В.). 60 баллов.
Вы знаете, что любая молекула ДНК представляет собой комбинацию четырех основных элементов — азотистых оснований — аденина (А), гуанина (Г), цитозина (Ц) и тимина (Т). В современной генетике существует понятие “инверсии гена”, когда в цепочке ДНК ее фрагмент обращается на 180°. Например, фрагмент …ЦГТТЦАГ… после инверсии выделенного фрагмента превратится в …ЦГЦТТАГ…
Требуется написать программу, которая для двух фрагментов ДНК определит минимальное число инверсий, необходимое для перевода одного фрагмента в другой.
Технические требования:
Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT
Ограничение времени: 10 секунд.
Формат входных данных:
две строки, каждая из которых содержит фрагмент ДНК. Длины фрагментов одинаковы и не превосходят 8.
Формат выходных данных:
одна строка, содержащая минимально необходимое число инверсий. Если такого способа нет, то вывести –1.
Пример 1 файла входных данных:
АГЦТАГЦТ ААГГЦЦТТ
Пример 1 файла выходных данных:
3
Пример 2 файла входных данных:
АГЦТАГЦТ АААААААА
Пример 2 файла выходных данных:
–1
© Пермский областной Оргкомитет олимпиад школьников по информатике, 2001; А.Г. Деменев