Задачи олимпиады "Школьная олимпиада по Красноярскому краю, 9-11 классы"
Задача A. Сороконожка
(Время: 1 сек. Память: 16 Мб Баллы: 100)
У сороконожки 40 левых ножек и 40 правых ножек. Под кроватью у сороконожки A левых тапочек и B правых тапочек. Сороконожка, просыпаясь, надевает тапочки. Для этого она засовывает под кровать первую левую ножку и надевает первый попавшийся тапочек, тратя на это одну секунду. Если тапочек оказывается левым, то она переходит ко второй левой ножке. Если же он оказывается правым, она переодевает его на какую-нибудь необутую правую ножку, тратя ещё одну секунду, то есть всего на такой тапочек уходит две секунды. Если все правые ножки уже обуты, то она снимает тапочек и кидает его в угол комнаты, тратя на это одну секунду, то есть на такой тапочек сороконожка тратит также две секунды. Процесс продолжается до тех пор, пока все левые ножки не окажутся в левых тапочках. Затем сороконожка аналогичным образом начинает надевать правые тапочки, продолжая до тех пор, пока не будут обуты все правые ножки.
Сегодня сороконожка встала не с той ножки, поэтому она готовится к худшему. Несмотря на это, она, как обычно, начинает обуваться с левой ножки. Сколько секунд понадобится сороконожке на утреннее обувание в худшем случае?
Входные данные
Входной файл INPUT.TXT содержит целые числа A и B (40 ≤ A, B ≤ 1018).
Выходные данные
В выходной файл OUTPUT.TXT выведите: сколько секунд понадобится в худшем случае сороконожке на утреннее обувание.
Пример
№
INPUT.TXT
OUTPUT.TXT
1
40 40
120
Задача B. Сверхстепень
(Время: 1 сек. Память: 16 Мб Баллы: 100)
Назовем значение выражения 22n n-ой сверхстепенью числа 2. Таким образом, например, третья сверхстепень числа 2 равна 223 = 28 = 256.
Ваша задача – вычислить n-ую сверхстепень двойки по модулю m.
Входные данные
Входной файл INPUT.TXT содержит два целых числа: n (0 ≤ n ≤ 105) и m (2 ≤ m ≤ 104).
Выходные данные
В выходной файл OUTPUT.TXT выведите ответ на задачу.
Примеры
№
INPUT.TXT
OUTPUT.TXT
1
3 1000
256
2
10 10
6
Задача C. Флаги
(Время: 1 сек. Память: 16 Мб Баллы: 100)
В День флага России владелец магазина решил украсить свою витрину полосками ткани белого, синего и красного цветов. Он хочет, чтобы выполнялись следующие условия:
Полоски одного цвета не должны располагаться рядом друг с другом.
Синяя полоска может быть расположена только между белой и красной или между красной и белой.
Определите количество способов выполнить желание владельца магазина. Например, для N = 3 возможны следующие варианты:
Входные данные
Входной файл INPUT.TXT содержит натуральное число N – количество полосок (N ≤ 92).
Выходные данные
В выходной файл OUTPUT.TXT выведите целое число – количество способов украсить витрину магазина.
Примеры
№
INPUT.TXT
OUTPUT.TXT
1
1
2
2
3
4
Задача D. Ладья в лабиринте
(Время: 1 сек. Память: 32 Мб Баллы: 100)
Ладья – это шахматная фигура, которая за один ход может переместиться на любое количество клеток по горизонтали или вертикали. При этом она не может «перепрыгивать» через стоящие на ее пути фигуры.
Вася недавно соорудил на шахматной доске своеобразный лабиринт, поставив в некоторые клетки доски пешки (самые «слабые» шахматные фигуры). Теперь он хочет знать, за какое минимальное количество ходов ладья может добраться из одной клетки в другую, перемещаясь по свободным клеткам доски.
Он размышляет над этим вопросом уже несколько дней, однако найти ответ не может. Поэтому он решил обратиться за помощью к Вам. Напишите программу, находящую ответ на Васину задачу.
Входные данные
Первая строка входного файла INPUT.TXT содержит два натуральных числа: n и m (1 ≤ n, m ≤ 500) – размеры лабиринта.
Каждая из последующих n строк содержит m символов. j-ый символ i-ой из этих строк соответствует клетке с координатами (i, j). Он равен «.» (точка), если клетка пуста, «P», если занята пешкой, «S», если это начальная клетка для ладьи, и «F», если это конечная клетка.
Выходные данные
В выходной файл OUTPUT.TXT выведите минимальное количество ходов, требуемое ладье для того, чтобы из начальной клетки попасть в конечную. Если конечная клетка недостижима из начальной выведите -1.
