Информатика

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

В ряд выписаны n чисел. Требуется поставить между каждой парой соседних чисел один из знаков "+" или "×" таким образом, чтобы значение получившегося выражения было как можно больше. Использовать скобки не разрешается.

Например, для последовательности чисел 1, 2, 3, 1, 2, 3 оптимально расставить знаки следующим образом: 1 + 2 × 3 × 1 × 2 × 3. Значение выражения в этом случае равно 37.

Входные данные
В первой строке вводится число n (2 <= n <= 200000). Вторая строка содержит n целых чисел - числа, между которыми следует расставить знаки. Все числа находятся в диапазоне от 0 до 10⁹.

Выходные данные
Выведите оптимальное выражение. В качестве знака "×" выводите символ "*" (звездочку). Если оптимальных решений несколько, выведите любое из них.

Почти все Королевство Байтленд покрыто лесами и реками. Малые реки сливаются в более крупные реки, которые, в свою очередь, сливаются друг с другом; в конечном счете, все реки сливаются вместе в одну большую реку. Большая река впадает в море вблизи города Байттаун.

В Байтленде имеется n лесозаготовительных поселков, каждый из которых расположен вблизи какой-либо реки. В настоящее время в Байттауне находится большая пилорама, которая обрабатывает все деревья, срубленные в Королевстве. Деревья сплавляются вниз по рекам от поселков, где они срублены, к пилораме в Байттауне. Король Байтленда решил поставить k дополнительных пилорам в поселках, чтобы уменьшить стоимость сплава деревьев. После установки пилорам деревья не обязательно должны сплавляться в Байттаун, а могут быть обработаны на ближайшей пилораме, находящейся ниже по течению рек. Очевидно, что деревья, срубленные в окрестности поселка с пилорамой, вообще не сплавляются по рекам.

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

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

Задание
Напишите программу, которая:
<> * читает из стандартного ввода количество поселков, количество дополнительных пилорам, которые будут установлены, количество срубленных в каждом поселке деревьев и описание рек,
*вычисляет минимальную стоимость сплава деревьев после установки дополнительных пилорам,
*выводит результат в стандартный вывод.

Входные данные
Первая строка входных данных содержит два целых числа: n — количество поселков, не считая Байттауна (2 ≤ n ≤ 100), и k
 — количество дополнительных пилорам, которые будут установлены (1 ≤ k ≤ 50 и k ≤ n). Поселки нумеруются числами 1 , 2 ,...., n , а Байттаун имеет номер 0.

Каждая из последующих n строк содержит три целых числа, разделенных одним пробелом. Строка i + 1 содержит:

w_i — количество деревьев, срубаемых в поселке i за год (0 ≤ w_i ≤ 10 000),
v_i — ближайший поселок (либо Байттаун) вниз по реке от поселка i (0 ≤ v_i ≤ n),
d_i — расстояние (в километрах) по реке от поселка i до поселка v_i (1 ≤ d_i ≤ 10 000).
Гарантируется, что суммарная стоимость сплава всех деревьев к пилораме в Байттауне не превосходит 2 000 000 000 центов в год.
В 50% тестов число n не превосходит 20.

Выходные данные
Первая и единственная строка выходных данных должна содержать одно целое число: минимальную стоимость сплава (в центах).

Пояснения


Рисунок сверху иллюстрирует входные данные примера. Номера поселков указаны внутри кругов. Числа под кругами обозначают количество деревьев, срубаемых вблизи данного поселка. Числа над стрелками указывают длины рек.

Пилорамы должны быть установлены в поселках 2 и 3.

Вы можете предполагать, что суммарное время работы библиотеки в процессе тестирования не будет превышать 4 сек.

Загрузить библиотеку для тестирования

Рассмотрим игру для двух игроков. Игрокам дан прямоугольник размером x × y (где x и y — положительные целые числа). Игроки ходят по очереди. Ход состоит в разделении прямоугольника на два прямоугольника одним горизонтальным или вертикальным разрезом. Полученные прямоугольники должны иметь положительные целочисленные размеры.


                  Возможные разрезы прямоугольника размером 4 × 3.

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

Ваша задача — написать программу, которая бы играла в игру с прямоугольниками и выигрывала. Для того чтобы играть, программа должна использовать специальную библиотеку. В библиотеке есть функции dimension_x() и dimension_y(), возвращающие размеры прямоугольника. Начальные размеры прямоугольника — целые числа от 1 до 100 000 000. Как минимум один из размеров больше 1. К тому же, в 50% тестов размеры прямоугольника не будут превышать 25.

В библиотеке есть также процедура cut(dir, position), которая должна вызываться вашей программой, чтобы сделать ход. Параметры dir и position описывают направление и позицию разреза соответственно. Параметр dir может принимать одно из двух значений: vertical и horizontal. Если dir = vertical, то проводится вертикальный разрез, а параметр position указывает x - координату разреза, как показано на рисунке выше. При этом вы должны гарантировать выполнение неравенства 1 ≤ position  ≤ dimension_x()− 1. Если dir = horizontal, то проводится горизонтальный разрез, а параметр position указывает y ? координату разреза. При этом, вы должны гарантировать выполнение неравенства 1 ≤ position  ≤ dimension_y()− 1.

После запуска вашей программы она будет играть за одного из игроков. Ваша программа ходит первой, она должна разрезать исходный прямоугольник. Когда ваша программа вызывает процедуру cut, ваш ход записывается и управление передается программе соперника. После хода соперника управление возвращается вашей программе. Значения, которые возвращаются функциями dimension_x() и dimension_y(), будут отражать результат вашего хода и хода соперника. Как только ваша программа выигрывает, проигрывает или делает неправильный ход, ее исполнение будет прервано. Прерывание вашей программы — это автоматический процесс, так что ваша программа должна продолжать делать столько ходов, сколько возможно до автоматического прерывания ее исполнения. Вы можете предполагать, что для предложенных входных данных всегда существует выигрышная стратегия для вашей программы.

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

Экспериментирование

Для того, чтобы дать вам возможность поэкспериментировать с библиотекой, в ваше распоряжение предоставлены примеры библиотек: их исходные тексты находятся в файлах preclib.pas, creclib.c и creclib.h . Эти библиотеки вы можете взять по адресу: http :// contest / . Они реализуют очень простую стратегию. Когда вы запустите вашу программу, она будет играть против этих простых соперников. Вы можете изменять их, чтобы протестировать вашу программу с лучшими соперниками. Следует учесть, что во время тестирования после окончания тура, ваша программа будет играть против другого соперника.

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

Если вы модифицируете часть implementation библиотеки preclib.pas, пожалуйста, перекомпилируйте её, используя команду ppc386 -O2 preclib.pas. Эта команда создаст файлы preclib.o и preclib.ppu. Эти файлы необходимы для компиляции вашей программы и должны быть в помещены в каталог, где находится ваша программа. Пожалуйста, не модифицируйте часть interface библиотеки preclib.pas.

Если вы модифицируете библиотеку creclib.c, пожалуйста, не забудьте поместить ее вместе с creclib.h в каталог, где находится ваша программа, — они необходимы для компиляции. Пожалуйста, не модифицируйте файл creclib.h.

В ваше распоряжение также предоставляются две простые программы, которые иллюстрируют использование библиотек crec.c и prec.pas. Пожалуйста, помните, что эти программы не являются правильными решениями. Вы можете откомпилировать их, используя такие команды:

gcc -O2 -static crec.c creclib.c -lm
g++ -O2 -static crec.c creclib.c -lm
ppc386 -O2 -XS prec.pas

Библиотеки

В ваше распоряжение предоставлены библиотеки, которые обеспечивают следующую функциональность:

Библиотека для FreePascal (preclib.ppu, preclib.o)
type direction = (vertical, horizontal);
function dimension_x(): longint;
function dimension_y(): longint;
procedure cut(dir: direction; position: longint);

 
Включите следующий оператор в ваш исходный файл rec.pas:
uses preclib;
Чтобы откомпилировать вашу программу, скопируйте файлы preclib.o и reclib.ppu в каталог, где находится ваш исходный файл, и выполните следующую команду:
ppc386 -O2 -XS rec.pas
Файл prec.pas является примером использования библиотеки preclib.

Библиотека для GNU C/C++ (creclib.h, creclib.c)

typedef enum __direction {vertical, horizontal} direction;
int dimension_x();
int dimension_y();
void cut(direction dir, int position);



Включите следующий оператор в ваш исходный файл (rec.c или rec.cpp):
#include ”creclib.h”
Чтобы откомпилировать вашу программу, скопируйте файлы creclib.c и creclib.h в каталог, где находится ваш исходный файл, и выполните следующую команду:
gcc -O2 -static rec.c creclib.c –lm
или:
g++ -O2 -static rec.cpp creclib.c –lm
Файл crec.c является примером использования библиотеки в C.
Пример взаимодействия

Ниже приведен пример взаимодействия вашей программы с библиотекой. Он показывает, как может проходить игра. Игра начинается с прямоугольника размером 4 × 3. Существует выигрышная стратегия для этого случая.
 

Ваша программа вызывает	Что происходит
dimension_x()	возвращает 4
dimension_y()	возвращает 3
cut(vertical, 1)	ваш разрез записывается, и прямоугольник размером 3 × 3 передается вашему сопернику, который разрезает его и получается прямоугольник размером 3 × 2; после этого управление передается вашей программе
dimension_x()	возвращает 3
dimension_y()	возвращает 2
cut(horizontal, 1)	ваш разрез записывается, и прямоугольник размером 3 × 1 передается вашему сопернику, который разрезает его и получается прямоугольник размером 2 × 1; после этого управление передается вашей программе
dimension_x()	возвращает 2
dimension_y()	возвращает 1
cut(vertical, 1)	в результате вашего разреза получается прямоугольник размером 1 × 1, так что вы выиграли; после этого работа вашей программы автоматически прекращается.

Сегодня день рождения Никиты. На празднование дня рождения приглашены n детей (включая самого Никиту). Все дети пронумерованы числами от 1 до n. Работники МакДональдса приготовили большой круглый стол и поставили вокруг него n стульев.

Как только дети приходят на день рождения, они рассаживаются за столом. Ребенок с номером 1 занимает одно из мест. Ребенок с номером 2 занимает место слева от ребенка с номером 1. Ребенок с номером 3 занимает следующее за ним место слева и так далее. Наконец, ребенок с номером n
 займет оставшееся свободное место между детьми с номерами n – 1 и 1.

Работники МакДональдса хорошо знают, что некоторые из приглашенных детей ведут себя весьма шумно за столом, если сидят друг с другом. Поэтому работники ресторана собираются пересадить детей в некотором порядке. Этот порядок описывается перестановкой p₁, p₁,..., p_n (p₁, p₂,..., p_n — различные целые числа от 1 до n). То есть, ребенок p₁ должен сидеть между p_n и p₂, ребенок p_i (i = 2, 3, ... , n − 1) должен сидеть между p_i-1 и p_i+1; ребенок p_n должен сидеть между p_n-1 и p1.

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

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

Имейте в виду, что ребенок p_i может сидеть как слева, так и справа от ребенка pn.

Задание
Ваша задача — написать программу, которая:
· читает из стандартного ввода количество детей и перестановку, определяющую желаемый порядок рассадки детей,
· вычисляет минимально возможную величину беспорядка,
· выводит результат в стандартный вывод.

Входные данные
В первой строке стандартного ввода содержится единственное целое число n (1 ≤ n ≤ 1 000 000). Во второй строке содержатся n целых чисел p₁, p₂,..., p_n, разделенных одним пробелом. Числа p₁, p₂,..., p_n образуют перестановку множества {1, 2, ... , n}, описывающую желаемый порядок рассадки детей. Кроме того, в 50% тестов число n не будет превышать 1 000.

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

Пояснения

На рисунке слева изображена исходная рассадка детей. На рисунке в середине показан результат пересаживания, при котором дети с номерами 1 и 2 перемещаются на одно место, дети с номерами 3 и 5 перемещаются на два места и дети с номерами 4 и 6 не меняют своего положения. Требуемые условия рассадки выполнены, поскольку 3-й сидит между 6-м и 4-м, 4-й сидит между 3-м и 5-м, 5-й сидит между 4-м и 1-м, 1-й сидит между 5-м и 2-м, 2-й сидит между 1-м и 6-м и 6-й сидит между 2-м и 3-м. Также существует другой вариант конечной рассадки детей, изображенный на рисунке справа. В обоих вариантах величина беспорядка равна 2.

В Горном Парке Развлечений открылся новый аттракцион с американскими горками. Трек в аттракционе состоит из n рельсов, соединенных последовательно друг с другом, причем первый рельс начинается на высоте 0. Оператор Байтмэн может изменять конфигурацию трека по своему усмотрению, корректируя наклон некоторых последовательно соединенных рельсов. Наклон остальных рельсов при этом не изменяется. Всякий раз, когда наклон некоторых рельсов изменяется, все следующие за ними рельсы соответственно поднимаются или опускаются. При этом высота начала трека всегда остается равной 0.

На рисунках представлены изменения конфигурации трека в соответствии со входными данными, заданными в примере:

Каждый заезд начинается с того, что кабина запускается из начала трека с энергией, достаточной для достижения высоты h. Иными словами, кабина будет продолжать движение по рельсам, пока ее высота не превысит h или пока она не достигнет конца трека. Вычислите по записям о всех заездах и изменениях конфигураций трека число рельсов, которые были полностью пройдены кабиной в каждом из заездов до ее остановки.

В аттракционе трек описывается последовательностью из n наклонов, по одному для каждого рельса. i -е число d равно разнице высот (в сантиметрах) между концом i -го рельса и его началом. Иными словами, если после прохождения по первым i − 1 рельсам кабина оказывается на высоте h сантиметров, то после прохождения по i рельсам она будет на высоте h + d_i сантиметров. Изначально все рельсы горизонтальны, то есть d_i = 0 для всех i. Заезды и изменения конфигурации происходят в течение дня. Каждое изменение конфигурации описывается тремя числами: a, b
и D. Такое изменение затрагивает рельсы с a -го по b -й (включительно). Наклон каждого из этих рельсов устанавливается равным D. Иными словами, d_i = D для всех a <= i <= b. Каждый заезд задается одним числом h – максимальной высотой, на которую может подняться кабина.

Задание
Напишите программу, которая:
• читает из стандартного ввода последовательность описаний изменений конфигурации трека и заездов,
• для каждого заезда вычисляет количество рельсов, которые пройдены кабиной,
• выводит результаты в стандартный вывод.

Входные данные
Первая строка входных данных содержит одно положительное целое число n – количество рельсов в треке, 1 <= n
 <= 1000000000 . Последующие строки содержат описания изменений конфигурации и заездов. Последняя строка входных данных содержит признак окончания. Каждая строка, начиная со второй, может содержать:

• Описание изменения конфигурации трека – один символ ‘I’ и целые числа a , b и D, разделенные одним пробелом (1 <= a <= b <= n , − 1000000000 <= D <= 1000000000).
• Описание заезда – один символ ‘Q’ и целое число h ( 0 <= h <= 1000000000 ), разделенные одним пробелом.
• Один символ “E” – признак окончания входных данных.
Вы можете предполагать, что в каждый момент высота любой точки трека содержится в промежутке [0 , 1000000000] . Входные данные содержат не более 100000 строк.

Выходные данные
i-я строка выходных данных должна содержать единственное целое число – количество рельсов, которые пройдены кабиной в i-м заезде.

Рассмотрим неубывающую последовательность s₁, ..., s_n + 1 ( s_i <= s_i + 1 для 1 <= i <= n ). Последовательность m₁, ..., m_n, в которой каждый член определен как m_i = ½ * ( s_i + s_i + 1 ) для 1 <= i <= n, назовем “средней последовательностью” для последовательности s₁, ... s_n + 1. Например, средняя последовательность для последовательности 1, 2, 2, 4 есть 1.5, 2, 3. Заметим, что элементы средней последовательности могут быть дробными числами. Тем не менее, в данной задаче используются только те средние последовательности, в которых все числа целые. Для заданной неубывающей последовательности из n целых чисел m1, ..., mn необходимо вычислить количество всех неубывающих последовательностей из n + 1 целых чисел s₁, ..., s_n + 1, для которых заданная последовательность m₁, ..., m_n является средней последовательностью.

Задание
Напишите программу, которая:

• читает из стандартного ввода неубывающую последовательность целых чисел;
• вычисляет количество всех неубывающих последовательностей целых чисел, для которых заданная последовательность является средней последовательностью;
• выводит ответ в стандартный вывод.

Входные данные
Первая строка стандартного ввода содержит одно целое число n (2 <= n <= 5000000). Оставшиеся n строк содержат значения последовательности m₁, ..., m_n. Строка i + 1 содержит одно целое число mi (0 <= mi <= 1000000000).

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

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

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

Сад представляет собой прямоугольник длиной l метров и шириной w метров, который разделен на l·w одинаковых единичных квадратов размером 1x1 метр каждый. Зафиксируем координатную систему так, чтобы оси координат были параллельны сторонам сада. Все квадраты имеют целые координаты (x,y), удовлетворяющие ограничениям 1 <= x <= l, 1 <= y <= w. В каждом единичном квадрате может содержаться любое количество роз.

Стороны прямоугольных областей, которые выбираются, должны быть параллельны сторонам сада, а их угловые единичные квадраты – иметь целые координаты. Прямоугольная область с угловыми единичными квадратами (l₁,w₁), (l₁ ,w₂), (l₂, w₁) и (l₂,w₂) (для 1 <= l₁ <= l₂ <= l и 1 <= w₁ <= w₂ <= w):

• содержит все единичные квадраты с координатами (x,y), которые удовлетворяют условию l₁ <= x <= l₂ и w₁ <= y <= w2, и
• имеет периметр 2 · (l₂−l₁+1)+ 2 · (w₂−w₁+1).

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

Задание
Напишите программу, которая:

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

Входные данные
Первая строка стандартного ввода содержит два числа: l и w (1 <= l, w <= 250), разделенных одним пробелом – длину и ширину сада. Во второй строке задаются два числа: n и k (2 <= n <= 5000, 1 <= k <= n/2), записанных через пробел и обозначающих общее количество роз в саду и количество роз, которое должно быть в каждой из прямоугольных областей. Следующие n строк содержат позиции роз, по одной розе в строке. Каждая (i+2)-я строка содержит два числа l_i, w_i (1 <= l_i <= l, 1 <= w_i <= w), разделенных одним пробелом – координаты квадрата, содержащего i-ю розу.

В одном квадрате может содержаться две или большее количество роз.

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

Рисунок к тесту:

Двое играют в следующую игру. Из кучки спичек за один ход игрок вытягивает либо 1, либо 2, либо 1000 спичек. Выигрывает тот, кто забирает последнюю спичку. Кто выигрывает при правильной игре?

Входные данные
Вводится одно натуральное число — N ( 1≤ N ≤ 10000) начальное количество спичек в кучке.

Выходные данные
Выведите 1, если выигрывает первый игрок (тот, кто ходит первым), или 2, если выигрывает второй игрок.

Сколько существует клеток на доске размером K * K таких, что шахматный конь, стоящий на этой клетке, бьет ровно N полей?

Входные данные
Вводятся натуральные числа K и N (1 ≤ K ≤ 100, 2 ≤ N ≤ 8).

Выходные данные
Выведите количество клеток, с которых конь бьет ровно N
полей.

Комментарий
на доске 8*8 конь бьет ровно два поля только с угловых клеток, их 4.

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



Содержимое черного ящика можно рассматривать в виде сетки размером n x n. Отверстия в сторонах ящика – это начала и концы строк и столбцов сетки. Каждая клетка сетки либо пустая, либо занята отражателем. Отражатель – это устройство, которое изменяет направление движения шара на 90 градусов. Рассмотрим пример ящика размером 5x 5.

Вброшенный шар движется по прямой, пока не попадает в отражатель или не вылетит наружу. Когда шар попадает в отражатель, шар меняет направление своего движения, а отражатель меняет свое положение (под словом «меняет» подразумевается поворот на 90 градусов). На примере показаны действия отражателя.



a) Первый шар вброшен через отверстие. Он попал в отражатель и изменил направление движения.

b) После попадания первого шара отражатель изменил свое положение. Новый шар вбросили в то же отверстие, он попал в тот же отражатель, и отразился в направлении, противоположном направлению первого шара после отражения.

c) Отражатель изменил свое положение. После каждого попадания положение отражателя изменяется.


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

ЗАДАНИЕ
Вам будет предоставлен интерфейс к 15 черным ящикам с помощью библиотеки функций Pascal или C/C++. Вы должны определить содержимое каждого из ящиков как можно точнее и отправить на проверку файлы, описывающие каждый ящик. Интерфейс также предоставляет возможность создания собственных ящиков для тестирования.

ОГРАНИЧЕНИЯ
1 ≤ n ≤ 30

 

ВЫВОД

Вы должны предоставить на проверку файлы, содержащие следующие данные для каждого из 15 черных ящиков:

blackboxK.out

ОПИСАНИЕ

#FILE blackbox K ..... .../. .... .../. .?.?.

СТРОКА 1: Заголовок файла, который должен иметь вид #FILE blackbox K где K (число в диапазоне 1..15) соответствует ящику, для которого найдено решение. n СТРОК: Каждая строка описывает строку ящика, начиная с верхней и заканчивая нижней. Каждая строка должна содержать ровно n символов, соответствующих клеткам, находящимся на пересечении этой строки и столбцов (слева направо). ·Символ ‘.’ обозначает, что клетка пуста. ·Символ ‘/’ обозначает, что в клетке находится отражатель с исходным положением ‘/’ ·Символ ‘’ обозначает, что в клетке находится отражатель с исходным положением ‘’ ·Символ ‘?’ обозначает, что Вы не смогли определить исходное содержимое клетки

 

БИБЛИОТЕКА

Вам будет предоставлена библиотека, которая содержит следующие функции:

ФУНКЦИЯ	Описание
PASCAL function Initialize(box: integer): integer; C/C++ int Initialize(int box);	Инициализирует библиотеку. Эта функция должна вызываться один раз в начале программы. Она возвращает значение n – количество отверстий на каждой стороне ящика. Параметр box должен содержать целое число в пределах от 1 до 15, указывающее номер ящика, который Вы хотите использовать, или 0, если Вы хотите использовать ящик, созданный Вами.
PASCAL function throwBall(holeIn, sideIn: integer; var holeOut, sideOut: integer): longint; C int throwBall(int holeIn, int sideIn, int *holeOut, int *sideOut); C++ int throwBall(int holeIn, int sideIn, int &holeOut, int &sideOut);	Вбрасывает шар в ящик через отверстие с номером holeIn на стороне sideIn. Стороны пронумерованы следующим образом: 1 – Верхняя, 2 – Правая, 3 – Нижняя и 4 – Левая. Отверстия пронумерованы слева направо и сверху вниз, начиная с номера 1 на каждой стороне. В параметрах holeOut и sideOut функция возвращает номер отверстия и номер стороны – место, где шар вылетел наружу. В качестве своего значения функция throwBall возвращает количество звуковых сигналов, вызванных попаданиями шара в отражатели.
PASCAL procedure ResetBox; C/C++ Void ResetBox();	Возвращает все отражатели в исходное положение.
PASCAL procedure ToggleDeflectors; C/C++ Void ToggleDeflectors();	Меняет положения всех отражателей в ящике на противоположные.
PASCAL procedure Finalize; C/C++ Void Finalize();	Корректно заканчивает взаимодействие с ящиком. Эта функция должна вызываться в конце Вашей программы.

Чтобы использовать библиотеку в Вашей программе, необходимо выполнить следующее:
·FreePascal: В каталоге задачи есть файлы pbblib .o и pbblib. ppu. Чтобы их использовать, необходимо добавить следующую строку в Вашу программу
uses pbblib;
В файле pblackbox.pas представлен пример использования библиотеки.

·C: В каталоге задачи есть файлы cbblib.o и cbblib.h. Чтобы их использовать, необходимо добавить следующую директиву в Вашу программу
#include “cbblib.h”
В файле cblackbox.c представлен пример использования библиотеки. Чтобы скомпилировать код, используйте следующую команду
gcc –o yourprogram cbblib.o yourprogram.c

·C++: В каталоге задачи есть файлы cppbblib.o и cppbblib.h. Чтобы их использовать, необходимо добавить следующую директиву в Вашу программу
#include “cppbblib.h”
В файле cppblackbox .cpp представлен пример использования библиотеки. Чтобы скомпилировать код, используйте следующую команду
g++ –o yourprogram cppbblib.o yourprogram.cpp

 

ЗАМЕЧАНИЕ: В любой момент времени может быть запущено не более одной программы, работающей с библиотекой.
 

ПРИМЕР ВЗАИМОДЕЙСТВИЯ

Ниже представлен пример взаимодействия с ящиком, изображенным ранее на рисунке:

ВЫЗОВ ФУНКЦИИ	ВОЗВРАЩЕННОЕ ЗНАЧЕНИЕ
Initialize(0);	Пусть программа взаимодействует с ящиком, изображенным на рисунке. Тогда функция возвращает значение 5, означая, что n = 5.
PASCAL throwBall(3,4,holeOut,sideOut ); C throwBall(3,4,&holeOut,&sideOut); C++ throwBall(3,4,holeOut,sideOut);	Шар вбрасывается в отверстие с номером 3 (третье сверху) на левой стороне. Возвращается значение 1 – это означает, что шар отразился один раз. После возврата из функции, переменная holeOut содержит значение 2, а переменная sideOut содержит значение 3, то есть шар вылетел через отверстие с номером 2 (второе слева) нижней стороны ящика.

ЭКСПЕРИМЕНТИРОВАНИЕ
Если Вы передадите значение 0 в функцию Initialize, библиотека прочитает содержимое ящика из файла blackbox.in. Так Вы сможете экспериментировать с библиотекой. Формат файла blackbox.in описан ниже.

blackbox.in

ОПИСАНИЕ

5 3 2 3 4 2 / 4 4 /

СТРОКА 1: Содержит целое число n, которое задает количество отверстий на каждой стороне. СТРОКА 2: Содержит целое число d , которое задает количество отражателей в ящике. СЛЕДУЮЩИЕ d СТРОК: Каждый отражатель описывается одной строкой. Каждая строка содержит два целых числа, разделенных пробелом, которые задают номер столбца и строки, где расположен отражатель. После второго числа через один пробел записан символ, который может быть ‘/’ или ‘’ и определяет исходное положение отражателя.

ЗАМЕЧАНИЕ: Файл blackbox. in из примера описывает ящик, изображенный вверху страницы 1.
 

СООБЩЕНИЯ ОБ ОШИБКАХ

В случае любых проблем библиотека выведет сообщение об ошибке в стандартный поток вывода ошибок. Возможные сообщения об ошибке и их значения приведены в нижеследующей таблице.
 

СООБЩЕНИЕ	ЗНАЧЕНИЕ
ERR 1 More than one app	Только одна программа может одновременно работать с черными ящиками, перезапустите все программы и запускайте их строго по одной.
ERR 2 Invalid box	Переданный вами номер ящика не лежит в пределах от 0 до 15.
ERR 3 Invalid deflector	В файле blackbox.in находится отражатель в некорректной клетке.
ERR 4 Invalid symbol	В файле blackbox.in обнаружен недопустимый символ.
ERR 5 Invalid size	Размер ящика в файле blackbox. in задан неверно.
ERR 6 Invalid input hole	Либо сторона, либо отверстие вбрасывания шара заданы неверно.
ERR 7 ALARM	Пожалуйста, обратитесь к техническому персоналу.

 

Город Мехико расположен в прекрасной долине, известной как Долина Мехико, на месте которой много лет назад было озеро. Около 1300 года ацтекские религиозные лидеры выпустили указ о том, что центр озера должен быть засыпан, чтобы построить столицу их империи. В настоящее время озеро полностью осушено.

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

В какой-то момент короли городов решили упорядочить товароперевозки. Они разработали маршрут товароперевозок, который соединяет все города вокруг озера. Маршрут удовлетворяет следующим условиям:

*Он начинается в каком-либо городе, проходит через каждый прибрежный город и заканчивается в городе, отличном от того, в котором он начался.
*Маршрут проходит через каждый город ровно один раз.
*Любые два последовательно посещаемых города маршрута обязаны иметь между собой коммерческое соглашение.
*Маршрут состоит из отрезков прямых, каждый из которых соединяет два последовательно посещаемых города маршрута.
*Чтобы избежать столкновения лодок, маршрут не должен иметь самопересечений.



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

Этот маршрут нигде не имеет самопересечений. Но если построить маршрут, идущий из города 2 в город 6, затем в город 5, а затем в город 1, то он будет неправильным, поскольку имеет самопересечения.

Города нумеруются целыми числами от 1 до c по направлению часовой стрелки.
Задание
Напишите программу, которая по заданному числу городов c и списку коммерческих соглашений между городами, найдет маршрут товароперевозок, удовлетворяющий указанным выше условиям.

Ограничения
3 ≤ c ≤ 1000, c – число городов вокруг озера

Входные данные
На вход Вашей программы поступают данные в следующем формате:

СТРОКА 1: Содержит целое число c.
СТРОКА 2: Содержит целое число n – количество коммерческих соглашений.
СЛЕДУЮЩИЕ n СТРОК: Каждая строка описывает одно коммерческое соглашение (одно соглашение описывается один раз). В строке задаются два целых числа, разделенных пробелами, которые соответствуют номерам городов, заключивших между собой коммерческое соглашение.

Выходные данные
Если возможно построить маршрут товароперевозок, выведите c строк, в каждой из которых записано целое число. Эти числа представляют собой порядок посещения городов по маршруту товароперевозок. Если невозможно построить маршрут товароперевозок, удовлетворяющий всем указанным требованиям, выведите одну строку, содержащую отрицательное целое число -1.

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

После победы в великой битве Король Ягуар хочет построить пирамиду, которая будет одновременно монументом в честь победы и гробницей для погибших солдат. Пирамида будет построена на поле боя. Она должна иметь прямоугольное основание, состоящее из a столбцов и b строк. Для сохранения останков и оружия павших солдат внутри основания пирамиды будет располагаться небольшая прямоугольная комната, состоящая из c столбцов и d строк.

Архитекторы Короля представили поле боя в виде прямоугольной сетки. Эта сетка состоит из квадратных клеток единичной площади и имеет m столбцов и n строк. Для каждой клетки они измерили ее высоту и получили некоторое целое число.

Основание пирамиды и комната должны покрывать включаемые ими клетки полностью, а их стороны должны быть параллельны сторонам поля боя. Высоты клеток, составляющих комнату, должны остаться неизменными, а высоты всех клеток основания пирамиды будут выровнены с помощью перемещения песка с более высоких клеток на более низкие. В результате этого высота основания пирамиды будет равна среднему арифметическому высот всех его клеток (за исключением клеток комнаты). Архитекторы могут выбрать любое местоположение для комнаты внутри пирамиды, но обязательно оставлять вокруг комнаты стену основания пирамиды толщиной хотя бы в одну клетку.

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



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

Ограничения
3 ≤ m ≤ 1000
3 ≤ n ≤ 1000
3 ≤ a ≤ m

3 ≤ b ≤ n

1 ≤ c ≤ a – 2
1 ≤ d ≤ b – 2
Все высоты – целые числа от 1 до 100.

Входные данные
Ваша программа получает входные данные в следующем формате:
СТРОКА 1: Содержит шесть целых чисел, разделенных пробелами, в следующем порядке: m, n, a, b, c и d.
СЛЕДУЮЩИЕ n СТРОК: Каждая из этих строк содержит m целых чисел, разделенных пробелами. Эти числа соответствуют высотам клеток в одной строке сетки. Первая из этих строк соответствует верхней строке (строке 1) сетки, а последняя – нижней строке (строке n). При этом m чисел в каждой строке соответствуют высотам клеток этой строки, начиная со столбца 1.

Выходные данные
Ваша программа должна вывести следующие данные:
СТРОКА 1: Должна содержать два целых числа, разделенные пробелом, – координаты левой верхней клетки основания пирамиды, при этом первое число соответствует столбцу, а второе – строке.
СТРОКА 2: Должна содержать два целых числа, разделенные пробелом, – координаты левой верхней клетки комнаты, при этом первое число соответствует столбцу, а второе – строке.

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

Фирма Macrohard разработала новый протокол обмена данными по сети. Каждый блок данных при этом обмене состоит из N
 чисел в диапазоне от 0 до M-1 включительно. Чтобы повысить надежность передачи, вместе с блоком данных пересылается контрольный блок такой же длины.

Предположим, что исходный блок состоит из чисел a₁, a₂,…,a_N. Тогда, контрольный блок состоит из чисел b1, b2,…,bN, из диапазона от 0 до M-1 включительно таких, что выполняются следующие равенства: b₁ = (a_N + b_N) mod M, b₂ = (a₁ + b₁) mod M, ... , b_N = (a_N-1 + b_N-1) mod M (обозначение X mod M обозначает остаток от деления X на M, например, 7 mod 4 = 3, 6 mod 2 = 0).

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

Ваня хочет поступить на работу программистом в фирму Macrohard, и в качестве вступительного задания ему поручили написать процедуру построения контрольного блока для заданного блока данных. Помогите ему!

Входные данные
В первой строке вводятся числа N и M (1 <= N <= 1000, 2 <= M <= 10⁹). Следующая строка содержит блок данных, для которого следует построить контрольный блок, числа разделены пробелами.

Выходные данные
В первой строке выведите YES, если для данного блока данных можно построить контрольный блок, и NO, если нельзя. В случае, если контрольный блок построить можно, во второй строке выведите контрольный блок. Числа разделяйте пробелами. Если решений несколько, можно выдать любое из них.

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

1) Вершинами треугольников являются только точки исходного набора. Каждая точка исходного набора является вершиной хотя бы одного треугольника.
2) Два различных треугольника либо не имеют общих точек, либо имеют общую вершину, либо имеют общую сторону (но площадь их пересечения всегда равна 0).
3) Любая точка, лежащая внутри выпуклой оболочки исходного набора точек, принадлежит хотя бы одному треугольнику (она может принадлежать нескольким треугольникам, если является их общей вершиной или принадлежит их общей стороне). (Выпуклой оболочкой некоторого набора точек называется наименьший выпуклый многоугольник, содержащий все эти точки).

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

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

Входные данные
В первой строке вводится число N - количество точек (3 <= N <= 30) исходного набора. Следующие N строк содержат по одной паре вещественных чисел - координаты соответствующей точки. Никакие три точки не лежат на одной прямой.

Выходные данные
Выведите количество различных триангуляций Делоне указанного набора точек.

У Пети есть набор из N кирпичиков. Каждый кирпичик полностью окрашен в один из K цветов, i-й кирпичик имеет размер 1×1×Li. Петя знает, что он может построить из всех кирпичиков прямоугольную стену толщиной 1 и высотой K, причем первый горизонтальный слой кирпичиков в стене будет первого цвета, второй - второго и т. д. Теперь Петя хочет узнать, может ли он из своего набора построить две прямоугольные стены, обладающие тем же свойством. Помогите ему выяснить это.

Входные данные
В первой строке входных данных задаются числа N и K (1 <= N <= 5000, 1 <= K <= 100). Следующие N строк содержат описание Петиных кирпичиков: сначала длина L_i, затем номер цвета C_i (1 <= L_i <= 100, 1 <= C_i <= K). Известно, что у Пети не более 50 кирпичиков каждого цвета.

Выходные данные
Выведите в первой строке YES, если Петя сможет построить из всех своих кирпичиков две прямоугольные стены высоты K, j-й слой кирпичиков в каждой из которых будет j-го цвета, и NO в противном случае. В случае положительного ответа, выведите во второй строке в произвольном порядке номера кирпичиков, из которых следует построить первую стену (кирпичики нумеруются в том порядке, в котором они заданы во входных данных, начиная с 1). Если решений несколько, можно выдать любое из них.

Издательская система LATEX предназначена для верстки сложных научно-технических текстов с большим количеством формул. Исходный файл для системы LATEX пишется на языке TEX и представляет собой текст документа, в который включены специальные символы и команды. Специальные символы и команды описывают размещение текста, в частности в математических формулах. Команда представляет собой последовательность латинских букв (регистр важен), перед которой стоит символ "\". Так, команда \frac предназначена для описания дроби, в которой числитель расположен над знаменателем. Рассмотрим простейшую структуру команды \frac.

Команда \frac имеет два параметра — числитель и знаменатель. Перед самой командой не обязательно ставить пробел. Следом за ключевым словом frac записываются числитель и знаменатель. Если числитель и знаменатель имеют длину более одного символа, они заключаются в фигурные скобки. Если числитель или знаменатель записываются одной буквой или цифрой, их можно не брать в фигурные скобки. Если числитель записывается одним символом, то он отделяется от \frac хотя бы одним пробелом. Если знаменатель записывается одним символом, то он не отделяется пробелом от числителя. Произвольное ненулевое количество пробелов считается синтаксически эквивалентным одному пробелу. Нельзя разделять пробелами на части ключевое слово \frac.

Дадим также формальное определение выражения для нашей задачи:

<выражение> ::= <элемент> | <элемент><выражение>
<элемент> ::= <дробь> | "{" <выражение> "}" | <другой математический элемент>
<дробь> ::= "\frac" <тело дроби>
<тело дроби> ::= <числитель><знаменатель>
<числитель> ::= <пробелы><непробельный символ> | [<пробелы>] "{" <выражение> "}"
<знаменатель> ::= <непробельный символ> | [<пробелы>] "{" <выражение> "}"
<другой математический элемент> ::= произвольная последовательность печатных символов, не содержащая фигурных скобок и подстроки "\frac"
<пробелы> ::= " " | " " <пробелы>
<непробельный символ> ::= произвольный печатный символ, за исключением " ", "", "{" и "}"

Здесь вертикальная черта | означает "или", заключенная в квадратные скобки часть может отсутствовать, а символы, записанные в кавычках обозначают самих себя. Печатный символ - любой символ с ASCII кодом от 32 (пробел) до 127. Например, выражение


записывается на языке TEX как

\frac{a+b}{d+1}+\frac ax -\frac 2 {2+\frac{3}{y}}

Чтобы в печатаемом документе вывести формулу, необходимо вычислить ее высоту для используемого при печати шрифта. Шрифт определяет размеры S
 - высоту отдельного символа и D
 - высоту горизонтальной дробной черты. Значения S
 и D
 задаются целыми числами. Ваша задача - для заданного выражения на языке TEX вычислить высоту формулы.

Отметим, что если две дроби принадлежат одному выражению, то их дробные черты записываются на одном уровне, а если нет (например, относятся к числителям или знаменателям различных дробей), это свойство может и не выполняться. Чтобы проиллюстрировать применение этого правила, приведем два примера:

\frac{a+b}{\frac cd}+\frac{\frac ef}{g+h}


\frac{a+b+c}{\frac{\frac de}{g+h}}+\frac{i+j+k}{\frac{l+m}{\frac no}}

Входные данные
В первой строке вводятся целые положительные числа S и D (1 <= S, D <= 10000). Следующая строка содержит описание формулы на TEX-е, длина строки не более 200 символов. Гарантируется, что формула синтаксически корректна, то есть фигурные скобки образуют правильную скобочную последовательность и строка содержит только печатные символы. Все символы "", встречающиеся в строке относятся к некоторой командной последовательности (не обязательно \frac), можете считать, что все прочие командные последовательности задают символы, высота которых равна S. Числитель и знаменатель каждой дроби содержат хотя бы по одному символу, вся формула содержит хотя бы один символ.

Выходные данные
Выведите единственное число - высоту формулы.

Рассмотрим выпуклый многоугольник, вершины которого лежат в точках плоскости с целыми координатами. Требуется разбить его на треугольники с вершинами в точках с целыми координатами, каждый из которых имел бы площадь 1/2, либо выяснить, что это сделать невозможно.

Входные данные
В первой строке вводится число N - количество вершин многоугольника (1 <= N <= 10). Следующие N строк содержат координаты вершин многоугольника в порядке обхода их по часовой стрелке. Все координаты - целые неотрицательные числа, не превышающие 10. Никакие три последовательные вершины многоугольника не лежат на одной прямой.

Выходные данные
Если выполнить разбиение указанным образом невозможно, выведите единственное число - 0. В противном случае выведите несколько строк, содержащих по 6 чисел каждая. Количество строк должно быть равно количеству треугольников в найденном разбиении. Числа в каждой строке должны представлять собой координаты вершин соответствующего треугольника - x₁, y₁, x₂, y₂, x₃, y₃. Площадь каждого треугольника должна быть 1/2. Порядок перечисления треугольников и вершин в каждом из треугольников может быть произвольным. Если допустимых разбиений несколько, выведите любое.

В одном государстве имеется N городов. Некоторые города соединены дорогами, причем для любых двух городов A и B выполняется следующее свойство: существует ровно один способ попасть из города A в город B если можно перемещаться только по дорогам и не разрешается проезжать по одной и той же дороге более одного раза.

Недавно президента этой страны заинтересовал вопрос: какие три города являются наиболее удаленными друг от друга. А именно, назовем взаимной удаленностью друг от друга трех городов A, B и C минимальное количество дорог, которое необходимо использовать, чтобы доехать от A до B, затем от B до C и затем от C до A (при этом разрешается использовать одну и ту же дорогу в различных путешествиях).

Требуется найти три города, для которых взаимная удаленность друг от друга будет максимальной.

Например, для пяти городов, соединенных дорогами так, как это показано на рисунке 1, три наиболее удаленных друг от друга города - это города 1, 2 и 5 (взаимная удаленность равна 2 + 3 + 3 = 8), а для городов на рисунке 2 - это любые три города, выбранные из множества {1, 2, 4, 5} (удаленность 2 + 2 + 2 = 6).

Входные данные
В первой строке вводится число N - количество городов (3 <= N <= 1000). Следующие N строк содержат описания городов. Описание i-го города сначала содержит K_i - количество городов, с которыми он соединен дорогами (1 <= K_i < N), а затем K_i чисел - номера городов, с которыми он соединен. Гарантируется, что входные данные корректны - то есть если есть дорога из города A в город B, то есть и дорога из города B в город A, причем для всех пар городов выполняется свойство, указанное в условии задачи.

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

Играют двое. Задаётся какая-то дата 2020 года. Каждый игрок на своём ходе называет более позднюю дату, увеличивая на 1 или 2 либо день в месяце, либо месяц, но не то и другое сразу. При этом сочетание дня и месяца должно оставаться датой. Игрок, назвавший 31 декабря, проигрывает. Оба играют наилучшим образом. Исходя из заданной даты вывести, кто выиграет.

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

Выходные данные
Вывести 1, если выигрывает первый (начинающий) игрок, или 2 - в противном случае.