Роботландский Университет 02/03
31 Азы программирования
Задачи турнира Корректора
-------------------------------

З А Д А Ч И
- - - - - -
март, 2003 (C) А.В.Рудь,
В.П.Семенко, А.Букирь
предисловие частично заимствовано из
сборника задач турнира Корректора,
2001 (С) А.А.Дуванов
                                На золотом крыльце сидели
                                царь, царевич, король,
                                королевич, сапожник, портной...
                                Кто ты будешь такой?
                                (детская считалочка)

  В конкурсе  Корректора  2002/2003 года предлагается 12 задач.
К проверке принимаются любые 8 по выбору команды. Рекомендуется,
в идеале, порешать все задачи, а затем выбрать те, в которых,
по мнению команды, найдены самые оптимальные решения.

  На первый  взгляд,  все  задачи,  кроме,  возможно, одной или
двух, могут  показаться совсем простыми, т.к. алгоритмы кажутся
прозрачными. Однако решение решению  рознь.  Постарайтесь найти
самые рациональные алгоритмы, с минимальным количеством  команд
исполнителя. Во многих задачах  возможны  "однопроходные" реше-
ния, которые, надеюсь, доставят вам настоящее удовольствие.

Для всех задач действуют следующие соглашения:

1. Будем считать, что лента Корректора достаточно длинная, и краевые
эффекты в решениях можно не учитывать (известно, что длина ленты при
необходимости настраивается в файле kor.ini). По этой же причине
не предполагается использовать в решениях замкнутость ленты,
обход вокруг ленты будет оцениваться как ОЧЕНЬ НЕРАЦИОНАЛЬНЫЙ прием.

2. Для "вычислений" рекомендуется  использовать ящик исполни-
теля, а в качестве  "чисел"  -- алфавитные символы, считая, что
символ изображает  число,  равное  порядковому номеру символа в
алфавите Корректора:  символ  "0"  соответствует  числу ноль, а
последний символ "@" - числу 69.  При  этом можно считать, что 
данные  на ленте устроены так, что при вычислениях  не возникает 
аварийных ситуаций: результат  или промежуточные значения не 
превышают по величине порядковый  номер  последнего алфавитного 
символа и не отрицательны.

  3. Символ "ПУСТО" (не путать с символом "ПРОБЕЛ") не соответ-
ствует никакому числу, кроме, разве что,  "палочного" нуля. Тем
не менее, символом  алфавита он является и может быть использо-
ван в исходных данных, если это не противоречит условию задачи.
Этот символ с двух сторон ограничивает данные на  ленте и может
означать отсутствие данных, "пустую" запись.

При оценке решений будет учитываться:

-- наличие описания алгоритма и комментария программы
-- наличие и правильность диаграммы переходов в задаче с,
   ее соответствие коду программы
-- правильность алгоритма и программы (на всех допустимых данных)
-- эффективность алгоритма и эффективность программы
   очень желательно минимизировать количество просмотров исходных данных,
   постарайтесь найти красивые однопроходные алгоритмы!
-- структурирование кода программы

В целях повышения удобочитаемости кода (что особенно важно при
перекрестных проверках) настоятельно рекомендуется:

-- Главную процедуру (с которой код начинает свою работу) именовать
   "Вход".
-- Имена всех процедур записывать в нижнем регистре, кроме первой
   буквы (не "ПРОХОД1", а "Проход1").
-- Использовать для процедур осмысленные имена, которые как-то
   документируют их работу ("фас!" -- это смешно, но "Поиск_цифры"
   -- гораздо лучше).
-- В кодах использовать краткие, но содержательные комментарии.
   Комментарии должны пояснять логику, а не "физику" работы кода.
   Такой комментарий плох (пуст):

   ВПРАВО // сдвигаем окошко вправо

   Этот лучше:

   ВПРАВО // к следующему символу записи

   Для важных процедур записывайте комментарий в виде:

   // <назначение процедуры>
   // Вход:  <где окно, что в ящике и на ленте>
   // Выход: <где окно, что в ящике и на ленте>

   Уверен, что эти рекомендации помогут, в первую очередь, самим
   разработчикам, поэтому не откладывайте комментирование
   на последние полчаса перед посылкой работы на конкурс (чтобы
   удовлетворить "причудам" куратора).

   Рекомендуется сначала писать комментарии, а только потом развертывать
   их в код. Практика программирования, когда код получается из комментариев,
   является обычной для серьезных программистов.

Успехов вам в конкурсе и приятных минут рождения красивого решения!

Задача 1 "От и до" (3 балла)
-----------------------------
  На ленте в соседних ячейках два символа из алфавита Корректо-
ра. Окошко на правом из них. Требуется плотно записать на ленту
символы, порядковые  номера  которых  меньше порядкового номера
правого символа и одновременно больше порядкового номера левого
символа. Если таких символов нет, написать на ленте слово "нет".
Исходные символы удалить с ленты.

Пример работы программы:

Начальное состояние            После работы программы
┬─┬─┬─┬─┬─╦═╦─┬─┬─┬─┬─┬        ┬─┬─┬─┬─┬─┬─╦═╦─┬─┬─┬─┬
│░│░│░│░│8║г║░│░│░│░│░│  ─>    │░│░│░│9│а│б║в║░│░│░│░│
┴─┴─┴─┴─┴─╩═╩─┴─┴─┴─┴─┴        ┴─┴─┴─┴─┴─┴─╩═╩─┴─┴─┴─┴

Задача 2 "Сколько нулей, сколько единиц?" (3 балла)
---------------------------------------------------
  На ленте запись, состоящая  только  из нулей и единиц. Окошко
Корректора слева от записи. Написать на ленте вплотную два сим-
вола, изображающие  количество  нулей  и единиц соответственно.
Исходную запись с ленты удалить.

Пример работы программы:

Начальное состояние            После работы программы
┬─┬─╦═╦─┬─┬─┬─┬─┬─┬─┬─┬        ┬─┬─┬─┬─┬─┬─┬─╦═╦─┬─┬─┬
│░│░║░║1│1│0│1│0│░│░│░│  ─>    │░│░│░│░│░│░│2║3║░│░│░│
┴─┴─╩═╩─┴─┴─┴─┴─┴─┴─┴─┴        ┴─┴─┴─┴─┴─┴─┴─╩═╩─┴─┴─┴

Задача 3 "Счастливый билет" (4 балла)
-------------------------------------
  На ленте плотно  записаны  шесть десятичных цифр- номер трол-
лейбусного билета. Окошко Корректора расположено перед записью.
Билет считается счастливым,  если  сумма первых трех цифр равна
сумме последних трех.  Требуется  написать на ленте слово "да",
если билет счастливый или слово "нет" в противоположном случае.
Исходную запись сохранять не нужно.

Пример работы программы:

Начальное состояние            После работы программы
┬─╦═╦─┬─┬─┬─┬─┬─┬─┬─┬─┬        ┬─┬─┬─┬─┬─╦═╦─┬─┬─┬─┬─┬
│░║░║2│5│0│4│1│2│░│░│░│        │░│░│░│░│д║а║░│░│░│░│░│
┴─╩═╩─┴─┴─┴─┴─┴─┴─┴─┴─┴        ┴─┴─┴─┴─┴─╩═╩─┴─┴─┴─┴─┴

Задача 4 "Середина" (5 баллов)
-------------------------------------
  На ленте  справа от окошка Корректора начинается произвольная
непустая запись. Найдите ее середину: если количество симво-
лов в записи нечетное, установите окошко Корректора на средний
символ, в  противном случае вставьте в середину записи символ
ПУСТО и установите на него окошко Корректора.

Примеры работы программы:

Начальное состояние            После работы программы
┬─╦═╦─┬─┬─┬─┬─┬─┬─┬─┬─┬        ┬─┬─┬─┬─┬─╦═╦─┬─┬─┬─┬─┬
│░║░║з│а│п│и│с│ь│░│░│░│        │░│░│з│а│п║░║и│с│ь│░│░│
┴─╩═╩─┴─┴─┴─┴─┴─┴─┴─┴─┴        ┴─┴─┴─┴─┴─╩═╩─┴─┴─┴─┴─┴

Начальное состояние            После работы программы
┬─╦═╦─┬─┬─┬─┬─┬─┬─┬─┬─┬        ┬─┬─┬─┬─┬─╦═╦─┬─┬─┬─┬─┬
│░║░║с│л│о│в│о│░│░│░│░│        │░│░│░│с│л║о║в│о│░│░│░│
┴─╩═╩─┴─┴─┴─┴─┴─┴─┴─┴─┴        ┴─┴─┴─┴─┴─╩═╩─┴─┴─┴─┴─┴

Задача 5 "Смешанное сложение" (5 баллов)
----------------------------------------
На ленте последовательно записаны палочное число, знак "+" и символ,
обозначающий число, равное его порядковому номеру. Окошко Корректора
расположено перед записью. Требуется получить результат сложения
в виде десятичного числа. Исходную запись удалить с ленты.

Пример работы программы:

Начальное состояние            После работы программы
┬─╦═╦─┬─┬─┬─┬─┬─┬─┬─┬─┬        ┬─┬─┬─┬─┬─╦═╦─┬─┬─┬─┬─┬
│░║░║|│|│|│+│б│░│░│░│░│        │░│░│░│░│1║4║░│░│░│░│░│
┴─╩═╩─┴─┴─┴─┴─┴─┴─┴─┴─┴        ┴─┴─┴─┴─┴─╩═╩─┴─┴─┴─┴─┴

Задача 6 "Горка из чисел" (5 баллов)
------------------------------------
На ленте единственный символ (не ПУСТО), видимый в окошко.
Требуется последовательно записать на ленте:
  1)все символы, порядковый номер которых меньше номера исход-
ного символа в порядке возрастания
  2)сам исходный символ
  3)тот же ряд 1) в порядке  убывания.
После  работы  программы окошко установить на исходный символ.

Пример работы программы:

Начальное состояние            После работы программы
┬─┬─┬─┬─┬─╦═╦─┬─┬─┬─┬─┬        ┬─┬─┬─┬─┬─╦═╦─┬─┬─┬─┬─┬
│░│░│░│░│░║4║░│░│░│░│░│        │░│0│1│2│3║4║3│2│1│0│░│
┴─┴─┴─┴─┴─╩═╩─┴─┴─┴─┴─┴        ┴─┴─┴─┴─┴─╩═╩─┴─┴─┴─┴─┴

Задача 7 "Жребий на пальцах" (6 баллов)
---------------------------------------
  На ленте два различных символа, записанные рядом. Они изобра-
жают количество  пальцев на руке (от  0 до 5),  которое наугад
"выбросили" двое  игроков.  Окошко Корректора на левом символе.
Начиная с  игрока,  который  "выбросил" меньше пальцев (назовем
его первым), ведется  счет от 1 до суммы "выброшенных" пальцев.
Т.е. число 2  соответствует второму игроку, число "3" первому и
т.д. Требуется установить окошко Корректора на символе, изобра-
жающем количество пальцев игрока, на котором закончится счет.
Все символы, кроме двух исходных, с ленты удалить.

Пример работы программы:

Начально  состояние            После работы программы
┬─┬─┬─┬─╦═╦─┬─┬─┬─┬─┬─┬        ┬─┬─┬─┬─┬─╦═╦─┬─┬─┬─┬─┬
│░│░│░│░║3║5│░│░│░│░│░│  ─>    │░│░│░│░│3║5║░│░│░│░│░│
┴─┴─┴─┴─╩═╩─┴─┴─┴─┴─┴─┴        ┴─┴─┴─┴─┴─╩═╩─┴─┴─┴─┴─┴

Задача 8 "Кому выходить?" (7 баллов)
-------------------------------------
  В  круговой  считалочке из m слов участвуют  n  человек.  Все
участники  пронумерованы:  первый, второй,  ...n-ый.  На  каком
участнике закончится счет,  если начинать с первого? На ленте в
соседних ячейках  два символа: левый обозначает количество счи-
тающихся (n), правый- количество слов в считалочке (m). В окош-
ко Корректора  виден  левый  символ.  После  работы программы в
окошке Корректора  должен  быть  символ, соответствующий номеру
участника, на котором закончился счет.

Пример работы программы:

Начальное состояние            После работы программы
┬─┬─┬─┬─╦═╦─┬─┬─┬─┬─┬─┬        ┬─┬─┬─┬─┬─╦═╦─┬─┬─┬─┬─┬
│░│░│░│░║5║8│░│░│░│░│░│  ─>    │░│░│░│░│░║3║░│░│░│░│░│
┴─┴─┴─┴─╩═╩─┴─┴─┴─┴─┴─┴        ┴─┴─┴─┴─┴─╩═╩─┴─┴─┴─┴─┴

Задача 9 "Кто останется?" (10 баллов)
-------------------------------------
  В  круговой  считалочке из m слов участвуют  n  человек.  Все
участники пронумерованы: первый, второй, ...n-ый. Считать начи-
нают с первого. Участник, на котором  закончился счет, выбывает
из круга. Оставшиеся участники повторяют считалочку, причем на-
чинают считать с участника,  следующего  за выбывшим по кругу в
направлении счета. Если повторить считалочку n-1 раз, останется
один участник. Требуется найти его номер.

  На  ленте  два символа, записанных через одну пустую  ячейку.
Левый обозначает количество считающихся (n), правый- количество
слов в считалочке  (m). В окошко Корректора виден левый символ.
После работы программы в окошке Корректора  должен быть символ,
соответствующий номеру участника, оставшегося в круге.

Пример работы программы:

Начальное состояние            После работы программы
┬─┬─┬─┬─╦═╦─┬─┬─┬─┬─┬─┬        ┬─┬─┬─┬─┬─╦═╦─┬─┬─┬─┬─┬
│░│░│░│░║5║░│8│░│░│░│░│  ─>    │░│░│░│░│░║1║░│░│░│░│░│
┴─┴─┴─┴─╩═╩─┴─┴─┴─┴─┴─┴        ┴─┴─┴─┴─┴─╩═╩─┴─┴─┴─┴─┴

Задача а "Умножение палочек" (8 баллов)
---------------------------------------
Автор задачи Букирь Артем, г.Тольятти

  На ленте записаны два палочных числа,  разделенных знаком ум-
ножения- звездочкой.  Звездочка видна в окошке Корректора. Тре-
буется  получить  на ленте результат умножения в виде  обычного
десятичного числа и в виде палочного  числа, разделенных знаком
равенства. Исходную запись на ленте можно не сохранять.

Пример работы программы:

Начальное состояние            После работы программы
┬─┬─┬─┬─┬─┬─╦═╦─┬─┬─┬─┬        ┬─╦═╦─┬─┬─┬─┬─┬─┬─┬─┬─┬
│░│░│░│|│|│|║*║|│|│░│░│  ─>    │░║6║=│|│|│|│|│|│|│░│░│
┴─┴─┴─┴─┴─┴─╩═╩─┴─┴─┴─┴        ┴─╩═╩─┴─┴─┴─┴─┴─┴─┴─┴─┴

Задача b "Простые числа" (12 баллов)
-------------------------------------
Автор задачи В.П.Семенко, г.Рубцовск

В окне Корректора виден символ, изображающий натуральное чис-
ло. Требуется написать на ленте все простые числа, меньшие дан-
ного числа, в виде плотного ряда  символов алфавита Корректора.
Исходное число с ленты не удалять, после работы программы уста-
новить окно Корректора на нем.

Пример работы программы:

Начальное состояние            После работы программы
┬─┬─┬─┬─┬─╦═╦─┬─┬─┬─┬─┬        ┬─┬─┬─┬─┬─┬─┬─╦═╦─┬─┬─┬
│░│░│░│░│░║в║░│░│░│░│░│  ─>    │░│1│2│3│5│7│б║в║░│░│░│
┴─┴─┴─┴─┴─╩═╩─┴─┴─┴─┴─┴        ┴─┴─┴─┴─┴─┴─┴─╩═╩─┴─┴─┴


Задача с (8 баллов) Хохотунчики.
-------------------------------------
  В языке хохотунчиков все  слова  строятся только из трех сло-
гов: "ха", "хи"  и "хо". Слово может содержать любое количество
слогов, например: "хаха", "хихихо", "хи". В записи любого хохо-
тунского предложения принято разделять  слова  пробелами. Между
словами могут быть запятые, которые пишутся слитно с левым сло-
вом. После запятой обязателен пробел. Предложение должно закан-
чиваться восклицательным  знаком, который пишется слитно с пос-
ледним словом.

Посмотрите, как коротко и точно выглядит рекурсивное определение
хохотунского предложения на языке Бэкуса-Наура:

<предложение>:=<слово>!|<слово>_<предложение>|<слово>,_<предложение>
<слово>:=<слог>|<слог><слово>
<слог>:=х<гласная>
<гласная>:=а|и|о

  Здесь в  угловые  скобки заключены определяемые понятия, знак
:= означает "по определению есть", знак | обозначает "или"

1) Составьте диаграмму рекурсивных переходов будущей програм-
мы (до 4 баллов)

2) Запрограммируйте лексический анализатор, проверяющий, является ли
   запись на ленте хохотунским предложением (до 4 баллов).
   Имена процедур должны совпадать с названиями состояний диаграммы. 

В начальный момент окно расположено слева перед записью:

┬─┬─╦═╦─┬─┬─┬─┬─┬─┬─┬─┬
│░│░║░║з│а│п│и│с│ь│░│░│
┴─┴─╩═╩─┴─┴─┴─┴─┴─┴─┴─┴

Если проверяемая запись -- выражение, написать следом за ней "ок":

┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─╦═╦─┬
│░│х│и│,│ │х│а│х│а│!│░║о║к│
┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─╩═╩─┴

Если запись -- не выражение, записать следом за ней сообщение "ош" и
поставить окно на первый неверный символ:

┬─┬─┬─┬─┬─╦═╦─┬─┬─┬─┬─┬─┬─┬
│░│░│░│х│о║-║х│о│!│░│о│ш│░│
┴─┴─┴─┴─┴─╩═╩─┴─┴─┴─┴─┴─┴─┴

