Отбор локальных участников проводится по результатам заочного тура.
Необходимо решить не менее одной задачи. Для участия вне конкурса в Интернет-версии соревнований необходима только регистрация,
участие в заочном туре необязательно.
Во всех задачах ввод осуществляется из стандартного ввода (stdin, т.е. клавиатура, но не используйте USE CRT), а вывод
на стандартный вывод (stdout, т.е. экран).
Программа на выполнение запускается по команде:
PROGRAM <INPUT.TXT >OUTPUT.TXT
поэтому в программе не должно быть подсказок для ввода и отладочной печати. Формат входного файла соответствует
спецификации, дополнительные проверки не нужны. Все строки, в том числе последняя, оканчиваются символом перехода на новую строку.
Время выполнения одного теста во всех задачах равно 2 секунды на компьютере жюри.
Для проверки решений используются компиляторы Free Pascal (совместим с Delphi/Turbo Pascal) и GNU C/C++ (используйте стандарт языка).
A. Поиск
совпадений
Даны два текста. Найти все слова, которые встречаются
в обоих текстах сразу. Словом будем называть последовательность из прописных и
строчных латинских букв (максимальная
длина слов – 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 |
B.
Наименьшее число
Среди целых положительных чисел, в десятичной записи
которых присутствуют разряды только из заданного набора, найти наименьшее число,
удовлетворяющее двум условиям: во-первых, сумма разрядов этого числа равна N и, во-вторых, это число кратно M. Если числа, удовлетворяющего этим условиям, не
существует, вывести “
Ввод
В первой строке входного файла содержится
единственное число 1<=T<=50 –количество
тестов во входном файле. В первой строке каждого теста содержится число 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 x M, разбитое на клетки единичного
размера. В некоторых клетках этого поля расположены препятствия,
и на них нельзя попасть, а для каждой из остальных клеток известно количество
золота, которое в ней находится. У вас есть три робота, изначально они
находятся в левом верхнем углу поля, и все они должны добраться до правого
нижнего угла поля. За один ход каждый робот может сдвинуться на одну клетку
вправо или на одну клетку вниз, если он при этом не выйдет за пределы поля и не
попадет на клетку с препятствием. Находясь на определенной клетке, робот
забирает из нее все золото. Взятое золото в клетке не
восстанавливается, и другие роботы там уже ничего не получат. На одной клетке
могут находиться несколько роботов. Когда все роботы добираются в правый нижний
угол, подсчитывается суммарное количество золота, собранного ими. Требуется так
провести роботов по полю, чтобы максимизировать это суммарное количество
золота. Гарантируется, что роботов можно провести из левого верхнего в правый
нижний угол.
Ввод
В первой строке входного файла содержится два целых
числа N и M (2<=N, M<=50). Далее следуют N строк, в каждой из которых содержится M целых
чисел в диапазоне от -1 до 1000 (числа в строке отделяются пробелами). Число,
находящееся в i строке на j месте равно количеству золота в соответствующей
клетке поля или -1, если в этой клетке находится препятствие. В левом верхнем и
в правом нижнем углах поля всегда находится ноль единиц золота.
Вывод
Вывести единственную строку, содержащую максимальное
суммарное количество золота, которое могут собрать три робота.
|
Пример ввода 1 |
Пример вывода 1 |
|
3 3 0 5 7 3 8 6 9 -1 0 |
29 |
|
Пример ввода 2 |
Пример вывода 2 |
|
4 5 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 0 |
164 |