Никакой теории, только задачи. Некоторые из задач данного листка взяты из курса В.А.Матюхина: www.olympiads.ru/problems/8v-03/
1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1
Вам дан маршрут мудреца. Требуется определить, сколько килограммов золота он собрал. Если мудрец проходит через одну клетку более одного раза, то он собирает с нее золото только в первый проход.
Входные данные. Входные данные состоят из двух частей: плана комнаты и маршрута мудреца. Сначала записано количество строк в плане команаты N, затем - количество столбцов M. Затем записано N строк по M целых чисел в каждой – количество килограммов золота, которое лежит в данной клетке (число от 0 до 50). Далее записано число K – сколько клеток обошел мудрец. Затем идет K строк с координатами этих клеток (координаты клетки – это два числа: первое определяет номер строки, второе – номер столбца, верхняя левая клетка на плане имеет координаты (0, 0), правая нижняя - (N-1,M-1)).
Выведите количество килограммов золота, которое собрал мудрец.
Пример
Вход Выход 3 4 14 1 2 3 4 5 6 7 8 9 0 0 0 5 0 0 0 1 1 1 1 0 0 0
Входные данные.
Сначала задается план комнаты, как в предыдущей задаче.
Далее указано количество клеток K, которое обошел мудрец.
Мудрец начинает свое перемещение из клетки (0, 0) – левого верхнего угла
комнаты. Далее идет последовательность из K-1 буквы,
разделенных пробелами, задающими направление перемещения мудреца на каждом шаге.
Возможные направления: L
– влево, R
– вправо,
U
– вверх, D
– вниз. Программа должна вывести
количество килограммов золота, которое собрал мудрец или слово Error
,
если заданная последовательность некорректна (мудрец натыкается на стенку комнаты).
Пример
Вход Выход 3 3 45 1 2 3 4 5 6 7 8 9 9 D D R R U U L D Вход Выход 2 2 Error 1 1 1 1 4 R D R
На вход программа получает два числа N и M, не превосходящие 10. Программа должна вывести количество искомых маршрутов
Пример
Вход Выход 2 3 3
Входные данные. Первая строчка входных данных содержит натуральные числа N и M, не превосходящих 1000. Далее идет план замка в виде N строчек из M чисел в каждой. Одно число соответствует одной комнате: 1 означает, что в комнату можно попасть, 0 – что комната закрыта. Формат выходных данных
Программа должна напечатать количество маршрутов, ведущих узника к выходу
и проходящих через M+N-1 комнату, или слово Impossible
, если таких маршрутов не существует.
Входные данные подобраны таким образом, что искомое число маршрутов не превосходит 2.000.000.000.
Пример
Вход Выход 3 5 3 1 1 1 1 1 1 0 1 0 1 1 1 1 1 1 Вход Выход 3 5 Impossible 1 0 1 1 1 1 0 1 0 1 1 1 1 0 1
Пример
Вход Выход 3 4 9 1 1 2 1 2 2 1 1 2 1 2 1
В данном примере число 9 можно достигнуть, например, при помощи
следующей последовательности перемещений: D R D R R
.
D
,
означающую передвижение вниз и M-1 букву R
, означающую передвижение направо.
Если таких последовательностей несколько, необходимо вывести ровно одну (любую) из них.
Пример
Вход Выход 3 4 9 1 1 2 1 D R D R R 2 2 1 1 2 1 2 1