Задача "Табло"
Сложность: 20%

На хоккейном стадионе в одном большом городе расположено большое прямоугольное табло. Оно имеет n строк и m столбцов (то есть состоит из n x m ячеек). Во время хоккейного матча это табло служит для отображения счета и времени, прошедшего с начала тайма, а в перерывах на нем показывают различную рекламу.

В связи с этим возникла задача проверки возможности показа на этом табло определенной рекламной заставки. Заставка также, как и табло, имеет размер n строк на m столбцов. Каждая из ячеек заставки окрашена в один из четырех цветов - трех основных: красный - R, зеленый - G, синий - B и черный - .(точка).

Каждая из ячеек табло характеризуется своими цветопередаточными возможностями. Любая из ячеек табло может отображать черный цвет - это соответствует тому, что на нее вообще не подается напряжение. Также каждая из ячеек может отображать некоторое подмножество множества основных цветов. В этой задаче эти подмножества будут кодироваться следующим образом:

0 - ячейка может отображать только черный цвет;
1 - ячейка может отображать только черный и синий цвета;
2 - ячейка может отображать только черный и зеленый цвета;
3 - ячейка может отображать только черный, зеленый и синий цвета;
4 - ячейка может отображать только черный и красный цвета;
5 - ячейка может отображать только черный, красный и синий цвета;
6 - ячейка может отображать только черный, красный и зеленый цвета;
7 - ячейка может отображать только черный, красный, зеленый и синий цвета.
Напишите программу, которая по описанию табло и заставки определяет: возможно ли на табло отобразить эту заставку.

Входные данные
Первая строка входного файла INPUT.TXT содержит целые числа n и m (1 ≤ n, m ≤ 100). Далее идут n строк по m символов каждая - описание заставки. Каждый из символов описания заставки принадлежит множеству {R, G, B, .} . Их значения описаны выше.

После этого идет описание табло. Оно содержит n строк по m чисел, разделенных пробелами. Значения чисел описаны выше.

Выходные данные
В выходной файл OUTPUT.TXT выведите YES, если на табло возможно отобразить заставку и NO - в противном случае.

​​Решение задачи "Табло"

Здесь необходимо использовать некоторый двумерный массив символов A[i][j] для запоминания информации, которую необходимо отбразить на табло. Проще всего использовать для этой цели одномерный массив строк. Здесь можно обойтись без массива для хранения возможностей табло. Сначала нужно считать данные о рекламной заставке в массив A, а затем пробегая по цветопередаточным возможностям табло можно каждую ячейку просто сравнивать с соответствующей ячейкой массива A и анализировать возможность ее отображения. В том случае, когда окажется, что в текущей ячейке информация не может быть отражена, то следует прекратить поиск и вывести NO. Если же такого случая не представится, то по завершении просмотра всех ячеек следует вывести YES.

Остается лишь понять: как определить, может ли цвет C быть отражен в ячейке с цветопередаточной возможностью K. Можно конечно просто рассмотреть каждый возможный случай для C согласно представленной таблице в формулировке задачи:

С='.'. Черный цвет мы можем вывести в любом случае.

С='R'. Красный цвет возможен лишь тогда, когда K больше, чем 3. В противном случае отобразить красный цвет не предосталяется возможным.

С='G'. Зеленый цвет возможен лишь при K=2,3,6,7.

С='B'. Синий цвет возможен лишь при K=1,3,5,7 или проще говоря, когда K - нечетно.

При такой проверке используется много условий. Можно заметить, что значение цветопередаточности в двоичной записи устроено таким образом, что 0й бит отвечает за синий цвет, 1й бит за зеленый и 2й - за красный. Тогда с помощью логической операции and можно проверить возможность использования какого-либо цвета. Например, если 1 and K > 0, то для K возможно отобразить синий цвет, если же 2 and K > 0, то можно отобразить зеленый, для красного же цвета должно выполняться 4 and K > 0. Для простоты можно определить массив C[T], аргументом которого будет цвет, а значением то число, которое необходимо использовать в операции and (конъюнкция, в языке Си это &). Таким образом, в дальнейшем для цвета T достаточно будет проверить значение C[T] and K (кроме черного цвета).

Реализация вышеописанного может быть представлена следующим образом на нашем алгоритмическом языке:

Логическая задача "Улов рыболова"

Возвращаясь с рыбалки домой, рыболов встретил своего приятеля, который поинтересовался его уловом. Но, так как наш рыболов помимо рыбалки был также большим любителем всякого рода загадок, ответил приятелю следующим образом: “Если к количеству пойманной мною рыбы добавить половину улова и еще десяток рыбин, то мой улов составил бы ровно сотню рыб”. Сколько рыбы поймал рыболов?

Ответ на задачу "Улов рыболова"

Решим задачу с ее конца. Отнимем лишние 10 рыб - останется 90 рыб. В число 90 заключены три равные части, из которых две являются действительным уловом, а третья - дополнительной половиной от действительного улова. Следовательно, эта дополнительная половина улова составляет 90:3=30 рыб, а сам улов 30х2=60 рыб.

Задача "Арифметическое выражение"
Сложность: 71%

Требуется вычислить значение арифметического выражения, в записи которого могут использоваться вещественные числа, круглые скобки, пробелы, бинарные операции «+», «-», «*» и «/», а так же функции cos(x) и sin(x). Вычисление следует проводить согласно синтаксису языка Delphi.

Входные данные
Входной файл INPUT.TXT содержит единственную строку, в которой находится запись арифметического выражения. Длина строки не превышает 200 символов. В строке могут содержаться любые символы. Гарантируется, что при корректном вычислении выражения не будет возникать переполнения 6-байтного вещественного типа и деления на ноль.

Выходные данные
В выходной файл OUTPUT.TXT выведите значение заданного арифметического выражения с точностью, не меньше 10-3. В том случае, когда в выражении присутствуют синтаксические ошибки, следует вывести «Error».

Решение задачи "Арифметическое выражение"

Вычисление арифметического выражения – классическая задача, решать которую можно по-разному. Можно использовать алгоритм перевода выражения в постфиксную форму, а затем производить вычисление данного выражения. Но в данном случае придется использовать стек и обрабатывать его вручную. Более просто использовать рекурсивный алгоритм, где стек рекурсии заменит вышеописанный стек. Опишем суть функции Count(s), которая будет возвращать значение арифметического выражения s.

Первоначально следует удалить из s лишние пробелы и затем удалить лишние соответствующие друг другу скобки, расположенные в начале и конце строки. Далее следует справа налево в строке найти в некоторой k-й позиции операцию «+», не находящуюся внутри скобок и разбить выражение на два выражения, которые можно вычислить рекурсивно: count(s) = count(s[1..k-1]) + count(s[k+1..length(s)]). После чего (если «+» не найден) следует повторить данный процесс для операций «-», «*», «/» именно в данном порядке.

Если же в рассматриваемом таким образом выражении операции не найдены, то это либо число либо вызов тригонометрической функции. Сначала следует проверить на функцию: для этого строка должна начинаться либо на ‘cos(‘, либо на ‘sin(’ и заканчиваться на ‘)’. Если начало – это функция, а окончание – не закрывающая скобка, то следует вывести сообщение об ошибке, иначе вычислить выражение в скобках, вызвав count(s[4..length(s)]), и вернуть значение функции от возвращаемого рекурсией значения.

Когда выражение не содержит знаков и функций, то его стоит рассматривать как число, которое следует перевести в числовой вещественный эквивалент, проверив на корректность перевода.

Логическая задача "Флаг на воздушном шаре"

Воздушный шар уносится непрерывным ветром в южном направле­нии. В какую сторону развиваются при этом флаги на его гондоле?

Ответ на задачу "Флаг на воздушном шаре"

Шар, уносимый воздушным течением, находится по отно­шению к окружающему воздуху в покое; поэтому флаги не станут развиваться на ветру ни в какую сторону, а будут свисать, вниз, как в безветрие.

Задача "Раз-два, раз-два"
Сложность: 49%

Для заданного натурального числа N требуется найти число, состоящее только из цифр 1 и 2, которое делилось бы на 2N.

Входные данные
Входной файл INPUT.TXT содержит натуральное число N, не превосходящее 300.

Выходные данные
В выходной файл OUTPUT.TXT выведите искомое число, состоящее не более чем из 10 000 цифр.

Решение задачи "Раз-два, раз-два"

Можно заметить, что для любого натурального N существует число, состоящее из N цифр 1 или 2, которое делится на 2N. Причем, если такое K-значное число делится на 2K, то разместив перед ним 1 или 2 всегда можно получить (K+1)-значное число, делящееся на 2K+1. Откуда очевидным образом вытекает алгоритм поиска нужного числа (динамическое решение): при K=1 мы имеем число 2, далее при увеличении значения K мы будем к предыдущему числу приписывать 1 слева и проверять его делимость на 2K, при положительном исходе будем оставлять 1, иначе заменять ее на 2. Ограничения в задаче позволяют осуществлять проверку делимости числа на 2K с использованием K делений на 2 длинного числа (длинная арифметика).

При прочтении данного решения могут возникать вопросы: как возможно прийти к данному решению и почему утверждение о построении такой последовательности является верным? Обычно, при решении подобных задач полезно попытаться найти какую-либо закономерность, выписав первые элементы искомой последовательности. Для N, меньших 20 это можно сделать "в лоб", простым перебором с проверкой (ведь понадобится перебрать не более 220 чисел). В результате получаемая последовательность (2, 12, 112, 2112, 22112, 122112, 2122112, 12122112, 212122112, ...) приводит к вышеописанной идее.

Используя метод математической индукции, возможно доказать справедливость данного алгоритма решения. Покажем, что для любого натурального N существует число, состоящее из N цифр 1 или 2, которое делится на 2N. Для N=1 решение очевидно, это число 2. Теперь предположим, что для некоторого натурального K данное условие так же выполняется, а это значит, что существует некоторое число X, которое делится на 2K и состоит ровно из K цифр. Нам нужно показать, что всегда возможно приписав слева к числу X цифру 1 или 2, получить число, делящееся на 2K+1 (заметим, что тогда число будет состоять ровно из K+1 цифры). Число X либо делится на число 2K+1, либо не делится. Если деление имеет место быть, то к числу X нужно дописать слева цифру 2 и тогда оно так же будет делиться на 2K+1. Действительно, ведь в результате дописывания двойки мы получим число 210K + X, где оба слагаемых делятся на 2K+1 (первое делится потому, что оно равно 2K+15K, а второе - по предположению), а значит и само число тоже делится. В случае, когда X не делится на 2K+1, необходимо приписать к X слева цифру 1, что приведет к делимости полученного числа на 2K+1. Действительно, полученное число тогда будет равно 10K + X = 2K(5K+Y), здесь X = 2K*Y. В скобках мы имеем сумму нечетных чисел, результатом которой обязательным образом будет четное число, что при умножении на 2K даст число, делящееся на 2K+1, что и требовалось доказать.

Логическая задача "Форма яйца"

Считается, что есть веская причина, по ко­торой у птичьих яиц один конец тупее другого. Что это за причина?

Ответ на задачу "Форма яйца"

Сферические и овальные яйца катились бы по прямой. Асимметрич­ные же яйца, у которых один конец тупее, а другой острее, при скатывании стремятся катиться по кругу. Если яйцо лежит на краю обрыва или в другом ненадежном месте, стрем­ление катиться по кругу, а не по прямой — большое преимущество.

Задача "Игра с монетами"
Сложность: 47%

Гриша и Дима играют в следующую игру: они разложили однокопеечные монетки в стопки (в разных стопках может быть различное количество монет), а стопки расположили на столе перед собой в ряд слева направо. Затем Гриша и Дима по очереди делают ходы. На каждом ходе один из игроков берет слева несколько стопок, не меньше одной, но и не больше, чем перед этим взял его соперник. Первый игрок своим первым ходом берет не более K стопок. Игра заканчивается, когда стопок не остается.

Требуется написать программу, позволяющую вычислить, какое максимальное число монет может получить первый участник после окончания игры, если второй – тоже старается ходить так, чтобы получить как можно больше монет.

Входные данные
Входной файл INPUT.TXT состоит из одной строки, в которой записаны: число стопок N (1 ≤ N ≤ 180), за ним идут N чисел, задающих количество монет в стопках слева направо (количество монет в стопке – не менее 1 и не более 20000), а затем число K, ограничивающее количество стопок, которые первый игрок может взять на первом ходе (1 ≤ K ≤ 80). Все числа в строке разделены пробелом.

Выходные данные
В выходной файл OUTPUT.TXT необходимо вывести одно число – максимальное количество монет, которое заведомо может получить первый игрок, как бы ни играл второй.

​​Решение задачи "Игра с монетами"

Введем обозначения: s[r] − суммарное количество монет в стопках с r-той по n-ю; g[r, m] − максимальное количество монет, которое может получить игрок, если сейчас его ход, при условии что остались стопки с r-той по n-ю, и он может взять не более m стопок. Элементы массива s[1..n] будут использоваться для вычисления элементов массива g[n, k], поэтому его нужно вычислить и сохранить сразу после ввода данных.

Далее вычисляем элементы массива g. Если игрок может взять все оставшиеся стопки, то он должен сделать это, иначе другой игрок возьмет не менее одной стопки из оставшихся стопок, и выигрыш игрока , чей сейчас ход, не будет максимальным. Следовательно, все числа g[r, m], где m ≥ n − r + 1, определены, в том числе все элементы g[n, m]. А именно, g[r, m]=s[r].

Будем находить элементы g[r, m] в порядке убывания r, при условии m < n − r + 1 . В этой ситуации игрок может взять от одной до m стопок. Пусть он взял i стопок. Тогда другой игрок окажется в ситуации (r + i, i) − его ход, разыгрываются стопки с (r + i) − той по n − ю, и можно взять не более i стопок. Он может взять максимальное количество монет, равное g[r + i, i]. Так как в стопках с r-той по n-ю было s[r] монет, то первый игрок , взяв i стопок, получит s[r] − g[r+i, i] монет.

Логическая задача "Переправа"

Имеется круглое глубокое озеро диаметром 200 метров и два дерева, одно из которых растет на берегу у самой воды, другое - по центру озера на небольшом островке. Человеку, который не умеет плавать, нужно перебраться на островок при помощи веревки, длина которой чуть больше 200 метров. Как ему это сделать?

Ответ на задачу "Переправа"

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

Задача "Отрезок и окружности"
Сложность: 58%

На плоскости задана система концентрических окружностей, центры которых находятся в начале координат, а радиусы равны 1, 2, 3, . . . . Также на плоскости задан отрезок, концы которого находятся в точках (x1, y1) и (x2, y2).

Необходимо найти число общих точек этого отрезка и указанной системы окружностей.

Входные данные
Входной файл INPUT.TXT содержит четыре целых числа: x1, y1, x2 и y2. Эти числа не превосходят 103 по абсолютной величине. Заданный отрезок имеет ненулевую длину.

Выходные данные
В выходной файл OUTPUT.TXT выведите одно целое число – количество общих точек.

Решение задачи "Отрезок и окружности"

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

Теперь необходимо свести данную задачу к рассмотренной выше. Для этого необходимо найти на отрезке точку, ближайшую к началу координат. Таким образом, исходный отрезок разбивается на два новых, для которых выполнено условие из простой задачи. Также следует рассмотреть крайний случай, а именно, если ближайшая к (0; 0) точка находится на целом расстоянии от начала координат. В этом случае мы посчитаем это пересечение дважды, поэтому необходимо уменьшить ответ на единицу.

Стоит заметить, что находить саму ближайшую точку нет необходимости. Достаточно найти лишь расстояние до нее.

Логическая задача "Поездки в трамваях"

Вдоль улицы, на которой я проживаю, курсируют трамваи красного и синего цвета, относящиеся к одному и тому же маршруту. Количество тех и других трамваев одинаковое. Красные трамваи, равно как и синие, ходят с одинаковым интервалом времени, составляющим десять минут. В течение дня я совершаю по несколько поездок, причем в самое разное время. Казалось бы, количество поездок в трамваях красного и синего цвета должно быть приблизительно одинаковым с возможным небольшим отклонением. Однако, в силу некоторых обстоятельств, фактическое количество поездок в трамваях красного цвета составляет, чуть ли не 90% от количества всех поездок. Как можно объяснить такое явление?

Ответ на задачу "Поездки в трамваях"

Трамваи одного цвета ходят относительно друг друга с интервалом в десять минут. Между трамваем красного цвета и следующим за ним трамваем синего цвета интервал движения составляет одну минуту, а между трамваем синего цвета и следующим за ним трамваем красного цвета – девять минут.