Задачи заочного тура личного первенства 2006

Даны два текста. Найти все слова, которые встречаются в обоих текстах сразу. Словом будем называть последовательность из прописных и строчных латинских букв (максимальная длина слов – 50 символов). Регистр букв игнорируется.

x-ray состоит из 2 слов X и RAY

Mary's состоит из 2 слов MARY и S

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

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

The tail wagging the dog.
The quick fox jumped over the lazy brown dog.

dog the

Среди целых положительных чисел, в десятичной записи которых присутствуют разряды только из заданного набора, найти наименьшее число, удовлетворяющее двум условиям: во-первых, сумма разрядов этого числа равна `N` и, во-вторых, это число кратно `M`. Если числа, удовлетворяющего этим условиям, не существует, вывести число –1.

В первой строке входного файла содержится единственное число `T` (1≤`T`≤50) –количество тестов во входном файле. В первой строке каждого теста содержится число `K` (1≤`K`≤10) – количество допустимых десятичных разрядов. Во второй строке через пробел записаны `K` различных десятичных разрядов (т.е. числа от 0 до 9). В третьей строке через пробел записаны числа `N` и `M` (1≤`N,\ M`≤500). Каждый новый тест записан с новой строки, пустых строк между тестами нет. Заданное ограничение по времени рассчитано на все тесты входного файла.

Для каждого теста вывести единственную строку, содержащую искомое число, или –1, если его не существует. Число не должно содержать ведущих нулей.

4
2
0 1
5 2
3
1 3 5
10 4
3
1 2 3
12 123
10
0 1 2 3 4 5 6 7 8 9
300 499

111110
-1
123123
5899999999999999899999999999999999

Есть прямоугольное поле размером `N\ times\ M`, разбитое на клетки единичного размера. В некоторых клетках этого поля расположены препятствия, и на них нельзя попасть, а для каждой из остальных клеток известно количество золота, которое в ней находится. У вас есть три робота, изначально они находятся в левом верхнем углу поля, и все они должны добраться до правого нижнего угла поля. За один ход каждый робот может сдвинуться на одну клетку вправо или на одну клетку вниз, если он при этом не выйдет за пределы поля и не попадет на клетку с препятствием. Находясь на определенной клетке, робот забирает из нее все золото. Взятое золото в клетке не восстанавливается, и другие роботы там уже ничего не получат. На одной клетке могут находиться несколько роботов. Когда все роботы добираются в правый нижний угол, подсчитывается суммарное количество золота, собранного ими. Требуется так провести роботов по полю, чтобы максимизировать это суммарное количество золота. Гарантируется, что роботов можно провести из левого верхнего в правый нижний угол.

В первой строке входного файла содержится два целых числа `N` и `M` (`2≤N,\ M≤50`). Далее следуют `N` строк, в каждой из которых содержится `M` целых чисел в диапазоне от `-1` до 1000 (числа в строке отделяются пробелами). Число, находящееся в `i`-й строке на `j`-м месте, равно количеству золота в соответствующей клетке поля или `-1`, если в этой клетке находится препятствие. В левом верхнем и в правом нижнем углах поля всегда находится ноль единиц золота.

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

3 3
0 5 7
3 8 6
9 -1 0

29

4 5
0 1 2 3 4
5 6 7 8 9
10 11 12 13 14
15 16 17 18 0

164