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

Автор:A. Klenin   Ограничение времени:5 сек
Входной файл:input.txt   Ограничение памяти:200 Мб
Выходной файл:output.txt  

Условие

Имеется текст и N слов. Длина текста L символов, длина каждого слова — от 1 до 255 символов. Требуется для каждого слова определить, входит ли оно в текст. Все слова и текст состоят из латинских букв. Заглавные и строчные буквы считаются различными.

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

В первой строке входного файла содержится текст, во второй — число N, в следующих N строках — слова.

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

Выходной файле должен содержать N чисел 1 или 0, обозначающих, что соответствующее слово входит или не входит в текст.

Ограничения

1 ≤ L ≤ 255, 1 ≤ N ≤ 1000.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
Longlongstring
2
short
string
0 1

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

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб

Условие

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

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

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

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

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

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

Стандартный вход Стандартный выход
1
1 2 0 3 4 0 5 10
1 0 3 0 5 10
2
11 0 0 12
0 12

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

Автор:Г. Гренкин   Ограничение времени:5 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

Дан массив целых чисел a1, a2, ..., aN и дано M команд типа "найти сумму чисел ai для i от l до r".

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

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

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

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

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

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

Ограничения

1 ≤ N ≤ 1000000

1 ≤ M ≤ 1000000

 − 1000 ≤ ai ≤ 1000

1 ≤ lj ≤ rj ≤ N

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

Входной файл (input.txt) Выходной файл (output.txt)
1
5
1 2 3 4 5
3
1 3
2 5
3 5
6 14 12

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

Автор:А. Жуплев   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

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

Имеется шахматная доска 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

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

Входной файл (input.txt) Выходной файл (output.txt)
1
8
3 5
#.#.#.*.
.#.#.*.#
*.#.*.#.
.*.*.#.#
#.X.#.#.
.*.*.#.#
*.#.*.#.
.#.#.*.#
2
3 1 2
#*#
X#.
#*#

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

Автор:Московская олимпиада для 7-9 кл., 2005   Ограничение времени:3 сек
Входной файл:b.in   Ограничение памяти:64 Мб
Выходной файл:b.out  

Условие

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

1 2 3 4 5 4 3 2 1
1 2 1 2 2 1 2 1
Вашей программе будет дана последовательность чисел. Требуется определить, какое минимальное количество и каких чисел надо приписать в конец этой последовательности, чтобы она стала симметричной.

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

Во входном файле записано сначала число N — количество элементов исходной последовательности. Далее записано N чисел — элементы этой последовательности. Элементы последовательности — натуральные числа от 1 до 9.

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

В выходной файл выведите сначала число M — минимальное количество элементов, которое надо дописать к последовательности, а потом M чисел (каждое - от 1 до 9) — числа, которые надо дописать к последовательности.

Ограничения

1 ≤ N ≤ 100

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

Входной файл (b.in) Выходной файл (b.out)
1
9
1 2 3 4 5 4 3 2 1
0
2
5
1 2 1 2 2
3
1 2 1
3
5
1 2 3 4 5
4
4 3 2 1

Problem G. Jigsaw separation

Author:A. Klenin   Time limit:1 sec
Input file:input.txt   Memory limit:256 Mb
Output file:output.txt  

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

No. Input file (input.txt) Output file (output.txt)
1
4 3
XXXX
XOXO
OOOO
YES
2
3 3
XXX
XOX
XXX
NO

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

Автор:Г. Гренкин   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

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

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

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

Входной файл содержит числа x1 y1 x2 y2 — координаты первой и второй пешек.

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

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

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3 6 7 5
0
2
3 4 5 6
4 5
3
4 5 5 6
0

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

Автор:А. Кленин, Е. Шавлюгин   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

Дана шахматная доска размером 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.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
4 2
1 1  2 1  3 1  4 1  4 2  3 2  2 2  1 2

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

Автор:Центральная предметно-методическая комиссия по информатике   Ограничение времени:1 сек
Входной файл:prizes.in   Ограничение памяти:256 Мб
Выходной файл:prizes.out  

Условие

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

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

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

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

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

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

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

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

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

3 ≤ n ≤ 50, 1 ≤ ai ≤ 105.

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

3 ≤ n ≤ 5000, 1 ≤ ai ≤ 105.

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

3 ≤ n ≤ 100000, 1 ≤ ai ≤ 109.

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

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

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

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

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

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

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

Ограничения

3≤ n ≤ 100000, 1 ≤ k ≤ n / 3, 1≤ ai ≤ 109.

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

Входной файл (prizes.in) Выходной файл (prizes.out)
1
10 2
1 2 4 5 2 4 2 2 1 6
7

Задача K. POBEDA-2014

Автор:Центральная предметно-методическая комиссия по информатике   Ограничение времени:2 сек
Входной файл:pobeda.in   Ограничение памяти:256 Мб
Выходной файл:pobeda.out  

Условие

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

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

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

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

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

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

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

Частичные правильные решения для тестов, в которых a1, a2, a3, a4 ≤ 100000, будут оцениваться из 50 баллов.

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

Первая строка входного файла содержит разделенные пробелами четыре целых числа: a1, a2, a3, a4. Входные данные могут превышать максимальные значения для 32 битного типа данных.

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

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

Ограничения

0 ≤ a1, a2, a3, a4 ≤ 1018;

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

Входной файл (pobeda.in) Выходной файл (pobeda.out)
1
2 2 2 2
2
2
10 10 0 0
3

0.495s 0.016s 35