#3855

Ожерелье

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Муниципальный этап, Московская область, Интернет этап, 2011, Задача B ]

Дано ожерелье, состоящее из n красных или черных бусин, нанизанных на нить. Ожерелье представляет собой замкнутую окружность. Разрежем ожерелье на $\text{[math]}$ связных цепочек по k бусин. Требуется написать программу, которая вычислит максимальное количество цепочек, состоящих только из красных бусин, которое можно получить среди всех способов разрезать ожерелье.

Входные данные

В первой строке входных данных содержатся два натуральных числа n и k, не превышающие 10⁶. Гарантируется, что k является делителем числа n. Во второй строке даны n чисел, разделенных одним проблеом, каждое из которых равно 0 или 1. i-ое число в этой последовательности обозначает цвет i-ой бусины в порядке обхода по часовой стрелке: 0 — черный, а 1 — красный, соответственно.

Выходные данные

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

Примечание

Гарантируется, что решения, корректно работающие при ограничении N ≤ 10 000, будут оцениваться из 60 баллов.

Примеры

Входные данные

9 3
1 1 1 1 0 0 0 1 1

Выходные данные

Входные данные

9 3
0 1 1 1 1 0 1 1 1

Выходные данные

#3856

Короли

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Муниципальный этап, Московская область, Интернет этап, 2011, Задача C ]

Дано прямоугольное шахматное поле размером n × m клеток (n столбцов, m строк), на котором находятся два короля. Для каждого короля даны его начальные координаты (x, y) и начальный вектор скорости (v_x, v_y). Числа v_x и v_y обозначают, что за один ход фигура передвигается на v_x клеток по горизонтали и на v_y по верткали, при этом числа v_x и v_y могут принимать значения - 1, 0 и 1. Короли по очереди делают ходы в направлении своих векторов скоростей, меняя направления у стенок доски по закону отражения (при отражении от края доски одна из компонент скорости меняется, при отражении от угла меняются обе компоненты скорости). Если король после очередного хода попадает на клетку с королём противника, то он объявляется победителем и игра заканчивается. Первым ходит белый король.

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

Входные данные

В первой строке входного файла даны натуральные числа n и m (1 ≤ n, m ≤ 10⁶). Во второй строке находятся четыре целых числа x_w, y_w, v_x, w, v_y, w, задающие начальное положение и вестор скорости белого короля. В третьей строке даны четыре целых числа, x_b, y_b, v_x, b, v_y, b, задающие начальное положение и вектор скорости чёрного короля. Гарантируется, что 1 ≤ x_w, x_b ≤ n, 1 ≤ y_w, y_b ≤ m, - 1 ≤ v_x, w, v_y, w, v_x, b, v_y, b ≤ 1. Кроме того, гарантируется, что короли не могут иметь нулевой вектор скорости (обе компоненты не могут быть одноременно равны 0).

Выходные данные

В случае, если игра не закончится, в выходной файл следует выдать единственную строку «TIE». Если же игра закончится после k-го хода одного из королей, программа должна выдать строку, содержащую «WHITE k» или «BLACK k».

Примечание

Решения, корректно работающие при 1 ≤ n, m ≤ 50, будут набирать не менее 20 баллов. Решения, корректно работающие при 1 ≤ n, m ≤ 1000, будут набирать не менее 50 баллов.

Примеры

Входные данные

3 3
1 2 1 1
2 1 1 1

Выходные данные

WHITE 2

Входные данные

3 3
1 1 1 1
3 1 1 1

Выходные данные

BLACK 1

#3857

Головоломка

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Муниципальный этап, Московская область, Интернет этап, 2011, Задача D ]

Картина в голове Штирлица не складывалась. За год из Центра поступило N · M фрагментов нового задания. Штирлиц запомнил каждый фрагмент и теперь складывает из них целое сообщение.

Текст задания записан на клетчатой прямоугольной странице размера (5N) × (5M), который разрезан на N · M частей. Каждый фрагмент сообщения можно представить квадратом 5 × 5 (серые клетки), у которого с каждого краю (заштрихованные области) может быть только один «выступ» или «впадина». Обратите внимание, что к краям не относятся углы квадрата (см. иллюстрацию).

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

$\text{[math]}$

Фрагмент может иметь ровную сторону (т.е. не имеет выступа или впадины) только если соответствующая сторона фрагмента является границей сообщения.

Требуется написать программу, которая поможет Штирлицу собрать из фрагментов целое сообщение.

Входные данные

В первой строке входных данных даются размеры сообщения — натуральные числа N и M (1 ≤ N ≤ 5, 1 ≤ M ≤ 4).

В следующих 7 · N · M строках по 7 символов задаются фрагменты сообщения. Каждый фрагмент состоит из 7 строк. Пустая часть фрагмента задается символами «.», а часть фрагмента, содержащая текст, символами «#».

Выходные данные

Выведите 7 · N строк по 7 · M символов, задающих как надо разложить части, чтобы получить целое сообщение. Части сообщения можно совмещать только параллельным переносом (то есть, запрещается поворачивать и переворачивать фрагменты сообщения).

Примечание

Если существует несколько способов восстановить сообщение, требуется вывести любой из них. Решения, корректно работающие при ограничениях N · M ≤ 10, оцениваются в 50 баллов.

Примеры

Входные данные

1 2
.......
.#####.
.#####.
.####..
.#####.
.#####.
.......
.......
.#####.
.#####.
######.
.#####.
.#####.
.......

Выходные данные

..............
.#####..#####.
.#####..#####.
.####..######.
.#####..#####.
.#####..#####.
..............

#3864

Цапли

Темы: [Целые числа]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Региональный этап, 2012, 1 день, Задача A ]

Петя и Маша пришли в зоопарк. Больше всего Пете понравились цапли. Он был поражен их способностью спать на одной ноге.

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

Через несколько минут к вольеру подошла Маша. За это время некоторые цапли могли поменять позу, поэтому Петя предложил ей заново пересчитать видимые ноги цапель. Когда Маша это сделала, у нее получилось число b.

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

Требуется написать программу, которая по заданным числам a и b выведет минимальное и максимальное количество цапель, которое могло быть в вольере.

Входные данные

Входной файл содержит два целых числа a и b, разделенных ровно одним пробелом (1 ≤ a ≤ 10⁹, 1 ≤ b ≤ 10⁹).

Выходные данные

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

Примечание к примеру тестов

В приведенном примере возможны следующие варианты:

В вольере две цапли. Когда Петя считал ноги, одна цапля стояла на двух ногах, а другая — на одной. Петя насчитал три ноги. Когда Маша считала ноги, обе цапли стояли на двух ногах, Маша насчитала четыре ноги.
В вольере три цапли. Когда Петя считал ноги, все цапли стояли на одной ноге, Петя насчитал три ноги. Когда Маша считала ноги, одна цапля стояла на двух ногах, а еще две — на одной. Маша насчитала четыре ноги.

Примеры

Входные данные

3 4

Выходные данные

2 3

#3865

Круглый стол

Темы: [Жадный алгоритм]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Региональный этап, 2012, 1 день, Задача B ]

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

Руководитель клуба Иван Петрович недавно заметил, что не все ребята активно участвуют в обсуждении. Понаблюдав за несколькими заседаниями клуба, он заметил, что активность члена клуба зависит от того, кто с кем сидит рядом.

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

Желая сделать заседание клуба как можно более интересным, Иван Петрович решил разместить участников за круглым столом таким образом, чтобы как можно больше членов клуба приняло активное участие в обсуждении.

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

Входные данные

Входной файл содержит два целых числа m и n, разделенных ровно одним пробелом (0 ≤ m ≤ 1000, 0 ≤ n ≤ 1000, m + n ≥ 3).

Выходные данные

Выходной файл должен содержать строку с расположенными в некотором порядке m символами «B» (заглавная латинская буква) и n символами «G» (заглавная латинская буква). Символ «B» означает мальчика, а символ «G» — девочку.

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

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

В первом примере все члены клуба примут активное участие в обсуждении.

Во втором примере мальчики примут активное участие в обсуждении, а девочки нет. В этом примере можно также разместить членов клуба следующим образом: «BBGG». В этом случае активное участие в обсуждении примут обе девочки, а мальчики — нет. Разместить всех так, чтобы три или четыре члена клуба приняли активное участие в обсуждении, нельзя.

Примеры

Входные данные

1 2

Выходные данные

BGG

Входные данные

2 2

Выходные данные

BGBG