Задачи на моделирование

Риэлторская фирма “КвартирКа” решила добавить в своё приложение кредитный калькулятор для своих клиентов. На время тестирования нового обновления калькулятор был сделан более простым.

Формат входных данных
На входе программа получает ряд натуральных целых чисел, разделённых переносом строки: сумма кредита (10000<=x<=999999999), процентная ставка (годовая) ( 1<=x<=100), планируемая сумма для ежемесячного погашения кредита (10000<=x<=999999999).
Формат выходных данных
На выходе программа должна выдать возможно ли выплатить кредит по представленным параметрам в виде: “True” - если возможно, “False” - если невозможно и на следующей строке количество месяцев необходимое для выплаты кредита, если кредит выплатить невозможно следует вывести ноль.

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

Пример: сумма кредита - 50.000, процентная ставка 50%, планируемая сумма погашения 10.000. В первый месяц будут начислены процента на долг, который составит 25.000. В первый месяц вся сумма пойдёт на погашения процентов 25.000-10.000. Во второй месяц, аналогично 15.000-10.000. В третий месяц 5.000 уйдёт на погашение долга по процентам и 5.000 на погашение задолженности, остаётся выплатить 45.000. В четвёртый месяц 45.000-10.000. В пятый 35.000-10.000. В шестой 25.000-10.000. В седьмой 15.000-10.000. На восьмой месяц кредит будет полностью погашен, так как не было набрано 12 месяцев проценты более не начислялись.

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

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

Пример матрицы и карточки (где белые участки – это вырезы (отверстия)).

Таким образом начинаем выписывать цифры по строкам слева-направо: 554755831378617673. Знаем, что цифр обозначающих координату 8, а две лишние – обозначающие запятые, получим координаты 55.755831 37.617673.
Также на каждой карточке Иван Фёдорович заметил на углу пометку, которая, как позднее он понял, определяет, как должна быть развёрнута карточка, так как метка должна при наложении всегда находиться в левом верхнем углу при взгляде на неё:

• 1 – метка в левом верхнем углу карточки;
• 2 – метка в правом верхнем углу карточки;
• 3 – метка в правом нижнем углу карточки;
• 4 – метка в левом нижнем углу карточки.

Входные данные
на первой строке подаётся целое число K (2 <= K <= 100) – количество преступлений, которые совершили грабители;
далее на K строках подаются координаты предыдущих мест преступлений в виде вещественных чисел с точкой, разделённых пробелом (например, 55.755831 37.617673)
на следующей строке подаются размеры матрицы и карточек в виде целых чисел N, M (5 <= N,M <= 1000), где N – количество строк матрицы, а M – количество столбцов;
далее на N строках подаются по M цифр матрицы;
после подаётся на новой строке целое число – количество карточек L (K < L <= 100); 
далее подаётся на одной строке L цифр от 1 до 4 через пробел, которые отображаются метки карточка в соответствии с порядком их появления;
затем L раз по N строк и M цифр подаются карточки по порядку их появления, которые содержат либо цифру 1 – обозначающую наличие прорези на ней, либо 0 – если прорези в этом месте на карточке нет.
Выходные данные
выведите все координаты будущих мест преступлений (каждую с новой строки), отсортировав их по возрастанию (если две координаты одинаковые по первой координате, то сортировать по возрастанию по второй), координаты одного места выводить через пробел.
Примечание:
·при выводе дробной части координат выводить всегда 6 знаков, если знаков меньше, то дополнять их незначащими нулями;
·если матрица прямоугольная, то гарантируется, что при совмещении метки на карточке с левым верхним углом матрицы, карточка совпадёт с размером матрицы;
·данные на карточках нельзя отзеркаливать (переворачиватькарточки не в плоскости OXY);
·гарантируется, что если даны метки на карточках, то при повороте карточка совпадёт с размером матрицы, не будет такого, что карточка будет иного размера, чем матрица.

В маленьком городе N, где нет ни интернета, ни телефонов, живут лучшие друзья Коля, Маша, Саша и Наташа. В очередной зимний день им очень хотелось провести время, играя в какую-нибудь игру, но такую, чтобы игра была не очень быстрой. Потому Маша предложила ребятам сыграть в своего рода модифицированную карточную версию игры «Пьяница» под названием «Круговерть_2».
Правила игры оказались следующими:

• ·игрокам заранее раздают поровну перетасованную колоду из52 карт (четыре масти: червы, бубны, трефы, пики, в каждой из которых 13 карт), таким образом у каждого игрока оказывается своя колода карт, стоящая в виде стопки, расположенной рубашкой вниз;
• ·каждый ход игроки выкладывают на стол по одной картесверху своей колоды на стол, по порядку слева-направо (первый игрок, второй игрок, третий и четвёртый), далее происходит определение победителей:
•     - если карты одной масти, то побеждает тот, у кого картабыла наибольшего значения (порядок карт в порядке их значения по возрастанию: туз, 2-10, валет, дама, король); туз - самая слабая карта;
•     - если карты разных мастей, то побеждает тот, у когомасть выше по значению (порядок мастей по возрастанию: червы, бубны, трефы, пики);
•     - если карт высшей масти несколько, то рассматриваетсяопределение наибольшего значения среди этих карт (например, выложили 10 червы, 8 бубны, 7 трефы, 8 трефы, то карты разных мастей, потому выбирается наибольшая масть – в данном случае трефы, таких карт две, среди них самая наибольшая 8 трефы, потому побеждает игрок 4);
• ·победитель забирает четыре карты в свою колоду по порядку,кладя сперва карту первого игрока под низ колоды, затем второго, третьего, четвёртого;
• ·побеждает тот игрок, который заберёт все картыпротивников.

Коля очень любит программирование, потому он решил заранее рассчитать, сколько им понадобится ходов, чтобы был определён победитель (у кого будут все 52 карты), потому ему требуется помочь написать программу, которая по входным данным игры определит через сколько ходов будет определён победитель игры. Если же за 1000 ходов победитель так и не определится, то вывести, сколько карт оказалось у первого игрока, у второго, третьего, четвёртого.
Входные данные:
на первых 13 строках подаются карты первого игрока (в порядке их нахождения в стопке карт),
далее на 13 строках подаются карты второго игрока (в порядке их нахождения в стопке карт),
далее на 13 строках подаются карты третьего игрока (в порядке их нахождения в стопке карт),
далее на 13 строках подаются карты четвёртого игрока (в порядке их нахождения в стопке карт).
Все карты подаются в формате <масть>, <значение>.
Масти обозначаются следующим образом (одна латинская буква в нижнем регистре):

• c – червы;
• b – бубны;
• t – трефы;
• p – пики.

Значения карт с картинками обозначаются следующим образом (одна латинская буква в нижнем регистре):

• t – туз;
• v – валет;
• d – дама;
• k – король.

Например:

• (t,10) – десятка треф;
• (c, t) – туз червей.

Выходные данные:
Если за 1000 ходов (включительно) кто-то победит, то вывести количество ходов и номер победившего игрока (например, 340 2, что означает, что за 340 ходов победил игрок №2).
Если за 1000 ходов (включительно) минимум у двух игроков останутся карты (никто не победит), то вывести количество карт по завершении 1000-го хода у первого игрока, у второго, у третьего, у четвёртого на одной строке через пробел (например, 48 3 1 0).
Примечание
•карты перечисляются в вводе так, как они лежат сверху-вниз,если сперва дали туз, затем 10, то на дне колоды лежит 10, а на верху туз, который будет вытащен первым.

В маленьком городе N, где нет ни интернета, ни телефонов, живут лучшие друзья Коля и Маша. В очередной зимний день им очень хотелось провести время, играя в какую-нибудь игру, но такую, чтобы игра была не очень быстрой. Потому Маша предложила Коле сыграть в своего рода модифицированную карточную версию игры «Пьяница» под названием «Круговерть».
Правила игры оказались следующими:
·игрокам заранее раздают поровну перетасованную колоду из52 карт (четыре масти: червы, бубны, трефы, пики, в каждой из которых 13 карт), таким образом у каждого игрока оказывается своя колода карт, стоящая в виде стопки, расположенной рубашкой вниз;

• каждый ход игроки выкладывают на стол по одной картесверху своей колоды на стол, далее происходит определение, кто заберёт карты:

               - если карты одной масти, то забирает карты тот, у когокарта была наибольшего значения (порядок карт в порядке их значения по возрастанию: туз, 2-10, валет, дама, король); туз - самая слабая карта; 
               - если карты разных мастей, то забирает карты тот, у когомасть выше по значению (порядок мастей по возрастанию: пики, червы, бубны, трефы);

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

Коля очень любит программирование, потому он решил заранее рассчитать, сколько им понадобится ходов, чтобы был определён победитель (у кого не будет карт), потому ему требуется помочь написать программу, которая по входным данным игры определит через сколько ходов будет определён победитель игры. Если же за 1000 ходов победитель так и не определится, то вывести, сколько карт оказалось у первого игрока и сколько у второго.
Входные данные:
на первых 26 строках подаются карты первого игрока (в порядке их нахождения в стопке карт),
далее на 26 строках подаются карты второго игрока (в порядке их нахождения в стопке карт).
Все карты подаются в формате <масть>, <значение>.
Масти обозначаются следующим образом (одна латинская буква в нижнем регистре):

• c – червы;
• b – бубны;
• t – трефы;
• p – пики.

Значения карт с картинками обозначаются следующим образом (одна латинская буква в нижнем регистре):

• t – туз;
• v – валет;
• d – дама;
• k – король.

Например:

• (t,10) – десятка треф;
• (c, t) – туз червей.

Выходные данные: 
Если за 1000 ходов (включительно) кто-то победит, то вывести количество ходов и номер победившего игрока (например, 340 2, что означает, что за 340 ходов победил игрок №2).
Если за 1000 ходов (включительно) у всех останутся карты (никто не победит), то вывести количество карт по завершении 1000-го хода у первого игрока и у второго на одной строке через пробел (например, 50 2).
Примечание
•карты перечисляются в вводе так, как они лежат сверху-вниз,если сперва дали туз, затем 10, то на дне колоды лежит 10, а на верху туз, который будет вытащен первым.

Город имеет форму прямоугольника с вершинами в точках (-W,-H), (-W,H), (W,H),(W,-H).
Плоскость разбита на кварталы. Квартал — это единичная клетка, вершины которой имеют целочисленные координаты. Назовем квартал городским, если все вершины квартала находятся внутри города (считается, что точка на границе принадлежит городу). Всего в городе будет 4·W·H кварталов.
Дорожная сеть состоит из N дорог (часть дорог или все проходят через город).
Дорога — это прямая линия, не параллельная осям координат.
Дорога задается двумя различными точками на ней (точки могут находиться вне города).
Для каждого квартала определим "значимость". Значимость квартала равна количеству дорог, проходящих через этот квартал. Считается, что дорога проходит через квартал, если имеет с кварталом не менее двух общих точек.
Найдите значение "значимости" для каждого квартала. Для каждой полученной "значимости" определите количество кварталов, имеющих эту значимость.

Формат входных данных
В первой строке заданы значения W, H, N (9<W,H<201, 0<N<1001)
В следующих N строках задано по четыре числа (координаты двух точек прямой, определяющих дорогу).

Формат выходных данных
В первой строке выведите число K - количество различных ненулевых значений "значимости".
В следующих K строках выведите по два числа - значение "значимости" и количество кварталов, имеющих такое значение "значимости".


Примечание к примеру

Город расположен в прямоугольнике со сторонами 8 и 6 клеток (всего 48 кварталов)
Через город проходят 4 дороги AB, CD, EF, GH
Значимость 1 будет у 24 кварталов (коричневый цвет на рисунке)
Значимость 2 будет у 5 кварталов (зеленый цвет на рисунке)
Значимость 4 будет у 1 кварталов (красный цвет на рисунке)
18 кварталов будут иметь значимость равную 0 (на печать не выводиться)

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

Формат ввода
На вход программе в первой строке подается натуральное число N, не превышающее 10000 – количество замеров температуры.
Во второй строке подается натуральное число X, не превышающее 1000 – пороговое значение температуры.
Далее в N строках подается по одному натуральному числу t_i, не превышающему 1000 – температура смеси при измерении номер i.
Формат вывода
Вывести одно целое число – сколько минут длился самый длительный нагрев смеси.

Электронная схема состоит из элементов И и НЕ.
Элемент НЕ имеет один вход и один выход. Принцип его работы следующий: если на входе появится сигнал 0, то через 1 мс на выходе установится сигнал 1, а если на входе 1, то через 1 мс на выходе установится сигнал 0.
Элемент И имеет два входа и один выход. Если на обоих его входах появится сигнал 1, то через 1 мс на выходе установится сигнал 1. Если хотя бы на один из входов поступает 0, то через 1 мс на выходе устанавливается сигнал 0.
Все точки подсоединения элементов пронумерованы. Если в точку поступает сигнал с выходов нескольких элементов, то в этой точке сигнал равен 0 тогда, когда со всех выходов поступает сигнал 0. Если с одного или нескольких выходов, подсоединенных в одной точке, поступает сигнал 1, то в этой точке устанавливается сигнал 1. В последних двух случаях сигнал устанавливается мгновенно (без задержки).
Известно состояние (сигнал 0 или 1) каждой точки в момент включения схемы. Необходимо выдать состояние некоторой указанной точки К в течение первых T мс с момента включения схемы.
В точках, которые соединены только с входами элементов, сигнал остается неизменным с момента включения схемы до окончания ее работы.
Формат ввода
На вход программе в первой строке подаётся натуральное число N. Далее идет N строк, каждая из которых содержит несколько целых десятичных чисел, отделенных друг от друга одним или несколькими пробелами. Первое число в строке показывает, что именно описывают оставшиеся числа данной строки:
0 - описание точки соединения;
   0 m n - точка с номером m имеет в момент включения состояние n (0 или 1)
1 - описание элемента НЕ;
   1 x y - элемент НЕ, вход которого соединен с точкой под номером x, а выход - с точкой под номером y
2 - описание элемента И;
   2 x y z - элемент И, один вход которого соединен с точкой под номером x, второй вход соединен с точкой под номером y, а выход - с точкой под номером z
3 - описание задания.
   3 K T - необходимо выдать состояние точки K в течение первых T мс с момента включения схемы.
Формат вывода
T строк: первая строка - состояние точки K в первую мс, вторая строка - состояние точки K во вторую мс, и так далее до T мс.

Пример
Пусть имеется схема, приведенная на рисунке. Необходимо выдать состояние точки 3 в течение 5 мс с момента включения схемы.

Станция связи принимает блоки сообщений. Каждое сообщение представляет собой последовательность кодовых сигналов. Всего сигналов 26; они перечислены в блоке как цифры числа, записанного в системе с основанием 26.Обработка некоторых кодовых сигналов требует участия операторов;значения таких сигналов кратны 6. На вход подаётся N чисел, записанных вдесятичной системе счисления – блоков сообщений. Определите, в сколькихблоках оказалось менее M₁ или более M₂ команд, требующих участияоператоров.

Формат входных данных
На вход программе в первой строке подается натуральное число N (N ≤ 10000) – количество блоков сообщений. Во второй строке подаются два целых неотрицательных числа M₁ и M₂ (0 ≤ M₁ ≤ M₂ ≤ 1000) – ограничение по количеству кодовых сигналов, требующих обработки оператором. Далее в N строках на вход подаётся по одному целому числу в диапазоне от 0 до 4*10⁹ – блок сообщений, записанных в десятичной системе счисления.
Формат выходных данных
Вывести одно целое число – в скольких блоках оказалось менее M₁ или более M₂ команд, требующих участия операторов.

Находясь в агрессивной среде аппарат, снабженный целым комплексом датчиков, мониторит сразу несколько параметров. Необходимо написать программу анализа для параметра F. Этот параметр принимает целые значения. Задан диапазон допустимых значений [X; Y] (границы отрезка тоже являются допустимыми значениями). Каждую минут снимаются показания с датчика F. После выключения оборудования датчик показывает 0. Это значение в серию измерений уже не включается. Необходимо посчитать наибольшее отклонение от допустимых значений и сколько раз за время наблюдения оно было зафиксировано.

Формат входных данных
На первых двух строчках вводятся два целых числа X и Y (X < Y), которые задают диапазон допустимых значений.
На последующих строчках вводятся целые числа (по одному в каждой строке) – показания параметра F, передаваемые аппаратом. Последнее значение 0 – признак выключения аппарата – это значение в показания НЕ включается.
Все числа по модулю не превосходят 1 000.
Гарантируется, что хотя бы один выход из допустимого диапазона значений был.
Формат выходных данных
Два целых числа в одной строке через пробел: максимальное отклонение и количество отклонений на такое значение за время наблюдения.

Примечание
В данном примере 11 измерений. Максимальное отклонение 2 от заданного допустимого диапазона [-4; 11] будет достигнуто 3 раза на значениях -6, 13 и 13
|-6 – (-4)| = |13 – 11| = 2

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

Формат входных данных
На вход на первой строке подаётся число X (1 <= X <= 100000) – длина дороги в метрах.
На второй строке подаются числа W, H (1 <= W,H <= 100) – высота и ширина жителя-прямоугольника в метрах соответственно.
На третьей строке подаётся число N (1 <= N <= 1000) – количество ям на дороге.
Далее на N-строках подаются координаты начала ямы (в метрах от начала дороги) и её ширина в виде целых положительных чисел от 1 до X. Координаты ям могут подаваться в любом порядке. Но все ямы не пересекаются и не накладываются.
Формат выходных данных
Выведите на первой строке количество ям, которые необходимо заделать, чтобы житель-прямоугольник, для которого производится расчёт, смог добраться до конца дороги.
Далее выведите координаты всех ям отсортированные в порядке появления от начала дороги до конца, КАЖДУЮ С НОВОЙ СТРОКИ.

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

В данном случае житель может стоять основанием перед началом дороги на стороне 2 (положение №1) или 3 (положение №2).
Если он стоит на основании длиной 2, то он попадёт только в яму под номером 14.
Если он стоит на основании длиной 3, то он попадёт в ямы 10 и 14.
Городу выгоднее заделать только одну яму, под номером 14.

Положение №1.


Положение №2.

 

В школе №1920 решили провести соревнование по написанию небольших игр среди школьников. Первым критерием данного соревнования было условие того, что в игре нельзя заранее рассчитать результат зная входные данные.
Коля написал игру, в которой задаётся квадратная матрица, состоящая из целых чисел, но не содержащая нулей. Суть игры в том, что в неё играют два участника и каждый может сделать одно из следующих действий:
1.Повернуть матрицу на 90 градусов по часовой стрелке
2.Повернуть матрицу на 90 градусов против часовой стрелке
3.Повернуть матрицу на 45 градусов по часовой стрелке (если есть нули,то они схлопываются (см. пример))
4.Повернуть матрицу на 45 градусов против часовой стрелке (если естьнули, то они схлопываются (см. пример))
У игроков есть ограниченное чётное количество ходов. Каждый из игроков ходит по очереди. Победой в игре считается сумма чисел на ближайшей стороне матрицы, которая находится ближе к игроку. Если матрица в конце повёрнута на 45 градусов, то результатом берётся ближайший угол матрицы к каждому из игроков (одно число в вершине).
Помогите Коле написать алгоритм, который будет по входной матрице и порядку действий ребят определять сколько очков набрал игрок №1 и игрок №2.
Поворот квадратной матрицы на 45 градусов по часовой стрелке будет выглядеть следующим образом.

Формат входных данных
На вход первой строкой подаются число N (1 <= N <= 1000) – размер исходной сгенерированной квадратной матрицы (N – количество строк). Далее на N строках подаются по N целых чисел (кроме нуля).
Далее подаётся число K (2 <= K <= 100, K – чётное)– количество ходов у игроков.
На последующих K-строках вводятся команды, которые выбрали ребята (от 1 до 4), где первая команда соответствует первому игроку (сидящему слева), следующая команда второму (сидящему справа) и так далее.
Формат выходных данных
Вывести на одной строке через пробел результат игры для первого игрока и для второго.

Примечание:

1	2	3
4	5	6
7	8	9

1 команда (повернуть на 90 градусов по часовой стрелке)

7	4	1
8	5	2
9	6	3

2 команда (повернуть на 45 градусов по часовой стрелке)

0	0	7	0	0
0	8	0	4	0
9	0	5	0	1
0	6	0	2	0
0	0	3	0	0

3 команда (повернуть на 90 градусов по часовой стрелке)

0	0	9	0	0
0	6	0	8	0
3	0	5	0	7
0	2	0	4	0
0	0	1	0	0

4 команда (повернуть на 45 градусов против часовой стрелке (нули схлопываются))

9	8	7
6	5	4
3	2	1

Первый игрок находится слева, значит ячейки, которые идут ему в счёт 9 + 6 + 3.
Для второго игрока справа 7 + 4 + 1.
 

На столе у большого начальника лежит стопка из N заявлений, пронумерованных сверху вниз от 1 до N. Первое заявление он подписывает и убирает из стопки, второе — выбрасывает в мусорную корзину, третье — кладёт вниз стопки. Далее процесс продолжается аналогично, пока заявления в стопке не закончатся. Определите, будет ли заявление с номером K подписано или выброшено, а также номер шага, на котором это произойдёт. Одним шагом является каждая из трёх операций, описанных выше.

Формат входных данных
Первая строка входных данных содержит целое число N, вторая строка — целое число K (1 ≤ N ≤ 10⁹ , 1 ≤ K ≤ N).
Формат выходных данных
В первой строке выведите «Yes», если заявление с номером K будет подписано, и «No», если оно будет выброшено. Во второй строке выведите номер шага, на котором это произойдёт.

Замечание
В первом примере из условия в стопке находятся 4 заявления: (1, 2, 3, 4). Заявление 1 подписывается, заявление 2 выкидывается, заявление 3 перекладывается в конец. После выполнения трёх шагов в стопке будут заявления (4, 3). Поэтому на пятом шаге заявление 3 будет выброшено.
Во втором примере из условия стопка имеет вид (1, 2, 3, 4, 5). После выполнения трёх шагов стопка будет иметь вид (4, 5, 3). За следующие три шага заявление 4 будет подписано, заявление 5 будет выброшено, а заявление 3 — переложено в конец стопки (в которой ничего не будет, кроме заявления 3). Поэтому после шести шагов стопка будет иметь вид (3). На седьмом шаге заявление 3 будет подписано.

Новая татарская игра <<2026>> ведется на прямоугольной клетчатой доске, состоящей из \(m\) строк и \(n\) столбцов. Доска разбита на \(m \times n\) единичных клеток размером \(1 \times 1\). На некоторых клетках стоят квадратные фишки размером \(1 \times 1\), на каждой фишке написана одна из \(26\) английских букв.

С фишками производятся \(q\) операций. Каждая операция состоит в перемещении всех фишек до упора в одном из четырех направлений. Таким образом, последовательность операций задается строкой \(s\) длины \(q\), состоящей из символов, соответствующих направлениям: <<L>> — влево, <<R>> — вправо, <<U>> — вверх и <<D>> — вниз.

Операция выполняется следующим образом: пока на доске есть хотя бы одна фишка, для которой соседняя с ней в заданном направлении клетка является свободной, эта фишка передвигается на эту соседнюю клетку.

Определите, как будет выглядеть доска после выполнения всех операций.

Формат входных данных

Каждый тест состоит из нескольких наборов входных данных. В первой строке теста задано целое число \(t\) — количество наборов входных данных в тесте (\(1 \le t \le 200\,000\)). Далее следуют описания наборов входных данных. Каждый набор входных данных описывается следующим образом:

В первой строке набора заданы целые числа \(m\) и \(n\) — размеры доски (\(1 \le m, n \le 10^6\), \(1 \le m\times n \le 10^6\)).

В следующих \(m\) строках задано изначальное расположение фишек на доске.

В \(i\)-й строке (\(1 \le i \le m\)) находится строка \(a_{i1}a_{i2}\ldots a_{in}\) длины \(n\), задающая \(i\)-ю строку доски. Каждый символ \(a_{ij}\) является либо строчной буквой английского алфавита от <<a>> до <<z>>, либо точкой <<.>>. Если \(a_{ij}=\mbox{<<.>>}\), то клетка в \(i\)-й строке и \(j\)-м столбце является пустой, иначе в ней находится фишка, на которой написана буква \(a_{ij}\).

В последней строке заданы \(q\) символов \(s_1s_2\ldots s_q\) без пробелов, задающие последовательность операций (\(1 \le q \le 10^6\)). Каждый символ \(s_i\) является одним из символов <<L>>, <<R>>, <<U>> или <<D>>.

Сумма значений \(m \times n\) по всем наборам входных данных не превышает \(2\cdot 10^6\). Сумма значений \(q\) по всем наборам входных данных не превышает \(2\cdot 10^6\).

Формат выходных данных
Для каждого набора входных данных выведите итоговое расположение фишек на доске после выполнения всех операций в том же формате, что и во входных данных.

Обозначим через \(\sum mnq\) сумму \(mnq\) по всем наборам входных данных.

Обозначим через \(\sum mq\) сумму \(mq\) по всем наборам входных данных.

Назовем расположение фишек лестницей, если \(m=n\), \(a_{ij}={<<\texttt{.}>>}\) для всех \(1 \le i \le j \le n\) и \(a_{ij}\ne{<<\texttt{.}>>}\) для всех \(1 \le j < i \le n\). Иными словами, все фишки находятся на клетках ниже главной диагонали доски, и на каждой клетке ниже главной диагонали есть фишка.

Пояснения к примерам
В первом наборе входных данных из примера доска изначально выглядит так:

Первая операция сдвигает все фишки влево, так как \(s_1={<<\texttt{L}>>}\). После ее выполнения доска будет выглядеть следующим образом:

Вторая операция сдвигает все фишки вправо, так как \(s_2={<<\texttt{R}>>}\). После ее выполнения доска будет выглядеть следующим образом:

Третья и последняя операция сдвигает все фишки наверх, так как \(s_3={<<\texttt{U}>>}\). После ее выполнения доска будет выглядеть следующим образом:

Вдоль прямой улицы на равном расстоянии располагаются N домов. Будем считать расстояние между домами за единицу длины.
Около каждого дома можно поставить один фонарь. Всего имеется A фонарей, которые могут освещать дома на расстоянии X (включительно), и B фонарей, которые могут освещать дома на расстоянии Y (включительно). В частности, при X = 0 или Y = 0 такой фонарь освещает только тот дом, у которого он установлен.
Вам необходимо расставить минимальное число фонарей так, чтобы все дома были освещены. Один дом может быть освещён несколькими фонарями. Освещать участки улицы между домами необязательно.

Формат входных данных
Первая строка входных данных содержит целое число N (1 ≤ N ≤ 10⁵ ). Следующие четыре строки содержат целые неотрицательные числа A, X, B и Y соответственно, которые не превосходят 10⁵ .
Формат выходных данных
Программа должна вывести столько строк, сколько фонарей необходимо установить. Каждая строка должна содержать два целых числа через пробел — координату фонаря и расстояние, которое он освещает (то есть одно из чисел X или Y ). Координаты представляют из себя целые числа от 1 до N, рядом с каждым домом можно поставить только один фонарь. При наличии нескольких правильных ответов можно вывести любой из них. Если ответа не существует, программа должна вывести одно число −1

Замечание
В ответе к первому примеру фонарь у дома 2 освещает также дома 1 и 3, фонарь у дома 5 — также дома 3, 4, 6 и 7, а фонарь у дома 9 — также дома 8 и 10. В результате все дома освещены. Во втором примере фонарей недостаточно.

В городе Летовецк  "Фестиваль Чисел" отмечается всегда в день с магической датой. Дата называется магической, если день, номер месяца и две последние цифры года совпадают. Например, 01.01.01 - магическая дата. 
По текущей дате, записанной в формате дд.мм.гг определите дату, когда будет отмечатся ближайший "Фестиваль чисел". То есть первую магическую дату, которая была бы не ранее текущей.

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

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

Центральная площадь Зожбурга представляет собой прямоугольник, разделенный на одинаковые единичные квадраты. Строки пронумерованы сверху вниз с единицы, столбцы слева направо с единицы. Каждый квадрат площади имеет координаты \(r\) и \(c\) — номер строки и столбца, соответственно.

На площади находится прямоугольный газон со сторонами, параллельными сторонам площади. Координаты левого верхнего углового квадрата газона \((R_L, C_L)\), координаты правого нижнего углового квадрата газона \((R_R, C_R)\). Вокруг газона оборудованы \(n\) дорожек для \(n\) бегунов. Дорожка \(i\) находится на расстоянии \(i\) от границы газона, на дорожке \(i\) находится бегун с номером \(i\). Бегун \(i\) стартует с квадрата с координатами \((r_i, c_i)\). Бегуны стартуют одновременно с одинаковой скоростью: через каждую секунду каждый спорстмен меняет текущий квадрат на своей дорожке на следующий квадрат на своей дорожке в направлении против часовой стрелки.

На прямоугольном газоне в квадрате \((R_p, C_p)\) стоит фотограф, цель которого — сделать красивую фотографию. Фотограф тестирует инновационную камеру с двойным объективом. Эта камера делает снимок одновременно в двух противоположных направлениях. Фотограф считает фотографию красивой, если все бегуны в момент, когда он делает снимок, находятся в одновременно в строке \(R_p\) или в стоблце \(C_p\). При этом благодаря инновационному свойству камеры они могут быть либо в одной строке с ним и справа и слева от него, либо в одном столбце с фотографом и выше и ниже него.

Ваша задача — узнать, через какое минимальное количество секунд \(t\) после старта забега фотограф сможет сделать красивую фотографию, или сказать, что красивая фотография в данных условиях не получится.

Формат входных данных
В первой строке входных данных находится число \(n\) (\(1 \le n \le 18\)) — количество бегунов. В следующей строке ввода даны шесть целых чисел \(R_L\), \(C_L\), \(R_R\), \(C_R\) (\(n + 1 \le R_L \le R_R \le 100 - n\), \(n + 1 \le C_L \le C_R \le 100 - n\)), \(R_p\) (\(R_L \le R_p \le R_R\)), \(C_p\) (\(C_L \le C_p \le C_R\)) — координаты левого верхнего квадрата газона, правого нижнего квадрата газона, координаты фотографа, соответственно. Гарантируется, что \(R_R - R_L + C_R - C_L\) делится на \(4\).

В следующих \(n\) строках даны два числа \(r_i\), \(c_i\) — стартовые координаты бегуна \(i\). Гарантируется, что стартовые координаты бегуна \(i\) находятся на дорожке \(i\), на каждой дорожке находится один бегун, дорожка \(i\) находится на расстоянии \(i\) от границы газона.

Формат выходных данных
Выведите единственное число \(t\) — через какое минимальное количество секунд \(t\) после старта забега фотограф сможет сделать красивую фотографию, или \(-1\), если фотографию сделать не получится.

Рисунок ко второму примеру.

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

Каждая вершина может быть покрашена в один из \(c\) цветов или быть бесцветной. Изначально все вершины бесцветные.

Вам необходимо обрабатывать два типа запросов:

1. color(\(u\), \(x\)) Дана вершина \(u\), покрасить вершину \(u\) в цвет \(x\), а затем вызвать color(\(L\), \((x + 1) \bmod c\)) для ее левого сына \(L\) и color(\(R\), \((x - 1 + c) \bmod c\)) для её правого сына \(R\). Заметим, что эта операция перекрашивает все (бесконечное) множество вершин в поддереве вершины \(u\). Здесь \(\bmod\) — операция взятия числа по модулю. Если вершина уже была покрашена, то её цвет меняется на новый.

2. Дана вершина, вывести её текущий цвет.

Формат входных данных
В первой строке вводятся два числа \(q\), \(c\) — количество запросов и цветов, соответственно (\(1 \leq q \leq 5 \cdot 10^5\), \(1 \leq c \leq 10^9\)). Затем следует \(q\) запросов, каждый из которых начинается с целого числа \(t_i\) — типа \(i\)-го запроса.

Если \(t_i\) = 1, то далее в строке даётся целое число \(x\) (\(0 \leq x \leq c - 1\)) цвет, в который надо покрасить вершину запроса \(u\). В следующей строке описан путь до вершины \(u\) в виде непустой строки \(s_i\), состоящей из символов <<L>> и <<R>>. Данная строка задаёт путь от корня дерева до вершины \(u\), где <<L>> обозначает переход к левому сыну, а <<R>> "— к правому.

Если \(t_i\) = 2, то в следующей строке задаётся путь до вершины, цвет которой необходимо вывести, заданный аналогично предыдущему запросу.

Гарантируется, что сумма длин путей до всех вершин запросов не превосходит \(5 \cdot 10^5\).

Формат выходных данных
Для каждого запроса второго типа в новой строке необходимо вывести ответ на него. Если вершина бесцветная, необходимо вывести число \(-1\).

Одна из центральных площадей Архангельска замощена прямоугольными плитками размера \(1 \times k\). Если ввести систему координат, так что левый нижний угол одной из плиток будет иметь координаты \((0, 0)\), то левые нижние углы плиток будут иметь координаты \((i \cdot k+j,j)\) для всех целых \(i\) и \(j\).

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

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

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

Входные данные
Первая строка входных данных содержит два числа \(n\) и \(k\) — количество вершин в основании памятника и размер плитки.

Каждая из последующих \(n\) строк содержит два целых числа \(x_i\), \(y_i\) — координаты \(i\)-й вершины основания. Координаты перечислены в порядке обхода против часовой стрелки.

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

Замечание

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

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

Требуется написать программу, которая по данным \(n\) тройкам \((a_i, b_i, c_i)\) значений характеристик каждого из пользователей определяет количество пар потенциальных друзей, то есть таких пар индексов \(i < j\), что из трёх равенств \(a_i = a_j\), \(b_i = b_j\), \(c_i = c_j\) выполняется ровно одно.

Входные данные
Первая строка входных данных содержит число \(n\) — количество пользователей (1 ≤ n ≤ 100 000). Каждая из последующих \(n\) строк содержит три целых положительных числа \(a_i\), \(b_i\) и \(c_i\) — значения характеристик \(i\)-го пользователя (1 ≤ a_i , b_i , c_i ≤ 100)

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

Примечание
В первом примере потенциальную пару друзей образуют пользователи 1 и 2, а также 2 и 3. В обоих случаях у пользователей совпадает значение первой характеристики и различаются значения второй и третьей характеристик. Пользователи 1 и 3 имеют одинаковые значения первых двух характеристик, поэтому они не образуют пару потенциальных друзей.

Старинные часы бьют каждые полчаса. Причем в начале каждого часа они бьют столько раз, сколько сейчас часов (по 1 разу – в час ночи и в час дня, по 2 раза – в два часа ночи в два часа дня и т.д., в полночь и в полдень они бьют, соответственно, по 12 раз). И еще 1 раз они бьют в середине каждого часа.

Дан промежуток времени (известно, что прошло строго меньше 24 часов). Напишите программу, определяющую, сколько ударов сделали часы за это время.

Входные данные
В первой строке записан начальный момент времени, во второй строке — конечный. Моменты времени задаются двумя целыми числами, разделяющимися пробелом. Первое число задает часы (от 0 до 23), второе — минуты (от 1 до 59, при этом оно не равно 30).

Выходные данные
Выведите одно число — сколько ударов сделали часы за этот отрезок времени.