Задача 1. Распознавание метки ≡

Условие

Приложение дополненной реальности пытается найти на изображении, полученном с камеры телефона, метку, представляющую собой ярко раскрашенный прямоугольник. Благодаря контрастному цвету прямоугольника на этапе предварительной обработки изображение удалось преобразовать в массив из W на H элементов, каждый из которых равен либо '#' (ASCII 35), если он принадлежит прямоугольнику, либо '.' (ASCII 46) в противном случае.

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

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

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

Первая строка входного файла содержит целые числа W H N. Следующие H строк содержат по W символов . и # каждая — изображение после предварительной обработки.

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

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

Ограничения

1 ≤ W, H ≤ 100, 0 ≤ N ≤ W × H

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

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

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

3 3 1
.#.
##.
...

3

2 2 0
#.
.#

0

Задача 2. Полоса препятствий ≡

Условие

Одно из заданий на соревнованиях по подводной робототехнике — полоса препятствий. Полоса состоит из n подряд идущих стен, высота i-й стены h_i.

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

Робот имеет ограниченный заряд батареи. Изначально он способен подняться над стеной высотой k или меньше, далее после каждого подъёма максимальная высота стены, которую может преодолеть робот, снижается на 1.

Робот поддерживает две команды: D — идти через подкоп (если подкопа ещё нет, то робот выкапывает его), U — проплыть над препятствием.

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

Первая строка входного файла содержит целые числа n m k. Следующая строка содержат n целых чисел h_i - высоты стен.

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

Выходной файл должен содержать строку NO, если задание выполнить невозможно. В противном случае — две строки: строку YES и строку из 2n символов U и D — последовательность команд робота, которая позволит ему преодолеть полосу препятствий и вернуться обратно. Первые n символов содержат описание прохождение от стены с номером 1 до стены с номером n, следующие n символов содержат описание прохождения от стены с номером n до стены с номером 1.

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

Ограничения

1 ≤ n, m ≤ 10⁵, 1 ≤ k, h_i ≤ 10⁹

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

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

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

10 5 10
10 1 4 2 4 3 4 4 8 9

YES
DUDUDUUUDDDDUUUDUDUD

5 1 1
5 5 5 5 5

NO

10 10 10000
13123 141323 213323 3213 213213 321 323213 1323 213 1232113

YES
DDDDDDDDDDDDDDDDDDDD

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

Условие

Программа для робота 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

Задача A1. Hello, world! ≡

Условие

Требуется написать программу, которая печатает "Hello, world!" (без кавычек)

Задача A2. Сложение чисел ≡

Условие

Вам необходимо написать программу, которая определяет сумму двух чисел A и B.

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

В первой строке записано два целых числа A и B.

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

Выведите единственное целое число — сумму чисел A и B.

Ограничения

1 ≤ A, B ≤ 10⁹

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

Баллы начисляются пропорционально количеству пройденных тестов.

По запросу сообщается количество набранных баллов.

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

2 7

9

22 88

110

Задача A3. FizzBuzz ≡

Условие

Требуется написать программу, которая считывает число и выводит Fizz, если число делится на 3, Buzz, если число делится на 5, и FizzBuzz, если оно делится и на 3, и на 5. Если число не делится ни на 3, ни на 5, вывести пустую строку (перевод строки).

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

23

25

Buzz

30

FizzBuzz

Задача A4. Олины торты ≡

Условие

Сегодня к Оле в гости придет N одногруппников, из-за чего она решила приготовить N тортов. В ее распоряжении есть M грамм сахара. Поскольку Оля не хочет никого обидеть, в каждом торте должно быть одинаковое количество сахара. Какое максимальное количество сахара может содержать каждый торт?

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

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

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

Необходимо вывести единственное число — максимальное количество сахара.

Ограничения

1 < N, M < 10000

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

10
2

5

6
4

1.5

Задача A5. Игра в предложения ≡

Условие

Паша, Аня, Оля и Оргрим играют в игру, в которой нужно восстановить предложение по его словам, произнесенным в обратном порядке.

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

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

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

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

Ограничения

1 ≤ N ≤ 100

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

4
cha
g'thazag
mog
Bin

Bin
mog
g'thazag
cha

Задача B2. Убрать соседа ≡

Условие

Дан массив чисел. Необходимо удалить элементы, за которыми в этом массиве следует ноль.

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

Входные данные содержат ряд чисел, разделенных пробелом.

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

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

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

1 2 0 3 4 0 5 10

1 0 3 0 5 10

11 0 0 12

0 12

Задача B3. Короткий текст и немного слов ≡

Условие

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

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

Ограничения

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

Longlongstring
2
short
string

0 1

Задача B4. Многократное суммирование ≡

Условие

Дан массив целых чисел a₁, a₂, ..., a_N и дано M команд типа "найти сумму чисел a_i для i от l до r".

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

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

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

Далее во входном файле содержится целое число M, за которым следуют M пар целых чисел l_j r_j.

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

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

Ограничения

1 ≤ N ≤ 1000000

1 ≤ M ≤ 1000000

 − 1000 ≤ a_i ≤ 1000

1 ≤ l_j ≤ r_j ≤ N

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

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

6 14 12

Задача B5. Две пешки и слон ≡

Условие

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

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

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

Входной файл содержит числа x₁ y₁ x₂ y₂ — координаты первой и второй пешек.

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

Если задача имеет решение, то выходной файл должен содержать два числа — координаты слона. Если решений несколько, вывести любое из них. Если задача не имеет решения, вывести единственное число 0.

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

3 6 7 5

0

3 4 5 6

4 5

4 5 5 6

0