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

Условие

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

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

Ограничения

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

Longlongstring
2
short
string

0 1

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

Условие

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

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

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

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

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

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

1 2 0 3 4 0 5 10

1 0 3 0 5 10

11 0 0 12

0 12

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

Условие

Дан массив целых чисел 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

Задача E. Слон на шахматной доске ≡

Условие

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

Имеется шахматная доска N на N клеток. В клетке с координатами (X; Y) находится слон. Требуется вывести шахматную доску с изображением слона и всех клеток, в которые он может походить.

Клетки чёрного цвета обозначаются символом '#' (ASCII 35), клетки белого цвета обозначаются символом '.' (точка, ASCII 46), клетка со слоном обозначается символом 'X' (ASCII 88), клетка, в которую может походить слон обозначается символом '*' (ASCII 42).

Ось ординат (OY) направлена вертикально вниз. Верхний левый угол доски имеет чёрный цвет и координаты (1; 1).

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

Входной файл содержит целые числа N X Y.

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

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

Ограничения

2 ≤ N ≤ 100

1 ≤ X, Y ≤ N

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

8
3 5

#.#.#.*.
.#.#.*.#
*.#.*.#.
.*.*.#.#
#.X.#.#.
.*.*.#.#
*.#.*.#.
.#.#.*.#

3 1 2

#*#
X#.
#*#

Задача F. Симметричная последовательность ≡

Условие

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

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

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

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

Ограничения

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

9
1 2 3 4 5 4 3 2 1

0

5
1 2 1 2 2

3
1 2 1

5
1 2 3 4 5

4
4 3 2 1

Problem G. Jigsaw separation ≡

Statement

Rectangular jigsaw puzzle consists of two pieces. Each piece is a 4-connected set of square cells, each cell represented by character 'X' or 'O'.

Your program must determine whether it is possible to separate puzzle pieces by moving either of them in vertical or horizontal direction.

In the first sample it is possible to separate pieces by moving 'X' piece up and/or 'O' piece down.

Input file format

First line of input contains two integers W H. Following H lines contain W characters each — puzzle representation.

Output file format

Output must contain a single string YES or NO.

Constraints

1 ≤ W, H ≤ 100. Each piece contains at least one cell.

Sample tests

4 3
XXXX
XOXO
OOOO

YES

3 3
XXX
XOX
XXX

NO

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

Условие

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

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

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

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

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

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

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

3 6 7 5

0

3 4 5 6

4 5

4 5 5 6

0

Задача I. Шахматный король ≡

Условие

Дана шахматная доска размером N × M клеток. Клетки на ней обозначаются парами координат — номерами вертикали и горизонтали.

В клетке (1, 1) расположен шахматный король. Требуется обойти королём доску, побывав в каждой клетке ровно один раз, и вернувшись в исходную позицию.

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

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

Входной файл содержит числа N M.

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

Выходной файл должен содержать N × M пар чисел v h — координаты клеток, через которые проходит путь короля (1 ≤ v ≤ N, 1 ≤ h ≤ M). Первая клетка в пути должна иметь координаты (1, 1), а последняя — (1, 2), (2, 1) или (2, 2). Если имеется несколько решений, вывести любое из них.

Ограничения

2 ≤ N, M ≤ 100.

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

4 2

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

Задача J. Призы ≡

Условие

Алиса и Боб стали победителями телевикторины, и теперь им предстоит выбрать себе призы. На выбор предлагается n призов, пронумерованных от 1 до n.

Распределение призов происходит следующим образом. Организаторы телевикторины сообщают победителям целое положительное число k (1 ≤ k ≤ n / 3). Сначала Алиса выбирает себе любые k подряд идущих номеров призов. Потом Боб выбирает себе k подряд идущих номеров призов, при этом он не может выбирать номера, которые уже выбрала Алиса. После этого победители забирают выбранные ими призы.

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

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

Пояснения к примерам

В приведенном примере Алиса может, например, выбрать 4-й и 5-й призы. После этого для Боба оптимально выбрать 9-й и 10-й призы с суммарной ценностью 7.

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

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

Подзадача 1 (30 баллов)

3 ≤ n ≤ 50, 1 ≤ a_i ≤ 10⁵.

Подзадача 2 (30 баллов)

3 ≤ n ≤ 5000, 1 ≤ a_i ≤ 10⁵.

Подзадача 3 (40 баллов)

3 ≤ n ≤ 100000, 1 ≤ a_i ≤ 10⁹.

Получение информации о результатах окончательной проверки

По запросу сообщается результат окончательной проверки на каждом тесте.

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

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

Вторая строка содержит n целых положительных чисел: a₁, a₂, …, a_n. Для каждого приза указана его ценность для Боба.

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

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

Ограничения

3 ≤ n ≤ 100000, 1 ≤ k ≤ n / 3, 1 ≤ a_i ≤ 10⁹.

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

10 2
1 2 4 5 2 4 2 2 1 6

7

Задача K. POBEDA-2014 ≡

Условие

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

Длина катета каждого из представленных выше треугольников равна одному сантиметру. За один такт видеокарта не может отобразить более чем a_i треугольников i-того типа.

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

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

Пояснения к примерам

Далее приведен рисунок для первого примера.

Система оценивания

Частичные правильные решения для тестов, в которых a₁, a₂, a₃, a₄ ≤ 100000, будут оцениваться из 50 баллов.

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

Первая строка входного файла содержит разделенные пробелами четыре целых числа: a₁, a₂, a₃, a₄. Входные данные могут превышать максимальные значения для 32 битного типа данных.

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

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

Ограничения

0 ≤ a₁, a₂, a₃, a₄ ≤ 10¹⁸;

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

2 2 2 2

2

10 10 0 0

3