Школьный тур олимпиады по информатике

ОЛИМПИАДА ПО ИНФОРМАТИКЕ. ШКОЛЬНЫЙ ЭТАП

9 - 11 КЛАССЫ

Задача 1. Шахматная доска

Шахматная доска состоит из n × m клеток, покрашенных в черный и белый цвет в

«шахматном» порядке. При этом клетка в левом нижнем углу доски покрашена в черный цвет. Определите, сколько всего на доске черных клеток.

Программа получает на вход два числа n и m, записанных в отдельных строках. Все числа — натуральные, не превосходящие 30 000.

Программа должна вывести одно целое число — количество черных клеток на доске.

Пример входных и выходных данных

_{Ввод Вывод}

3 6

⁴

Система оценивания

Решение, правильно работающее только для случаев, когда входные числа не превосходят 10, будет оцениваться в 40 баллов.

Задача 2. Манхэттен

Кварталы Манхэттена состоят из авеню, направленных с юга на север и улиц, направленных с запада на восток. Все улицы и авеню пронумерованы числами, начиная с 1 подряд (первая улица, вторая улица, третья улица и т. д.). Передвигаться можно только по улицами или по авеню.

_{Третья улица}

_N

авеню

авеню

авеню

авеню

Вторая улица _{W E}

Четвертая

_S

Первая

Вторая

Третья

Первая улица

Миша впервые попал на Манхэттен. Сейчас он стоит на пересечении авеню номер x₁ и улицы номер y₁. Ему нужно попасть на перекресток авеню номер x₂ и улицы номер y₂. Определите маршрут, который он должен пройти.

Программа получает на вход 4 числа: x₁, y₁, x₂, y₂, записанных в отдельных строках. Все числа — натуральные, не превышают 10³. Начальное и конечное расположение Миши не совпадают.

Программа должна вывести последовательность из латинских заглавных букв, описывающих маршрут, которому должен следовать Миша. Буква «N» обозначает перемещение на один квартал на север, «S» — на юг, «W» — на запад, «E» — на восток. Программа должна вывести самый короткий из всех возможных маршрутов, если же кратчайших маршрутов существует несколько, то программа должна вывести любой из них (но только один).

Программа может выводить последовательность ходов не в одну строку (как в примере), а каждый символ ответа — в отдельной строке (например, если каждый символ ответа выводится при помощи отдельной команды вывода внутри цикла).

Пример входных и выходных данных

_{Ввод Вывод Примечание}

^{1 EEESS} Миша стоит на пересечении первой авеню и третьей улицы и

³ должен попасть на пересечение четвертой авеню и первой

⁴ улицы. Ему нужно пройти три квартала на восток и два

¹ квартала на юг. Возможны и другие ответы, например,

«SSEEE», «ESESE» и прочие. Возможен вывод ответа не в одну строку, а каждый символ ответа — в отдельной строке.

Задача 3. Пятница, 13-е

Календарь жителей планеты Плюк состоит из N месяцев, каждый месяц состоит ровно из 30 дней, неделя состоит из 7 дней. Особо несчастливыми на планете Плюк считается 13-е число месяца, если оно выпадает на пятницу.

Известно, что Новый год на планете Плюк начался в k-й по счету день недели

(1-й день недели — понедельник, 2-й — вторник, 3-й — среда, … , 7-й — воскресенье).

Определите, сколько в этом году на планете Плюк будет особо несчастливых пятниц, 13-е.

Программа получает на вход два натуральных числа, записанных в отдельных строках. Первое число — количество месяцев в календаре планеты Плюк N, не превосходящее 10⁹. Второе число — номер дня недели, на который приходится первое число первого месяца нового года, может принимать значения от 1 до 7.

Программа должна вывести единственное натуральное число — количество несчастливых дней в этом году.

Пример входных и выходных данных

_{Ввод Вывод Примечание}

^{12 2} На 13-е число будут приходиться пятницы четверого

¹ _{и одиннадцатого месяцев.}

Система оценивания

Решение, правильно работающее только для случаев, когда N не превосходит 100, будет оцениваться в 60 баллов.

Задача 4. Автомобильные номера

В Российской Федерации на разных видах транспортных средств устанавливаются разные по формату регистрационные знаки («автомобильные номера»). Вот пример нескольких возможных форматов регистрационных знаков.

В этой задаче «буквой» может быть любая заглавная буква латинского алфавита. Напишите программу, которые по регистрационному знаку определяет его тип или

определяет, что регистрационный знак некорректен.

Программа получает на вход три строки текста, каждая строка содержит один образец регистрационного знака (возможно, некорректный). Каждый образец содержит от 1 до 10 символов, являющихся цифрами и заглавными латинскими буквами (других символов во входных данных быть не может).

Программа должна вывести для каждого образца число, соответствующее типу транспортного средства, как в приведенной таблице, то есть 1 — для частных транспортных средств, 2 — для общественного транспорта, 3 — для прицепов, 4 — для мотоциклов. Если номерной знак некорректен (не подходит ни к одному из указанных типов), то необходимо вывести число 0. Каждое число необходимо выводить в отдельной строке.

Пример входных и выходных данных

_{Ввод Вывод}

Y019KM 1

A9999 0

OH2645 3

_{Система оценивания}

Решение, правильно работающее только в тех случаях, когда все регистрационные знаки корректны (относятся к одному из четырех типов), будет оцениваться в 40 баллов.

Задача 5. Числа-палиндромы

Палиндромом называется строка, которая одинаково читается как слева направо, так и справа налево. Рассмотрим все натуральные числа, запись которых в десятичной системе счисления является палиндромом (при этом запись не начинается с нуля). Например, числа

121 и 1331 являются палиндромами, а число 123 — нет. По данному числу N найдите N-e в порядке возрастания число-палиндром.

Программа получает на вход одно натуральное число N, не превосходящее 100 000. Программа должна вывести одно натуральное число — N-е в порядке возрастания

число-палиндром.

Пример входных и выходных данных

Ввод Вывод

20 111

Система оценивания

Решение, правильно работающее только в тех случаях, когда N не превосходит 100, будет оцениваться в 20 баллов.

Решение, правильно работающее только в тех случаях, когда N не превосходит 1000, будет оцениваться в 40 баллов.