Тогда при выполнении команды S(3) мусорщик выполнит следующие действия:
1) переместится на 1 метр в направлении S
2) выполнит последовательно команды N(2), U(2), S(2), D(2), D(2), U(2), S(2), E(2).
Если далее проанализировать действия мусорщика при выполнении команд из пункта 2, получим, что в целом он совершит следующие перемещения:
SNNUUSNUSDDUSEDWEDDWEDUUSNUSDDUSEE
По заданной команде определите, какое общее количество перемещений на один метр совершит ловушка при выполнении заданной команды. В приведенном примере это количество равно 34.
Формат входных данных
Первые шесть строк входного файла задают правила для команд с направлением N, S, W, E, U и D соответственно. Каждая строка содержит не более 100 символов (и может быть пустой). Следующая строка содержит команду ловушки: сначала символ из множества {N, S, W, E, U, D}, затем пробел и параметр команды - целое положительное число, не превышающее 100.
Формат выходных данных
Выведите в выходной файл единственное число - количество перемещений, которое совершит ловушка. Гарантируется, что ответ не превышает 109.
Пример
trash.in
N
NUSDDUSE
UEWWD
U
WED
S 3
trash.out
34
Решение g6_1094:
Первая мысль, которая возникает при прочтении условия - использовать рекурсию. В принципе, мысль правильная, однако размерность задачи не очень большая и за счет сохранения уже вычисленных результатов можно сэкономить много времени.
Для каждого из направлений сохраним строку правила. Теперь напишем рекурсивную процедуру с двумя переменными на входе - направление (C) и параметр (I). Понятно, что для вычисления, A[C, I] достаточно просуммировать все значения (и прибавить 1), где Cnew - символы строки, соответствующей C и параметром I-1. Однако чтобы получилась экономия времени, следует запоминать уже посчитанные значения. Это можно реализовать с помощью массива от 1 до 100 для каждого из 6 символов. Сначала следует заполнить массив специальными символами, которые будут означать, что значение еще не посчитано (например, отрицательными числами). Каждый раз, когда будет посчитано новое значение - следует заносить его в массив. Для параметра 1 массив для всех направлений должен быть заполнен 1.
Здравствуйте, уважаемые посетители!
Этот сайт посвящен подробному разбору олимпиадных задач по информатике. На этом сайте разобраны задачи школьных, городских, областных, Всероссийских, международных, университетских, ACM олимпиад, а также задачи неопределенного происхождения и собственного сочинения. Исходные тексты к задачам не прилагаются. К некоторым задачам прилагаются тесты. Кроме того имеется отличная подборка книг и статей, великолепная коллекция ссылок и активно работающий форум. Удачи вам в решении олимпиадных задач!
Если вы на сайте впервые, то прочитайте документ "Первый раз на g6", он поможет вам разобраться, что к чему.
Все архивы находяться в формате RAR 3. Вы можете скачать WinRAR 3 с этого сайта или последнюю версию с сайта rarlab
Сайт построен на технологии JavaScript. Если ваш браузер не поддерживает ее, то вы можете воспользоваться html-списком задач и ссылками на другие разделы с этой страницы
В разделе "Разбор задач" вы можете найти большое количество задач с подробным разбором. Если у вас есть опыт написания программ на Паскале или Си, то по разбору задачи вам очень легко будет написать программу. Разобраны задачи, характерные для олимпиад, прорешав их вы сможете хорошо подготовиться к олимпиаде по информатике или наоборот, выбрать задачи для проведения своей олимпиады. Студенты могут найти в этом разделе разбор задач из лабораторных работ по информатике.
В разделе "Книги, статьи" лежат самые лучшие книги по олимпиадным задачам по программированию, учебники по Паскалю, а также мои статьи. Алгоритмы, используемые в решении той или иной задачи, кратко изложены в ее разборе. Если вам нужен какой-то алгоритм, то заходите на algolist.manual.ru - самую большую и хорошую коллекцию алгоритмов.
В разделе "Авторы" перечислены авторы разборов на этом сайте. Там же лежит моя автобиография
В разделе "Архив" содержится самое большое количество ссылок (в одной таблице!) на русскоязычные задачи и тесты к ним.
В разделе "Форум" находится объединенный форум AlgoList
В разделе "Ссылки" вы можете найти ссылки на хорошие ресурсы про олимпиадные задачи, Паскаль и алгоритмы.
Задачи отсортированы по номеру
Соритровать задачи по: номеру|номеру (обратно)|сложности|сложности (обратно)|теме|теме (обратно)
Номер задачи
|
Название
|
Сложность
|
Тема
|
Тесты
|
#1001
|
Проблема с A и B
|
очень простая
|
Структуры данных
|
Тесты
|
#1002
|
Трамвайные билеты
|
очень простая
|
Динамическое программирование
|
Тесты
|
#1003
|
Шифр Цезаря
|
очень простая
|
Строки
|
-
|
#1004
|
Равновеликие прямоугольники
|
простая
|
Арифметика
|
Тесты
|
#1005
|
MIME64
|
средней сложности
|
Строки
|
Тесты
|
#1006
|
Скобки
|
простая
|
Строки
|
-
|
#1007
|
Куль хацкеры
|
средней сложности
|
Строки
|
-
|
#1008
|
Редкое имя
|
средней сложности
|
Строки
|
Тесты
|
#1009
|
Уравнение
|
простая
|
Арифметика
|
-
|
#1010
|
Вирусы
|
простая
|
Структуры данных
|
-
|
#1011
|
Города
|
средней сложности
|
Переборные задачи
|
Тесты
|
#1012
|
КВН
|
простая
|
Арифметика
|
-
|
#1013
|
Коррекция кода
|
простая
|
Строки
|
-
|
#1014
|
Исправления
|
средней сложности
|
Строки
|
-
|
#1015
|
Степень
|
простая
|
Арифметика
|
-
|
#1016
|
Диски
|
сложная
|
Разное
|
Тесты
|
#1017
|
Демократия в опасности
|
простая
|
Арифметика
|
-
|
#1018
|
Пуговицы
|
простая
|
Арифметика
|
-
|
#1019
|
Банки
|
средней сложности
|
Арифметика
|
-
|
#1020
|
A to B
|
простая
|
Поиск
|
-
|
#1021
|
2n
|
средней сложности
|
Арифметика
|
Тесты
|
#1022
|
Ниточка
|
средней сложности
|
Геометрия
|
-
|
#1023
|
Массивище
|
средней сложности
|
Структуры данных
|
Тесты
|
#1024
|
Знакомые
|
средней сложности
|
Разное
|
-
|
#1025
|
Домино
|
сложная
|
Сортировки и последовательности
|
-
|
#1026
|
Монеты
|
сложная
|
Арифметика
|
-
|
#1027
|
Четные и нечетные члены последовательности
|
очень простая
|
Структуры данных
|
-
|
#1028
|
Считаем кораблики
|
средней сложности
|
Разное
|
-
|
#1029
|
Палиндромы
|
очень простая
|
Строки
|
-
|
#1030
|
Лошадью ходи!
|
средней сложности
|
Динамическое программирование
|
-
|
#1031
|
Левые повороты
|
средней сложности
|
Геометрия
|
-
|
#1032
|
Почти Крэг Туми
|
простая
|
Арифметика
|
-
|
#1033
|
Прицельное метание помидор
|
средней сложности
|
Арифметика
|
-
|
#1034
|
Программистика
|
сложная
|
Разное
|
Тесты
|
#1035
|
'Мы вас упакуем!'
|
очень простая
|
Арифметика
|
-
|
#1036
|
Хитрющая строка
|
сложная
|
Арифметика
|
-
|
#1037
|
Анаграммы
|
средней сложности
|
Строки
|
-
|
#1038
|
Система Защиты
|
очень сложная/особо интересная
|
Структуры данных
|
Тесты
|
#1039
|
Виза
|
простая
|
Арифметика
|
-
|
#1040
|
Робот-сапер
|
сложная
|
Задачи на графах
|
-
|
#1041
|
Квадраты
|
сложная
|
Структуры данных
|
-
|
#1042
|
Треугольник
|
средней сложности
|
Динамическое программирование
|
-
|
#1043
|
Принцип компании
|
средней сложности
|
Сортировки и последовательности
|
-
|
#1044
|
Уникальная строка
|
средней сложности
|
Строки
|
-
|
#1045
|
День рождения Иванова
|
сложная
|
Динамическое программирование
|
Тесты
|
#1046
|
Упаковка простых
|
сложная
|
Структуры данных
|
-
|
#1047
|
Бизнес-классики
|
очень сложная/особо интересная
|
Динамическое программирование
|
-
|
#1048
|
Оппозиция
|
сложная
|
Задачи на графах
|
-
|
#1049
|
Телеметрия
|
очень сложная/особо интересная
|
Разное
|
-
|
#1050
|
Лесной пожар
|
очень сложная/особо интересная
|
Геометрия
|
-
|
#1051
|
Замок
|
сложная
|
Задачи на графах
|
-
|
#1052
|
Олимпиада
|
очень сложная/особо интересная
|
Динамическое программирование
|
-
|
#1053
|
Конфуз
|
средней сложности
|
Структуры данных
|
Тесты
|
#1054
|
Автобусный диспетчер
|
очень сложная/особо интересная
|
Разное
|
Тесты
|
#1055
|
Кубики
|
очень сложная/особо интересная
|
Разное
|
Тесты
|
#1056
|
Многоугольники
|
сложная
|
Сортировки и последовательности
|
Тесты
|
#1057
|
Электронная почта
|
очень сложная/особо интересная
|
Динамическое программирование
|
Тесты
|
#1058
|
Автобус
|
очень сложная/особо интересная
|
Поиск
|
Тесты
|
#1059
|
Электронные часы
|
сложная
|
Разное
|
Тесты
|
#1060
|
Дождик
|
сложная
|
Геометрия
|
Тесты
|
#1061
|
K-ичные числа
|
средней сложности
|
Сортировки и последовательности
|
-
|
#1062
|
Черепаха
|
сложная
|
Динамическое программирование
|
Тесты
|
#1063
|
Михаил Густокашин против бюрократии
|
средней сложности
|
Задачи на графах
|
Тесты
|
#1064
|
Агенты
|
средней сложности
|
Задачи на графах
|
Тесты
|
#1065
|
Игра в слова
|
средней сложности
|
Строки
|
Тесты
|
#1066
|
Ездец
|
простая
|
Разное
|
Тесты
|
#1067
|
Метро
|
средней сложности
|
Задачи на графах
|
Тесты
|
#1068
|
Террористы
|
сложная
|
Задачи на графах
|
Тесты
|
#1069
|
Школы
|
сложная
|
Задачи на графах
|
Тесты
|
#1070
|
Блокада
|
сложная
|
Задачи на графах
|
Тесты
|
#1071
|
Форум
|
средней сложности
|
Задачи на графах
|
Тесты
|
#1072
|
Столица
|
средней сложности
|
Поиск
|
Тесты
|
#1073
|
Три города
|
очень сложная/особо интересная
|
Задачи на графах
|
Тесты
|
#1074
|
Простые гири
|
средней сложности
|
Арифметика
|
Тесты
|
#1075
|
Folding
|
сложная
|
Динамическое программирование
|
Тесты
|
#1076
|
Фишки
|
сложная
|
Структуры данных
|
Тесты
|
#1077
|
Квадраты 2
|
средней сложности
|
Динамическое программирование
|
Тесты
|
#1078
|
Калькулятор
|
простая
|
Переборные задачи
|
-
|
#1079
|
Предсказание
|
простая
|
Арифметика
|
-
|
#1080
|
Чайнворд
|
очень сложная/особо интересная
|
Динамическое программирование
|
Тесты
|
#1081
|
Таймер
|
простая
|
Строки
|
Тесты
|
#1082
|
Домой на электричках
|
средней сложности
|
Динамическое программирование
|
Тесты
|
#1083
|
Клад
|
очень простая
|
Арифметика
|
Тесты
|
#1084
|
Забавная игра
|
простая
|
Структуры данных
|
Тесты
|
#1085
|
Целые точки
|
средней сложности
|
Геометрия
|
Тесты
|
#1086
|
Степень 2
|
сложная
|
Арифметика
|
Тесты
|
#1087
|
Игра с фишками
|
средней сложности
|
Задачи на графах
|
Тесты
|
#1088
|
Раскопки
|
сложная
|
Строки
|
Тесты
|
#1089
|
Эксперимент
|
средней сложности
|
Динамическое программирование
|
-
|
#1090
|
Кубооктаэдр
|
средней сложности
|
Арифметика
|
-
|
#1091
|
Бусинки
|
средней сложности
|
Динамическое программирование
|
-
|
#1092
|
Пары слов
|
средней сложности
|
Переборные задачи
|
Тесты
|
#1093
|
Несвязные области
|
средней сложности
|
Разное
|
Тесты
|
#1094
|
Космический мусорщик
|
средней сложности
|
Динамическое программирование
|
Тесты
|
|