1. Кросс-курс (автор-составитель — Брызгалов Е.В., оппонент — Южаков М.А.). 8 баллов.
На Московской Межбанковской Валютной Бирже завершились очередные торги, по итогам которых были определены курсы мировых валют по отношению к российскому рублю.
Требуется написать программу, которая определит кросс-курс двух валют.
Примечания:
Технические требования:
Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT
Ограничение по времени: 3 секунды.
Формат входных данных:
В первой строке содержится одно число N — количество валют.
Далее следует N строк, содержащих название валюты (не более чем 20 букв латинского алфавита)
и через пробел ее курс (в рублях). В последней строке приведены названия двух валют (A и B),
разделенные пробелом.
Формат выходных данных:
Одно число, определяющее кросс-курс валют A и B (курс валюты A в валюте B).
Пример файла входных данных:
3 USD 29.4325 DM 13.7000 FFr 6.3230 USD FFr
Пример файла выходных данных:
4.6548
2. Система счисления Штерна-Броко (идея — Д. Кнут, составитель — Деменев А.Г., оппонент — Брызгалов Е.В.). 12 баллов.
Существует замечательный способ построения всех неотрицательных несократимых дробей m/n, где n и m — взаимно простые целые числа, т.е. не имеющие одинаковых простых сомножителей. Суть способа в том, чтобы начать с двух дробей 0/1 и 1/0, а затем повторить необходимое число раз следующую операцию: вставить (m+m')/(n+n') между двумя соседними дробями m/n и m'/n'.
Всю совокупность вставок можно представить в виде бинарного дерева, называемого деревом Штерна-Броко, начало которого выглядит так:
Каждый узел дерева имеет вид (m+m')/(n+n'), где m/n — ближайший предок сверху слева, а m'/n' — сверху справа.
Можно воспользоваться символами L и R для идентификации левой и правой ветви при продвижении вниз по дереву от корня, дроби 1/1, к некоторой определенной дроби. Тогда каждая положительная дробь получает единственное представление в виде строки состоящей из символов "R" и "L" (дроби 1/1 соответствует пустая строка). Такое представление положительных рациональных чисел назовем системой счисления Штерна-Броко.
Требуется написать программу, которая по заданному числу, записанному в системе счисления Штерна-Броко, выведет соответствующую дробь.
Примечания:
1) длина входной строки — не более 1000 символов;
2) числитель и знаменатель дроби не превосходят 2000000000.
Технические требования:
Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT
Ограничение по времени: 5 секунд.
Формат входных данных:
В единственной строке заданное число, записанное в системе счисления Штерна-Броко.
Формат выходных данных:
В единственной строке заданное число, записанное в виде рациональной дроби, где числитель отделен от знаменателя символом "/".
Пример файла входных данных:
LRRL
Пример файла выходных данных:
5/7
3. Ещё одна последовательность (составитель — Гладков В.П., оппонент — Брызгалов Е.В.). 20 баллов.
В последовательности цифр а1, а2, а3, … каждый член, начиная с четвёртого, равен последней цифре суммы трёх предыдущих.
Требуется написать программу, которая по заданным а1, а2, а3 определяет аn, где n <= 1000000000.
Технические требования:
Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT
Ограничение по времени: 5 секунд.
Формат входных данных:
Входной файл INPUT.TXT содержит две строки. В первой строке заданы три цифры а1, а2, а3, разделённые одним пробелом.
Во второй строке — одно число n.
Формат выходных данных:
Выходной файл OUTPUT.TXT содержит одну искомую цифру.
Пример файла входных данных:
2 3 6 1000000000
Пример файла выходных данных:
7
4. Следующее слово (составитель — Гладков В.П., оппонент — Еремин Е.А.). 25 баллов.
Задаётся некоторое русское слово, длина которого не превышает 80 символов, например ФАРА. Из всех его букв составляются все возможные другие слова, может быть и бессмысленные, например, ААРФ, ААФР, АРАФ, АРФА, …, ФРАА.
Требуется написать программу, которая по заданному слову строит непосредственно следующее за ним по алфавиту слово, состоящее из тех же букв, что и заданное.
Примечание: слова содержат только заглавные русские буквы.
Технические требования:
Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT
Ограничение по времени: 5 секунд.
Формат входных данных:
Входной файл INPUT.TXT содержит одно слово, состоящее не более чем из 80 заглавных русских букв.
Формат выходных данных:
Выходной файл OUTPUT.TXT содержит одно слово, непосредственно следующее в алфавитном порядке за заданным, или слово “нет”, написанное малыми русскими буквами, если нужного слова найти не удаётся.
Пример 1 файла входных данных:
АРАФ
Пример 1 файла выходных данных:
АРФА
Пример 2 файла входных данных:
Я
Пример 2 файла выходных данных:
нет
5. Дроби (идея — Шестаков А.П., составитель — Брызгалов Е.В., оппонент — Каганов И.В.). 35 баллов.
Требуется написать программу, которая выводит в порядке возрастания все правильные несократимые дроби, знаменатели которых не превосходят N (2 <= N <= 500).
Технические требования:
Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT
Ограничение по времени: 10 секунд.
Формат входных данных:
На входе одна строка, содержащая натуральное число N.
Формат выходных данных:
Несколько строк, каждая из которых содержит ровно одну дробь. Дробь записывается как два числа (числитель и знаменатель), разделенные символом "/" (знак деления)
Пример файла входных данных:
4
Пример файла выходных данных:
1/4 1/3 1/2 2/3 3/4
© Пермский областной Оргкомитет олимпиад школьников по информатике, 2001