Задачи олимпиады "1й тур школьной олимпиады по Красноярскому краю"
Задача A. Неглухой телефон
(Время: 1 сек. Память: 16 Мб Баллы: 100)
Возможно, что Вы когда то играли в игру «Глухой телефон», либо слышали о ней. В этой игре участникам приходится передавать информацию друг другу различными способами: словесно, образно, бывает даже приходится писать левой рукой текст, который другой участник команды должен будет прочитать. Так же известно, что практически никогда передаваемая информация не доходит до конечного адресата. Обозначим за Fi(x) функцию, которая преобразует текст передаваемой информации x в ту, которую получит участник i+1 от участника i. Тогда последний n-й участник получит данные y, которые будут выражаться следующей формулой:
y = Fn-1(Fn-2(…F2(F1(x))))
Но Вам необходимо исключить какие-либо внешние факторы, которые могут исказить исходную информацию и Вы должны реализовать программу «неглухой телефон», которая сможет безошибочно доставлять исходные данные, т.е. в нашем случае функция Fi(x) = x для всех i от 1 до n-1.
Входные данные
В единственной строке входного файла INPUT.TXT записано натуральное число от 1 до 100.
Выходные данные
В выходной файл OUTPUT.TXT нужно вывести в точности то же число, которое задано во входном файле.
Пример
№
INPUT.TXT
OUTPUT.TXT
1
5
5
Задача B. День программиста
(Время: 1 сек. Память: 16 Мб Баллы: 100)
День программиста отмечается в 255-й день года (при этом 1 января считается нулевым днем).
Требуется написать программу, которая определит дату (месяц и число григорианского календаря), на которую приходится День программиста в заданном году.
В григорианском календаре високосным является:
год, номер которого делится нацело на 400
год, номер которого делится на 4, но не делится на 100
Входные данные
В единственной строке входного файла INPUT.TXT записано целое число от 1 до 9999 включительно, которое обозначает номер года нашей эры.
Выходные данные
В единственную строку выходного файла OUTPUT.TXT нужно вывести дату Дня программиста в формате DD/MM/YYYY, где DD — число, MM — номер месяца (01 — январь, 02 — февраль, ..., 12 — декабрь), YYYY — год в десятичной записи.
Примеры
№
INPUT.TXT
OUTPUT.TXT
1
2000
12/09/2000
2
2009
13/09/2009
Задача C. Таблица умножения
(Время: 1 сек. Память: 16 Мб Баллы: 100)
Большой любитель математики Вова решил повесить у себя в комнате таблицу умножения. После некоторых раздумий он обнаружил, что обычная таблица умножения 10 на 10 уже не популярна в наши дни. Он решил повесить у себя в комнате таблицу N на M. Представив себе эту таблицу, Вова задался вопросом - сколько раз в ней встречается каждая из цифр от 0 до 9?
И прежде чем нарисовать эту таблицу Вова попросил вас написать программу, которая даст ответ на его вопрос.
Как известно, в таблице умножения на пересечении строки i и столбца j записано число i∙j.
Входные данные
Входной файл INPUT.TXT состоит из единственной строки, на которой через пробел записаны два натуральных числа N и M (1 ≤ N, M ≤ 1000).
Выходные данные
Выходной файл OUTPUT.TXT должен состоять из десяти строк. На строке i выведите количество раз, которое Вове придется нарисовать цифру i - 1.
Пример
№
INPUT.TXT
OUTPUT.TXT
1
10 10
28 24 27 15
23 15 17 8 15 6
Задача D. Количество путей в лабиринте
(Время: 1 сек. Память: 16 Мб Баллы: 100)
Карта лабиринта представляет собой квадратное поле размером N×N. Некоторые квадраты этого поля запрещены для прохождения. Шаг в лабиринте – перемещение из одной разрешенной клетки к другой разрешенной клетке, смежной с первой по стороне. Путь – это некоторая последовательность таких шагов. При этом каждую клетку, включая начальную и конечную, можно посещать несколько раз.
Требуется написать программу, которая подсчитает количество различных путей из клетки (1, 1) в клетку (N, N) ровно за K шагов (то есть оказаться в клетке (N, N) после K-го шага).
Входные данные
Входной файл INPUT.TXT содержит в первой строке числа N и K, разделенные пробелом (1 < N ≤ 15, 0 < K ≤ 30). Следующие N строк, по N символов в каждой, содержат карту лабиринта, начиная с клетки (1, 1). Символ «0» означает не запрещенную для прохождения клетку, а символ «1» - запрещенную. Начальная и конечная клетки всегда разрешены для прохождения.
Выходные данные
Выходной файл OUTPUT.TXT должен содержать количество возможных различных путей длины K. Во всех тестах это значение не будет превышать 2147483647.
