Задача A. Программирование робота ≡

Условие

Программа для робота X представляет из себя последовательность из 0 и 1. Известно, что если в коде содержится K подряд стоящих 0 или 1, то робот сбрасывается к заводским настройкам.

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

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

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

Первая строка входных данных содержит два целых числа n и k. Вторая строка входных данных содержит строку длины n, состоящую из 0 и 1.

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

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

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

Ограничения

3 ≤ n, k ≤ 3 ⋅ 10⁵

Описание подзадач и системы оценивания

Решения, работающие для n ≤ 3, оцениваются из 20 баллов. Решения для n ≤ 10 оцениваются из 50 баллов. Баллы выставляются за каждый успешно пройденный тест.

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

3 3
111

110

10 3
1110001110

1100101100

3 3
101

101

Задача B. Усовершенствование космического корабля ≡

Условие

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

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

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

Первая строка содержит одно целое число N — количество вершин в многоугольнике описывающем, космический корабль. Следующие N строк содержат N пар вещественных чисел (x_i, y_i) (по одной в строке) — координаты вершин выпуклого многоугольника, описывающего космический корабль, в порядке обхода.

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

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

Ограничения

 − 10000 ≤ x_i, y_i ≤ 10000

3 ≤ N ≤ 10⁴

Описание подзадач и системы оценивания

Баллы выставляются за каждый успешно пройденный тест.

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

6
0.5 0.5
3 0
5 2
3 3
1 3
0 2

3

4
0 0
0 1
1 1
1 0

3

Задача C. Слон Пахом и разработка RPG ≡

Условие

Слон Пахом создаёт новую RPG, для игры ему потребовался уровень-лабиринт. Лабиринт содержит n × m платформ, n рядов по m платформ. Платформы бывают трёх видов:

1. Коридоры. В зависимости от ориентации обозначаются или символом "-" (находясь на такой платформе можно, пройти только влево или вправо) или "|" (находясь на такой платформе, можно пройти только вверх или вниз).
2. Перекрёстки. Обозначаются символом "+" (можно пройти в любую сторону).
3. Стены. Обозначаются символом "#" (по ним нельзя пройти).

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

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

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

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

Первая строка входных данных содержит два целых числа n и m. Следующие n строк содержат по m символов каждая — описание лабиринта.

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

Первая строка выходных данных должна содержать "YES", если лабиринт проходимый, в противном случае "NO".

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

Ограничения

1 ≤ n, m ≤ 10³

Описание подзадач и системы оценивания

Решения, работающие для n = 1, оцениваются из 30 баллов. Баллы выставляются за каждый успешно пройденный тест.

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

5 5
+++++
+++++
+++++
+++++
+++++

YES
0

1 8
+-------

YES
0

1 8
+------|

NO

5 6
|-----
|-###-
#|---#
####|#
+++#|-

YES
5

1 1
#

NO