Шахматная доска состоит из n × m клеток, покрашенных в черный и белый цвет в «шахматном» порядке. При этом клетка в левом нижнем углу доски покрашена в черный цвет. Определите, сколько всего на доске черных клеток. Программа получает на вход два числа n и m, записанных в отдельных строках. Все числа — натуральные, не превосходящие 30 000. Программа должна вывести одно целое число — количество черных клеток на доске.

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

+«Решение»

Если количество клеток на доске четное, например   или , то количество черных  клеток в каждом ряду одинаково и равно половине всех клеток. На первой доске это   клеток, а на второй  

 

Если же общее  количество клеток нечетно, например,   или ,  то количество черных клеток будет на одну больше, т.е. надо посчитать    и добавить единицу.

 

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

Можно обойтись и без 

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

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

Миша впервые попал на Манхэттен. Сейчас он стоит на пересечении авеню номер x1 и улицы номер y1. Ему нужно попасть на перекресток авеню номер x2 и улицы номер y2.
Определите маршрут, который он должен пройти. Программа получает на вход 4 числа: x1, y1, x2, y2, записанных в отдельных строках. Все числа — натуральные, не превышают 103. Начальное и конечное расположение Миши не совпадают.
Программа должна вывести последовательность из латинских заглавных букв, описывающих маршрут, которому должен следовать Миша. Буква «N» обозначает перемещение на один квартал на север, «S» — на юг, «W» — на запад, «E» — на восток. Программа должна вывести самый короткий из всех возможных маршрутов, если же кратчайших маршрутов существует несколько, то программа должна вывести любой из них (но только один).
Программа может выводить последовательность ходов не в одну строку (как в примере), а каждый символ ответа — в отдельной строке (например, если каждый символ ответа выводится при помощи отдельной команды вывода внутри цикла).

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

+«Решение»

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

На рисунке, точка , где находится Миша, соответствует  пересечению авеню номер  и улицы номер . Мише нужно попасть на пересечение  авеню номер  и улицы номер , в точку .

Сравнивая  с   и  с  по знаку, можно понять, в какую сторону необходимо Мише двигаться, а по абсолютной величине разницы  и    «на сколько« надо двигаться. Если разность положительна , то двигаться надо вправо, иначе влево. Если разность положительна , то двигаться надо вверх, иначе вниз.

Программа на Python будет такой:	Программа на Pascal:

Можно решить еще проще! Программа на Python:

Можно не проверять разности координат, зная принцип работы цикла (если цикл должен выполняться отрицательное количество раз, то он вообще выполняться не будет).	В представленном ниже коде, происходит операция умножения строки на число и если число отрицательное — то умножения не произойдет.
Python Задача Манхеттен. Усовершенствованное решение	Python Задача Манхеттен. Элегантное решение

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

Календарь жителей планеты Плюк состоит из N месяцев, каждый месяц состоит ровно из 30 дней, неделя состоит из 7 дней. Особо несчастливыми на планете Плюк считается 13-е число месяца, если оно выпадает на пятницу. Известно, что Новый год на планете Плюк начался в k-й по счету день недели (1-й день недели — понедельник, 2-й — вторник, 3-й — среда, … , 7-й — воскресенье).

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

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

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

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

+«Решение»

Рассмотрим календарь планеты Плюк. Найдем, когда наступит «Пятница 13-го» на примере первых нескольких месяцев. Пусть 1 число попадает на понедельник.

1 месяц		2 месяц		3 месяц		4 месяц		5 месяц

Заменим,  что

 

1 первое число каждого месяца сдвигается на два дня, по сравнению с предыдущим месяцем,

 

2 «пятница 13» случается, когда первый день месяца попадает на воскресенье  — это  день недели.

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

— счетчик пятниц;

«Пятницы 13-го» находятся следующим образом:

пробегаем по всем заданным месяцам (от 1 до N),

проверяем  число на «пятницу» (см.«2»)   ,  учитывая, что в следующем месяце первое число смещается на два дня недели, (см.«1» и календарь)   изменяем       для каждого следующего месяца.

Когда станет большим   (в случае, субботы или воскресенья  — 6 или 7 день недели ), выполнив команду  , получим  или , а таких дней недели  — нет. Поэтому  , если  (или ).

Суммируем число таких «Пятницы 13-го»  в  

 

Программа на Python будет такой:	Программа на Pascal:
Python Задача Календарь	Pascal Задача Календарь

 

 

Эффективное решение и по памяти и по быстродействию.

Если проанализировать календарь, то можно понять, что при 30 дневном месяце, после нахождения первой «пятницы 13», это событие будет повторяться через 7 месяцев (или просто посмотреть на тестовые данные ). Достаточно посчитать, сколько останется таких событий.

Программа на Python:

Python Задача Календарь. Эффективное решение

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

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

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

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

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

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

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

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

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

+«Решение»

Один из  способов решения такой. Создадим  пустую строку  и будем последовательно перебирать символы исходной строки и проверять, является ли он цифрой. Если символ является цифрой, то добавим в конец строки символ «1», иначе добавим символ «0».  Получим один из четырех вариантов вариантов:  «011100», «00111», «001111», «111100», соответствующим номерам первого, второго, третьего или четвертого типа номеров. Из программы выводятся “1”, “2”, “3”, “4” соответственно, или,   в противном случае выводится “0”.

Программа на Python:

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

Задача 5.

Палиндромом называется строка, которая одинаково читается как слева направо, так и справа налево. Рассмотрим все натуральные числа, запись которых в десятичной системе счисления является палиндромом (при этом запись не начинается с нуля). Например, числа 121 и 1331 являются палиндромами, а число 123 — нет. По данному числу N найдите N-e в порядке возрастания число-палиндром.

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

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

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

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

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

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

+«Решение»

Решение на 40 баллов

Для того, чтобы проверить, является ли число палиндромом, преобразуем его десятичную запись в строку, развернем ее в обратном порядке и проверим   две получившиеся строки на равенство.

Программа на Python:

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