Код программы: a := a xor B; b := a xor B; a := a xor B; Разобраться в ней не так уж сложно. Задача g6 1002: Трамвайные билеты - страница 8
.RU

Код программы: a := a xor B; b := a xor B; a := a xor B; Разобраться в ней не так уж сложно. Задача g6 1002: Трамвайные билеты - страница 8



Тогда при выполнении команды 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

Космический мусорщик

средней сложности

Динамическое программирование

Тесты







kolumbiya-strana-udivitelnaya-pervij-raz-moyo-znakomstvo-s-etoj-volshebnoj-stranoj-proizoshlo-v-fevrale-2007-goda-po-vozvrasheniyu-iz-kolumbii-ya-v-bukvalnom-smi-stranica-2.html
kolya-18-let-drug-tani-student-kulinarnogo-uchilisha-stranica-23.html
kolyada-stranica-6.html
koma-i-transi-inner-dreambody-work.html
komanda-forma-informatika.html
komanda-kluba-yunesko-zaranka-g-lyahovichi-brestskoj-oblasti-voprosi-zadaniya-3.html
  • learn.bystrickaya.ru/glava-16-lyubov-i-pulsaciya-pili-valerij-tihomirov-legenda-o-yakutse-ili-nezolotoj-telenok-valerij-tihomirov.html
  • esse.bystrickaya.ru/rabochaya-programma-dlya-studentov-i-ii-kursov-vseh-specialnostej-ochno-zaochnaya-forma-obucheniya.html
  • literature.bystrickaya.ru/besedi-o-zolotih-stihah-pifagora-stranica-7.html
  • lektsiya.bystrickaya.ru/praktikum-po-stilistike-i-literaturnomu-redaktirovaniyu-dlya-studentov-fakulteta-ekrannih-iskusstv-sankt-peterburg-stranica-2.html
  • turn.bystrickaya.ru/p-i-kachura-otskanirovano-by-uda-1997g-stranica-10.html
  • institute.bystrickaya.ru/gazovaya-hromatografiya-i-ee-primenenie-v-analiticheskoj-himii.html
  • thescience.bystrickaya.ru/iz-livijskih-sirta-i-ras-lanufa-rossiyan-budut-evakuirovat-paromom-iz-tripoli-samoletami-internet-resurs-wwwitar-tasscom-22022011.html
  • notebook.bystrickaya.ru/itogo-ekz-214-specifikaciya-na-postavku-izdanij-dlya-municipalnogo-uchrezhdeniya-kulturi.html
  • lecture.bystrickaya.ru/82sovmestnie-zasedaniya-komiteta-tpp-rf-po-razvitiyu-chastnogo-predprinimatelstva-malogo-i-srednego-biznesa-i-orgkomiteta-xi-vserossijskoj-konferencii-predstavitelej-malih-i-srednih-predpriyatij.html
  • shpargalka.bystrickaya.ru/vnebyudzhetnie-fondi.html
  • teacher.bystrickaya.ru/film-arthaus-linii-kino-bez-granic-komedijnij-neonuar.html
  • holiday.bystrickaya.ru/metodicheskoe-posobie-po-diplomnomu-proektirovaniyu-dlya-studentov-obuchayushihsya-po-specialnosti-061000-080507-stranica-2.html
  • klass.bystrickaya.ru/42filosofiya-shopengauera-osobennosti-i-osnovnie-ponyatiya-rassmatrivaet-mir-s-tochki-zreniya-ego-predelnih-poslednih-osnovanij.html
  • obrazovanie.bystrickaya.ru/posleslovie-galina-shekina-ff-ili-fenomen-faustova-literaturnaya-artel-stupeni.html
  • report.bystrickaya.ru/hronicheskie-zabolevaniya-zhelchnogo-puzirya-i-zhelchnih-putej-klassifikaciya.html
  • lesson.bystrickaya.ru/russkaya-sistema-mer.html
  • textbook.bystrickaya.ru/izmenenie-investicionnoj-politiki-kak-vnutri-gosudarstva-tak-i-dlya-vneshnih-investorov.html
  • turn.bystrickaya.ru/polozhenie-o-provedenii-gorodskogo-konkursa-detskih-teatralnih-kollektivov-v-ramkah-xviii-gorodskogo-konkursa-festivalya-hudozhestvennogo-tvorchestva-uspeh-2012.html
  • upbringing.bystrickaya.ru/meropriyatiya-po-obespecheniyu-dostupnim-zhilem-molodih-semej-i-molodih-specialistov-na-seles-izmeneniyami-ot-17-sentyabrya-2007-g-5-marta-2008g-31-yanvarya-2009-g.html
  • znaniya.bystrickaya.ru/rasskazat-ob-istorii-razvitiya-lokalnih-i-globalnih-setej-stranica-2.html
  • klass.bystrickaya.ru/45-byudzhetnij-sektor-programma-socialno-ekonomicheskogo-razvitiya-municipalnogo-obrazovaniya-zalarinskij-rajon.html
  • zanyatie.bystrickaya.ru/osnovi-metodologii-fiziki-v-kurse-srednej-shkoli.html
  • laboratornaya.bystrickaya.ru/rabochee-vremya-i-vremya-otdiha-stranica-55.html
  • ekzamen.bystrickaya.ru/sistema-vidi-i-naznacheniya-tamozhennih-platezhej.html
  • college.bystrickaya.ru/27-trebovaniya-k-tehnicheskomu-obespecheniyu-kursovoj-proekt-po-kursu-proektirovanie-avtomatizirovannih-sistem.html
  • studies.bystrickaya.ru/administrativnoe-stroenie-subektov-rossijskoj-federacii-chast-6.html
  • paragraf.bystrickaya.ru/zakon-o-socialnoj-zashite-invalidov-v-rossijskoj-federacii-stranica-8.html
  • otsenki.bystrickaya.ru/sekciya-36-programma-xxx-iv-oj-mezhregionalnoj-studencheskoj-nauchnoj-konferencii-molodezh-i-kooperaciya-2010.html
  • uchitel.bystrickaya.ru/razrabotka-gibkogo-avtomatizirovannogo-proizvodstva-po-vipusku-fazovogo-komparatora.html
  • ucheba.bystrickaya.ru/programma-disciplini-landshaftovedenie-opd-f-07-celi-i-zadachi-disciplini.html
  • literature.bystrickaya.ru/chast-1-pedagogicheskij-process-yavlyaetsya-bogochelovecheskim-sinergejnim-sostoyashim-iz-bozhestvennoj-i-chelovecheskoj-sostavlyayushih.html
  • zanyatie.bystrickaya.ru/moskovskie-vokzali.html
  • textbook.bystrickaya.ru/investicionnij-pasport-municipalnogo-obrazovaniya-gorod-rajchihinsk.html
  • desk.bystrickaya.ru/plani-seminarskih-zanyatij-po-discipline-ekonomika-zarubezhnih-stran.html
  • composition.bystrickaya.ru/pesa-dlya-provincialnogo-teatra-stranica-2.html
  • © bystrickaya.ru
    Мобильный рефератник - для мобильных людей.