Информатика

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

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

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

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

Замените в программе символы __ таким образом, чтобы числа 10 и 20 выводились в столбик (каждое число на отдельной строке).

Удалите эти подчеркивания и напишите на этом месте нужные числа и переход на новую строку.

Найдите количество чисел Z, удовлетворяющих неравенству A ≤ Z ≤ B, таких, что в записи Z
в двоичной системе счисления используется ровно 2 единицы. Например, если A=10; B=20; то таких чисел 5 (это числа 10=1010₂; 12=1100₂; 17=10001₂; 18=10010₂; 20=10100₂).

Входные данные
На вход программы поступают два числа, записанных через пробел — A, B ( 0 ≤ A, B ≤ 10⁹)

Выходные данные
Выведите одно число – количество чисел Z.

Илья Муромец идет на битву со Змеем Горынычем. У Змея Горыныча М голов, Илья Муромец за один удар отрубает N голов, после удара Змей Горыныч регенерирует K голов. Далее процесс повторяется, пока головы не кончатся.

Напишите программу, которая определяет, сможет ли Илья Муромец одолеть Змея Горыныча и, если да, то сколько ударов для этого потребуется.

Входные данные
Программа получает три числа, записанных через пробел — N, M и K (1 ≤ N , M, K ≤ 10⁹), где N – число голов, которые Илья Муромец срубает одним ударом, M – число голов Змея Горыныча, K – число голов, которые Змей Горыныч регенерирует за раз.

Выходные данные
Вывести число ударов, которые должен нанести Илья Муромец, чтобы убить Змея Горыныча. Если одолеть Змея Горыныча при заданных исходных данных невозможно, то следует вывести «NO» (без кавычек заглавными буквами).

По заданному числу определить название месяца.

Входные данные
Вводится одно натуральное число N, 1 ≤ N ≤ 12

Выходные данные
Программа выводит КОД месяца согласно таблице:

 

В игру «черный ящик» играют с помощью квадратного черного ящика, который располагается на плоском столе. На каждой из сторон ящика есть 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). Если решений несколько, можно выдать любое из них.

В околоземном космическом пространстве накопилось много мусора, поэтому ученые сконструировали специальный аппарат - ловушку для космического мусора. Для того, чтобы хорошо собирать мусор, этот аппарат должен двигаться по достаточно сложной траектории, сжигая собранный по пути мусор. Ловушка может передвигаться в пространстве по 6 направлениям: на север (N), на юг (S), на запад (W), на восток (E), вверх (U) и вниз (D). Движением ловушки управляет процессор. Программа движения задается шестью правилами движения, которые соответствуют каждому из указанных направлений. Каждое такое правило представляет собой строку символов из множества {N, S, W, E, U, D}.

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

Пусть, например, заданы следующие правила:

Направление	Правило
N	N
S	NUSDDUSE
W	UEWWD
E
U	U
D	WED

Тогда при выполнении команды S(3) мусорщик выполнит следующие действия:
1) переместится на 1 метр в направлении S
2) выполнит последовательно команды N(2), U(2), S(2), D(2), D(2), U(2), S(2), E(2).
Если далее проанализировать действия мусорщика при выполнении команд из пункта 2, получим, что в целом он совершит следующие перемещения:

SNNUUSNUSDDUSEDWEDDWEDUUSNUSDDUSEEПо заданной команде определите, какое общее количество перемещений на один метр совершит ловушка при выполнении заданной команды. В приведенном примере это количество равно 34.

Входные данные
Первые шесть строк входных данных задают правила для команд с направлением N, S, W, E, U и D соответственно. Каждая строка содержит не более 100 символов (и может быть пустой). Следующая строка содержит команду ловушки: сначала символ из множества {N, S, W, E, U, D}, затем пробел и параметр команды - целое положительное число, не превышающее 100.

Выходные данные
Выведите единственное число - количество перемещений, которое совершит ловушка. Гарантируется, что ответ не превышает 10⁹.

Издательская система 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 - в противном случае.

Ваня наблюдает за лягушкой. Изначально она сидит в точке 0 числовой прямой. Каждую секунду она прыгает на 1 вправо, пока не достигнет точки K. Затем она начинает каждую секунду прыгать на 1 влево, пока не вернется в точку 0, затем – опять вправо и т. д. Требуется определить, где окажется лягушка через T секунд.

Входные данные
Вводятся два числа K и T, разделенные пробелом. Оба числа натуральные и не превосходят 1 000 000 000.

Выходные данные
Вывести одно число – координату лягушки в момент времени T.
 

В файле приведён фрагмент базы данных «Продукты» о поставках товаров в магазины районов города. База данных состоит из трёх таблиц.
Таблица «Движение товаров» содержит записи о поставках товаров в магазины в течение первой декады июня 2021 г.,
а также информацию о проданных товарах. Поле Тип операции содержит значение Поступление или Продажа,
а в соответствующее поле Количество упаковок внесена информация о том, сколько упаковок товара поступило в магазин или было продано в течение дня. Заголовок таблицы имеет следующий вид.

ID операции

Дата

ID магазина

Артикул

Количество упаковок, шт.

Тип операции

Таблица «Товар» содержит информацию об основных характеристиках каждого товара. Заголовок таблицы имеет следующий вид.

Артикул

Отдел

Наименование товара

Ед_изм

Количество в упаковке

Цена за упаковку

Таблица «Магазин» содержит информацию о местонахождении магазинов. Заголовок таблицы имеет следующий вид.

ID магазина

Район

Адрес

На рисунке приведена схема указанной базы данных.


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

Файл к заданию

В файле приведён фрагмент базы данных «Продукты» о поставках товаров в магазины районов города. База данных состоит из трёх таблиц.
Таблица «Движение товаров» содержит записи о поставках товаров в магазины в течение первой декады июня 2021 г.,
а также информацию о проданных товарах. Поле Тип операции содержит значение Поступление или Продажа,
а в соответствующее поле Количество упаковок внесена информация о том, сколько упаковок товара поступило в магазин или было продано в течение дня. Заголовок таблицы имеет следующий вид.

ID операции

Дата

ID магазина

Артикул

Количество упаковок, шт.

Тип операции

Таблица «Товар» содержит информацию об основных характеристиках каждого товара. Заголовок таблицы имеет следующий вид.

Артикул

Отдел

Наименование товара

Ед_изм

Количество в упаковке

Цена за упаковку

Таблица «Магазин» содержит информацию о местонахождении магазинов. Заголовок таблицы имеет следующий вид.

ID магазина

Район

Адрес

На рисунке приведена схема указанной базы данных.


Используя информацию из приведённой базы данных, определите, на сколько увеличилось количество упаковок яиц диетических, имеющихся в наличии в магазинах Октябрьского района, за период с 1 по 8 июня включительно.
В ответе запишите только число.

Файл к заданию