Задача A. Лабиринт
Условие
Лабиринт задан как двумерный массив символов '.' и '#', означающих пустое пространство и стену соответственно.
В любой не занятой стеной клетке может находиться Искатель. Ему разрешено перемещаться по клеткам лабиринта в четырех направлениях: вверх,
вниз, влево и вправо. Покидать лабиринт через внешнюю границу запрещено, ибо за его пределами находится сплошная стена. Требуется написать
программу, которая по заданному лабиринту определяет существует ли путь от входа к выходу.
Формат входного файла
Первая строка входного файла содержит числа
N и
M - количества строк и столбцов в описании лабиринта соответственно.
В следующих
N строках содержатся по
M символов из множества '.' (пустое пространство) , '#' (стена), 'S' (вход), 'F' (выход).
В описании лабиринта присутствует ровно один символ 'S' и ровно один 'F'.
Формат выходного файла
Выведите в выходной файл текстовую строку 'YES', если существует путь от входа к выходу и 'NO' в противном случае.
Ограничения
1 ≤ N,M ≤ 1000
Примеры тестов
| № |
Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|
| 1 |
3 3
S#.
.#F
...
|
YES
|
| 2 |
3 3
S#.
.#F
#..
|
NO
|
Задача B. Выражение
Условие
Пусть задана конечная последовательность целых чисел. Если между всеми соседними числами поставить по одному знаку арифметической операции сложения,
вычитания или умножения, получится арифметическое выражение, значение которого можно посчитать. При этом, согласно общепринятым правилам, сначала выполняются
операции умножения, как более приоритетные. И только затем - сложения и вычитания. Напишите программу, которая по заданному набору чисел найдет такую
расстановку знаков арифметических операций, что соответствующее выражение окажется равным нулю.
Формат входного файла
Первая строка входного файла содержит число
N — количество элементов последовательности.
Вторая строка содержит
N целых чисел
Ai — элементы последовательности.
Формат выходного файла
Выведите в выходной файл текстовую строку, состоящую из знаков арифметических операций, не разделяя их пробелами. При этом '+' должен соответствовать
сложению, '-' - вычитанию, '*' - умножению. Если искомой последовательности не существует, выведите 'No solution'. Если существует несколько решений,
выведите любое из них.
Ограничения
2 ≤ N ≤ 8, −10 ≤ Ai ≤ 10
Примеры тестов
| № |
Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|
| 1 |
3
5 10 15
|
+-
|
| 2 |
4
4 5 15 5
|
*--
|
| 3 |
4
4 5 16 5
|
No solution
|
Задача C. Обход доски конем
Условие
Напишите программу, которая по заданным размерам прямоугольного участка шахматной доски определяет такую последовательность ходов конем,
что каждая клетка участка оказывается посещенной ровно один раз. При этом начинать обход можно с любой клетки. Конь ходит согласно обычным шахматным
правилам, смещаясь на две клетки по одному из направлений и на одну по другому. По горизонтали клетки нумеруются заглавными буквами латинского алфавита,
по вертикали — цифрами.
Формат входного файла
Первая строка входного файла содержит целые положительные числа
N и
M — ширина и высота участка шахматной доски соответственно.
Формат выходного файла
Выведите в выходной файл текстовую строку — последовательность клеток в том порядке в котором их должен пройти конь. Каждая клетка должна присутствовать
в ответе ровно один раз. Каждый элемент, задающий позицию должен состоять из буквы латинского алфавита и цифры. Соседние элементы разделяются пробелами.
Если решения не существует, выведите "No solution".
Ограничения
1 ≤ N * M ≤ 30
Примеры тестов
| № |
Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|
| 1 |
1 1
|
A1
|
| 2 |
1 2
|
No solution
|
| 3 |
3 4
|
A1 B3 C1 A2 B4 C2 A3 B1 C3 A4 B2 C4
|
