Задача A. Котенок Гав и сосиски ≡

Условие

В распоряжение котенка Гава и щенка Шарика поступила лента из N сосисок. Они договорились есть ее с разных концов до тех пор, пока не встретятся. Гав съедает V_Gav сосисок в секунду, а Шарик — V_Sharik сосисок в секунду.

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

Формат входного файла

Формат выходного файла

Выходной файл должен содержать два числа: сначала количество сосисок, целиком съеденных Гавом, а затем количество сосисок, целиком съеденных Шариком.

Ограничения

Примеры тестов

10 1 2

3 6

2 5 3

1 0

2 5 5

1 1

Задача B. Настройка гитары ≡

Условие

Однажды программист Вася решил научиться играть на гитаре. Первым делом он выучил правила настройки гитары.

Первая струна настраивается по камертону. Каждая следующая струна настраивается по предыдущей, а именно:

• вторая струна, зажатая на пятом ладу, звучит в унисон с открытой первой;
• третья струна, зажатая на четвёртом ладу, звучит в унисон с открытой второй;
• четвёртая струна, зажатая на пятом ладу, звучит в унисон с открытой третьей;
• пятая струна, зажатая на пятом ладу, звучит в унисон с открытой четвёртой;
• шестая струна, зажатая на пятом ладу, звучит в унисон с открытой пятой.

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

Формат входного файла

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

i-ый символ входной строки показывает как звучит (i + 1)-ая струна относительно i-ой, а именно:

• < (ASCII 60) — (i + 1)-ая струна, зажатая на соответствующем ладу, звучит ниже открытой i-ой;
• = (ASCII 61) — (i + 1)-ая струна, зажатая на соответствующем ладу, звучит в унисон с открытой i-ой;
• > (ASCII 62) — (i + 1)-ая струна, зажатая на соответствующем ладу, звучит выше открытой i-ой.

Формат выходного файла

В выходном файле должна содержаться строка из 5 символов, описывающая действия, которые требуется произвести для настройки гитары. В i-ой позиции строке должен содержаться символ, описывающий действие над (i + 1)-ой струной:

• * (ASCII 42) — ничего не делать;
• + (ASCII 43) — натянуть (повысить частоту звучания);
• - (ASCII 45) — ослабить (понизить частоту звучания);
• ? (ASCII 63) — невозможно определить.

Примеры тестов

=====

*****

=<=<=

*++++

>==<=

---??

Задача C. Древнее сложение ≡

Условие

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

Каждая цифра представлялась с помощью трёх символов, имевших значения:

• «ракушка» * — ноль,
• «точка» . — один,
• «черта» | — пять.

• сумма их значений равна значению записываемой цифры,
• количество использованных символов минимально,
• символы «точка» предшествуют символам «черта».

Требуется по двум заданным в записи майя числам определить их сумму и представить в той же записи.

Формат входного файла

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

Символ «ракушка» обозначается '*' (ASCII 42), «точка» — '.' (ASCII 46), «черта» — '|' (ASCII 124). Разряды отделяются друг от друга пробелом (ASCII 32).

Формат выходного файла

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

Ограничения

Оба числа не превосходят 10⁹.

Строки во входном файле содержат от 1 до 255 символов.

Примеры тестов

.
..

...

.|
....|

|||

.. | .||
| ..||

.. .|| ...

Задача D. Индикатор загрузки ≡

Условие

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

Индикатор загрузки представляет собой поле n × m пикселей, отражающее состояние загрузки некоторого файла размером n ⋅ m байт. Все пиксели индикатора нумеруются от 1 до n ⋅ m слева направо сверху вниз, при этом пиксель c номером i окрашен в чёрный цвет, если i-й по счёту байт файла уже загружен, и в белый цвет — в противном случае.

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

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

Формат входного файла

В первой строке входного файла находятся целые числа n m b. Вторая строка содержит четыре числа r₁ c₁ r₂ c₂ — координаты видимой части индикатора. Следующие r₂ − r₁ + 1 строк по c₂ − c₁ + 1 символов каждая описывают видимую часть изображения: строки с r₁-й по r₂-ю, столбцы с c₁-го по c₂-й. Символ '=' (ASCII 61) обозначает чёрный пиксель, символ '.' (ASCII 46) — белый.

Формат выходного файла

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

Ограничения

1 ≤ n, m ≤ 10⁴, 1 ≤ b ≤ n ⋅ m, n ⋅ m делится на b нацело.

1 ≤ r₁ ≤ r₂ ≤ n, 1 ≤ c₁ ≤ c₂ ≤ m, r₂ − r₁ ≤ 100, c₂ − c₁ ≤ 100.

Примеры тестов

5 7 5
2 3 2 3
.

0 28

5 7 5
1 5 3 7
.==
==.
..=

21 21

Задача E. Нарезка фантиков ≡

Условие

Для производства конфетных фантиков изготовлена длинная узкая лента с напечатанными на ней картинками. Длина каждой картинки — L мм, расстояние между двумя соседними картинками — d мм, расстояние от начала ленты до первой картинки — a мм.

Нужно получить N фантиков длиной W мм каждый. Аппарат по производству фантиков работает так: сперва от начала ленты отрезается и выбрасывается кусок длиной x мм. Затем от начала ленты один за другим отрезаются фантики длиной W мм каждый.

Каким должно быть x, чтобы на каждом фантике была целиком расположена ровно одна картинка? Картинки, попадающие на фантик только частично, не считаются.

Формат входного файла

Входной файл содержит целые числа L d a N W.

Формат выходного файла

Выходной файл должен содержать целое число x.

Число x должно удовлетворять неравенству 0 ≤ x < L + d.

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

Ограничения

1 ≤ N, L, W, d ≤ 1000.

0 ≤ a < L + d.

Гарантируется, что существует хотя бы одно решение.

Примеры тестов

3 1 2 3 7

1

Задача F. Золотая середина ≡

Условие

Центральным элементом набора из k чисел называется такой элемент, который после сортировки набора будет занимать в нём центральную позицию (то есть позицию номер ⌈k / 2⌉, считая с единицы).

Числа добавляются в изначально пустой набор в заданном порядке. Требуется определить значения центрального элемента после добавления каждого числа.

Формат входного файла

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

Формат выходного файла

Выходной файл должен содержать n целых чисел — значения центрального элемента после каждого добавления.

Ограничения

1 ≤ n ≤ 10⁶,  − 10⁹ ≤ a_i ≤ 10⁹.

Примеры тестов

3
5 3 4

5 3 4

5
1 2 3 2 4

1 1 2 2 2

Задача G. Оригами ≡

Условие

Складывание фигуры начинается с квадратного листа бумаги, лежащего на специальной (также квадратной) учебной доске для оригами. Доска размечена на n × n клеток, стороны которых параллельны её краям. Через все клетки доски проведены диагонали двух типов: пересекающие клетки сверху вниз слева направо (\) и справа налево (/). Две диагонали, соединяющие противоположные углы доски, называются главными.

Схема складывания фигуры состоит из последовательных указаний о сгибах. Каждый сгиб проходит вдоль одной из 4 n − 2 диагоналей доски, при этом бумага всегда загибается в сторону центра доски. Таким образом, для диагоналей, расположенных выше главной, возможен только сгиб вниз, для диагоналей, расположенных ниже главной, — только сгиб вверх. Сгиб, проходящий через главную диагональ, возможен как в одну, так и в другую сторону.

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

Ниже показан процесс складывания фигуры по схеме, приведённой в примере 2.

→

→

Формат входного файла

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

Каждый сгиб задаётся положением диагонали, вдоль которой он должен быть произведён, и состоит из трёх компонент.

1. Тип диагонали — символ '/' (ASCII 47) или '\' (ASCII 92).
2. Направление сгиба листа — символ 'u' (ASCII 117) для сгиба вниз или 'l' (ASCII 108) для сгиба вверх; однозначно определяет положение относительно главной диагонали.
3. Номер диагонали — целое число от 1 до n. Диагонали каждого типа, расположенные по одну сторону от главной, нумеруются по возрастанию от угла доски к главной диагонали.

Формат выходного файла

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

Ограничения

1 ≤ n ≤ 100, 0 ≤ m ≤ 4 n − 2.

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

Примеры тестов

3 2
\u1/u3

~~^
~,#
,##

4 3
/l3\u2/u3

~~^~
~,#>
,##~
#'~~

Задача H. Модель Изинга ≡

Условие

Модель Изинга используется в физике для описания твердого тела. Она использует представление кристаллической решетки, в узлах которой находятся атомы.

Рассмотрим плоскую прямоугольную решетку с N узлами по вертикали и M узлами по горизонтали (всего NM узлов). Каждый узел характеризуется своим спином, который может принимать значения  + 1 или  − 1.

Соседними считаются узлы решётки, смежные по горизонтали или вертикали. Назовём энергией решетки количество пар соседних узлов с различными спинами.

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

Энергия решетки, приведенной в примере, равна 13. После изменения спина левого верхнего узла и третьего узла во второй строке получим решетку с энергией 15.

Формат входного файла

Формат выходного файла

В выходной файл выведите четыре числа: r₁ c₁ r₂ c₂  — координаты двух узлов, изменение спина в которых максимально увеличит энергию. r_i  — номер строки узла, c_i  — номер узла в его строке. Нумерация начинается с 1.

Ограничения

Примеры тестов

3 4
+-+-
-+++
+-+-

1 1 2 3

Задача I. Беговые дорожки ≡

Условие

Между n спортсменами организуется соревнование по бегу. К сожалению, в распоряжении организаторов имеется стадион лишь с n − 1 беговой дорожкой, поэтому одновременно могут состязаться только n − 1 из n участников. По этой причине соревнования разбиваются на несколько забегов.

Правила соревнований требуют, чтобы каждый из бегунов:

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

Кроме того, некоторые пары спортсменов во избежание конфликтов нельзя выставлять на соседние дорожки в забеге. При этом у каждого из участников есть не более одного «неприятного» ему конкурента, и чувство антипатии является взаимным.

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

Формат входного файла

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

Формат выходного файла

Первая строка выходного файла должна содержать число забегов r в предлагаемой схеме. Следующие r строк должны состоять из n − 1 числа — номеров спортсменов, выставляемых на дорожки в каждом из забегов.

Ограничения

2 ≤ n ≤ 100.

1 ≤ r ≤ 1000.

Примеры тестов

4 1
2 3

4
4 2 1
1 3 4
2 1 3
3 4 2