Заочная олимпиада учителей информатики РС(Я)
Перекресток
При организации движения по сложным перекресткам, для того чтобы траектории водителей, выполняющие различные маневры не пересекались, вводят ограничения на возможные маневры водителей, в зависимости от того, по какой полосе движения водитель подъехал к перекрестку. Для этого используется знак «движения по полосам».
Рассмотрим дорогу, подходящую к перекрестку, на котором сходится m дорог. Водитель, подъехавший к перекрестку по этой дороге, потенциально может продолжить свое движение в m различных направлениях – обратно по дороге, по которой он приехал, а также по одной из оставшихся m-1 дорог. Пронумеруем возможные направления числами от 1 до m слева направо с точки зрения подъезжающего водителя, номер 1 получит разворот и возврат по дороге, по которой водитель подъезжал к перекрестку, номер 2 – поворот на самую левую из дорог, и т. д.
Пусть дорога содержит n полос для движения. Пронумеруем полосы от 1 до n слева направо, самая левая получит номер 1, следующая номер 2, и т. д. Знак «движение по полосам» разрешает каждой из полос движение по некоторым из m возможных направлений. При этом должны выполняться следующие условия:
Если с i-й полосы разрешено движение в a-м направлении, а j-й полосы – в b-м направлении, причем i<j, то a<=b; С каждой полосы разрешено движение хотя бы в одном направлении; В каждом направлении разрешено движение хотя бы с одной полосы.Инспекция по безопасности дорожного движения заинтересовалась, а сколько различных знаков «движение по полосам» можно установить перед таким перекрестком. Помогите им найти ответ на этот вопрос.
Формат входного файла
Входной файл содержит два целых числа m и n(2<=m<=50, 1<=n<=15)
Формат выходного файла
В выходной файл выведите одно число – количество возможных знаков «движения по полосам», которые можно установить перед перекрестком.
Примеры
Input. txt | Output. txt |
4 2 | 7 |
В примере возможны следующие варианты знаков «движение по полосам»:
С левой полосы | С правой полосы |
Разворот Разворот Разворот, налево Разворот, налево Разворот, налево, прямо Разворот, налево, прямо Разворот, налево, прямо, направо | Разворот, налево, прямо, направо Налево, прямо, направо Налево, прямо, направо Прямо, направо Прямо, направо Направо Направо |
Небоскребы
В городе есть N небоскребов. Небоскребы стоят подряд на одной улице и пронумерованы от 1 до N в порядке следования. Количество этажей i-ого небоскреба равно Ai.
Для демонстрации города было решено выбрать M небоскребов. Нельзя выбирать подряд идущие небоскребы, т. е. между любыми двумя выбранными небоскребами должен находиться хотя бы один небоскреб. Надо выбрать M небоскребов так, чтобы суммарное количество этажей было наибольшим.
Формат входного файла
В первой строке входного файла содержатся два целых числа N, M – количество небоскребов всего и количество небоскребов, которое требуется (1 ≤ N, M ≤ 1000). В следующей строке N целых чисел A1, A2, …, An – количество этажей для каждого небоскреба (1 ≤ Ai ≤1000000).
Формат выходного файла
Вывести единственное число – суммарное количество этажей выбранных небоскребов. Если выбрать невозможно, напечатать -1.
Примеры входного и выходного файлов
input. txt | output. txt | Примечание |
3 1 1 3 2 | 3 | |
10 5 10 1 1 10 20 12 1 1 1 1 | 34 | |
10 6 1 2 3 4 5 6 7 8 9 10 | -1 | Между выбранными небоскребами должен стоять хотя бы один небоскреб. |
Туристы.
Расстояние между пунктами А и В s км. Из пункта А в пункт В отправляются одновременно 4 туриста. Пешком, на велосипеде, на мопеде и на мотоцикле. Расстояние в t км. пешеход проходит за k1 часов, велосипедист это расстояние проезжает за k2 часа. На мопеде t км. можно проехать за k3 часов и, наконец это расстояние мотоциклист проезжает за 1 час. По пути можно оставить средство передвижения и воспользоваться другим средством передвижения. За какое минимальное время, и каким образом, все путники могут достигнуть пункта В?
Технические требования: k1, k2, k3, s, t и s / t – целые числа. 1 < k3 < k2 < k1.
Выходной файл input. txt состоит из одной строки, в которой, разделенные пробелами находятся числа s, t, k1, k2, k3. В первой строке выходного файла output. txt указывается минимальное время за которое все четверо туристов могут пройти s километров. Во второй строке указывается, за сколько часов каждый турист пройдет t километров. В третей строке указывается время, за которое каждый турист пройдет 2t километров. В четвертой строке указывается время за которое каждый турист пройдет 3t километров и т. д.. В последней строке указывается время за которое каждый турист пройдет s км.
Например, для трех туристов (нет мотоцикла). Если t =30 км. s=60 км. k2=3, k1=5. (мопед проезжает 30 км за один час). Ответ должен быть таким.
input. txt | output. txt |
6 1 3 5 | 6 6 6 |
В случае, если все туристы не могут прийти в пункт В одновременно, нужно вывести ‘no’.
Вычислитель.Инженеры сконструировали робота вычислителя, который некоторое число целое число a умножает на число b или прибавляет к нему число с. Арифметические действия выполняются по модулю m. Со вновь полученными числами выполняются те же операции. Если при этом полученное число совпадет с уже ранее полученным числом, то с этим числом больше арифметических действий не производят. Так как m ≤ 100, то, понятно, что через некоторое время все вычисления закончатся. Надо после того, как вычисления закончились, найти число, которое больше всех получалось при этих вычислениях (если таких чисел несколько – то нужно указать минимальный из них), и, указать минимальный путь получения этого числа из исходного числа а (указать все промежуточные числа).
Технические требования:
В входном файле input. txt единственная строка содержит, разделенные пробелами числа a, b, c, m. Все эти числа положительны и не больше ста. Выходной файл output. txt тоже состоит из одной строки. Первым числом в этой строке является найденное наиболее часто повторяющееся в вычислениях число (если их несколько, то минимальное из них). Затем через пробел пишем число, из которого получилось найденное число, затем через пробел стоит число, из которого получилось предыдущее число и т. д. до тех пор пока не получится исходное число а. Эта цепочка чисел должна быть минимальной по количеству содержащихся в ней чисел из всех возможных аналогичных цепочек.
Пример:
input. txt | output. txt |
3 2 5 10 | 2 6 3 |
Путник.
Путник стоит на берегу реки в точке с координатами (0,U). Река имеет ширину D. Берега реки параллельны друг другу. За рекой в точке с координатами (0,V) растет береза. Путнику надо за кратчайшее время добраться до березы. Скорость путника по земле в K раз больше скорости движения по воде. Укажите координату по оси ОХ точки на другом берегу реки, через которую должен пройти путник. (K>=1; V>=D).
Технические требования: Входной файл ‘input. txt’ состоит из одной строки, в которой, разделенные пробелами находятся переменные K, D, U,V. Ответ надо поместить в файл ‘output. txt’ Точность вычислений не менее 10-9
Пример:
input. txt | output. txt |
1 4 12 12 | 8.0000000000 |
Опять цепочка.
Алексей Попович, где-то нарыл большое число белых и черных бусинок. Теперь у него практически неограниченное число бусинок белого, черного, красного, зеленого и синего цветов.
Сколько различных красивых цепочек длины N он может подарить Василисе Прекрасной? Цепочка, как и раньше, считается красивой, если у каждых 6 подряд лежащих бусинок в цепочке, присутствуют бусинки всех 5-ти цветов.
Технические требования:
Входной файл input. txt содержит единственное число N ≤ 1010000. Выходной файл output. txt содержит единственное число, ответ.
Пример:
input. txt | output. txt |
8 | 8520 |
