Задача по информатике

Что такое средняя метка? Это метка, равноотстоящая от концов массива. Отсюда идея алгоритма: последовательно продвигаться от концов массива до встречи в середине. Раз у нас массив меток, то продвигать будем отсутствие метки, "дырку". Первая прикидка алгоритма:

А1. Стереть метки в крайних ячейках массива (инициализация) .
А2. Передвинуть левую дырку на позицию вправо, правую - на позицию влево.
А3. Если дырки совпали - середина найдена, иначе к шагу А2.

Условимся, что в начале каретка стоит над самой левой меткой массива. Тогда шаг А1 можно условно записать так:

Ш1. Стереть метку.
Ш2. Вправо пока метка.
Ш3. Влево
Ш4. Стереть метку.

Но чтобы стереть две метки, надо как минимум иметь эти две метки. Что же произойдёт, если метка всего одна? На Ш4 мы попытаемся стереть метку в ячейке, обработанной на Ш1. Но в этом случае единственная метка уже стёрта и больше ничего делать не надо, можно останавливаться. Итак, Ш4 получается таким:

Ш4. Если не метка, то Стоп, иначе стереть метку.

После Ш4 каретка стоит над правой дыркой. Шаг А2 тогда будет такой:

Ш5. Влево пока метка.
Ш6. Поставить метку.
Ш7. Вправо.
Ш8. Стереть метку.
Ш9. Вправо пока метка.
Ш10. Поставить метку.
Ш11. Влево.
Ш12. Стереть метку.

Дырки сдвинулись навстречу друг другу, и каретка снова стоит над правой дыркой. Осталось определить, когда же надо заканчивать. Перед самой встречей состояние ленты такое:

...ххх. х. ххх.. .

Выполнив Ш5-Ш11, получим такое состояние:

...хххх. хххх.. .

То есть на Ш12 мы попытаемся стереть метку в пустой ячейке, очищенной на Ш8. Это означает, что наши дырки встретились и мы стоим на середине. Можно останавливаться. Значит, Ш12 будет таким:

Ш12. Если не метка, то Стоп, иначе стереть метку.

Осталось начать новый цикл:

Ш13. Перейти к Ш5.

Заметим теперь, что Ш3-Ш4 и Ш11-Ш12 полность совпадают, и в обоих случаях после этих команд выполняется Ш5. Значит, после Ш10 можно просто перейти к Ш3. В итоге получаем:

Ш1. Стереть метку.
Ш2. Вправо пока метка.
Ш3. Влево
Ш4. Если не метка, то Стоп, иначе стереть метку.
Ш5. Влево пока метка.
Ш6. Поставить метку.
Ш7. Вправо.
Ш8. Стереть метку.
Ш9. Вправо пока метка.
Ш10. Поставить метку.
Ш13. Перейти к Ш3.

Ну и сама программа:

1. СТЕРЕТЬ
2. ВПРАВО
3. ? 4 2
4. ВЛЕВО
5. ? 6 7
6. СТОП
7. СТЕРЕТЬ
8. ВЛЕВО
9. ? 10 8
10. ПОСТАВИТЬ
11. ВПРАВО
12. СТЕРЕТЬ
13. ВПРАВО
14. ? 15 13
15. ПОСТАВИТЬ 4