Задача F, приведенная ниже, была предложена участникам на дополнительный конкурс, за отдельный приз жюри. Участники могли решать задачу в течении двух недель после олимпиады. Однако, никто из школьников задачу F так и не решил.

Один крупный компьютерный концерн разработал новый язык программирования SIM и суперкомпьютер, который интерпретирует программы на этом языке. Суперкомпьютер может выполнять 100 триллионов операторов языка SIM в секунду, но выяснилось, что его процессор делает ... ошибки! Не чаще, чем 1 раз на 1000 команд он может либо перескочить на другую команду, либо испортить содержимое одной ячейки памяти. Разработчики стали горевать, что их изобретение никому не нужно, но ученые подсказали, что после небольшой модификации системы команд компьютер все же можно будет использовать. Они предложили ввести несколько новых команд и новый безопасный режим работы процессора, в котором процессор не делает ошибок, но работает очень медленно, со скоростью всего 1000 операторов в секунду. Новые операторы позволяют переключаться в безопасный режим и выходить из него. Также ввели регистр PSW, единичное значение которого разрешает выполнение некоторых "опасных операторов". После такой модификации сделалось возможным любую программу небольшого размера переделать в "надежную", т.е. устойчивую к ошибкам суперкомпьютера.

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

Ниже приводится список операторов первоначального языка SIM:

1. Оператор присваивания.

Формат: <Name> = <Value>, где Name - это имя переменной, Value - это либо имя переменной, либо целочисленная константа.

Действие: Оператор устанавливает значение переменной Name равной значению Value

Пример: Temperature = -1

2. Арифметический оператор

Формат: <Name>=<Value1><Op><Value2>

где Value1 и Value2 - как и в операторе присваивания, а Op - один из знаков арифметических операций +, -, *, / (деление нацело).

Действие: Оператор устанавливает значение переменной Namе равной значению выражения в правой части.

Пример: i = i + 1

3. Операторы ввода-вывода

Формат: READ <Name> и WRITE <Value>

Действие: Оператор READ читает из входного потока очередное число и записывает его в переменную Name. Оператор WRITE выводит в выходной поток либо значение указанной переменной, либо константу (параметр Value).

Пример: READ

4. Оператор безусловного перехода

Формат: GOTO <Label> ,

где Label - либо идентификатор метки, либо целочисленная константа Disp.

Действие: происходит безусловный переход к оператору с заданной меткой, либо к команде, отстоящей от данной на Disp операторов.

Примеры:

GOTO -1 (переход на пред. оператор)

GOTO ABC

5. Оператор условного перехода

Формат: IF <Value1><Op><Value2>GOTO<Label>

где Op - знак операции сравнения: "<", ">", "=", "<>", "<=", ">=", а Label - либо идентификатор метки, либо целочисленная константа Disp.

Действие: Если логическое выражение истинно, происходит переход (см. GOTO).

Пример: IF A=0 GOTO EndProgram

6. Оператор останова

Формат: HALT

Действие: Производит останов процессора. Программа заканчивает работу.

Пример: HALT

7. Метки

Метка описывается идентификатором метки, после которого ставится символ двоеточие ":".

Пример метки: ThisIsLabelExample:

Пример программы, которая вводит N и находит (не самым оптимальным способом) сумму чисел от 1 до N:

read N
i = 1
sum = 0
Loop: if i > N goto EndProgram
   sum = sum + i
   i = i + 1
goto Loop
EndProgram:
HALT

Как уже было сказано выше, в связи с тем, что Суперкомпьютер делал ошибки в язык были добавлены:

8. Безопасный режим работы

В этом режиме процессор работает очень медленно, но не делает ошибок. Теперь операторы READ, WRITE и HALT выполняются только в безопасном режиме! В обычном режиме выполнение этих команд не производит никаких действий.

9. Оператор SLOW

Формат: SLOW

Действие: Переводит процессор в безопасный (медленный режим). Если процессор уже находился в безопасном режиме, команда не производит никаких действий. Команда работает только в том случае, если значение переменной PSW=1. Если PSW ≠ 1 команда не производит никаких действий. Переменная PSW является обыкновенной переменной и также может быть ошибочно испорчена Суперкомпьютером.

10. Оператор FAST

Формат: FAST

Действие: Выводит процессор из безопасного режима. Если процессор работал в нормальном режиме, команда не производит никаких действий.

Начало работы программы

В начале работы значения всех переменных нулевые. Свою работу суперкомпьютер начинает в безопасном состоянии!

Ошибки Суперкомпьютера

Суперкомпьютер делает не более одной ошибки на 1000 команд в нормальном режиме. Это означает, выполнив в нормальном режиме 1000 команд (без переключений в безопасный режим) он ошибется не более одного раза. Если ошибка была непосредственно перед выполнением команды SLOW, то следующая ошибка может возникнуть прямо сразу после выполнения команды FAST, несмотря на то, что 1000 команд еще не прошло. Ошибка появляется в промежутке между выполнениями команд. Во время ошибки процессор либо портит значение какой-то переменной, либо сдвигает указатель текущей команды в какое-то случайное место (но в пределах программы).

Ошибок при исполнении не бывает. При делении на 0 получается 0. Программа считается зацикленной, т.е. после выполнения последней команды в программе процессор переходит на первую.

Примечание

Безопасный режим был введен не для того, чтобы в нем постоянно работать, а только для того, чтобы сделать возможным работу программы на ошибающемся компьютере!

Подсказка

Пользуйтесь тем, что до и после ошибки Суперкомпьютер выполнит по крайней мере 1000 команд без сбоев.

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

    
FAST
Begin:
PSW=1
SLOW
OUT=1
WRITE 555
IF PSW=0 GOTO Begin
IF OUT=0 GOTO Begin
HALT
GOTO Begin (можно не писать)

Задание

Напишите программу, которая переводит текст программы на первоначальном языке SIM (не расширенном спец. командами) в надежную. Исходная программа содержит не более 40 операторов. Результирующая надежная программа должна содержать не более 4000 операторов. Во время работы надежная программа должна выполнять не более, чем 200 + 200 * (Количество выполненных операторов READ и WRITE) команд в медленном (безопасном) режиме.

1. Операторы записываются в отдельных строках.
2. Метка может находиться либо в отдельной строке, либо стоять на одной строке с оператором.
3. Идентификатор переменной и метки состоит не более, чем из 20 символов.
4. Файл может содержать пустые строки и лишние пробелы, однако числа, операторы и идентификаторы разрываться не могут.
5. Идентификаторы не могут быть названы именами операторов.
6. Метка и переменная не могут иметь одно имя.
7. Идентификатор состоит из больших и маленьких латинских букв, цифр и символов: "_", "@", "#". Первый символ идентификатора не может быть цифрой.
8. Регистр букв и идентификаторах и ключевых словах значения не имеет.

Все тоже самое, только имена переменных и метки могут состоять из 25 символов.

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