Имя файла исходных данных: INPUT.TXT
Имя выходного файла: OUTPUT.TXT

Задано уравненение вида A+B=C, где A, B и C - неотрицательные целые числа, в десятичной записи которых некоторые цифры заменены знаками вопроса "?". Например, ?65+443=2?4. Требуется подставить вместо знаков вопроса цифры, так чтобы равенство стало верным, либо определить, что это невозможно. Найти только одно из возможных решений.

Исходные данные

Файл исходных данных содержит одну или несколько строк, в каждой из которых записано одно уравнение в виде A+B=C. Уравнение состоит не более, чем из 80 символов. Файл исходных данных не содержит пробелов и пустых строк.

Выходные данные

Для каждого уравнения вывести в выходной файл на отдельной строке решение - верное равенство, полученное из исходного уравнения заменой знаков вопроса цифрами, либо сообщение "решения не существует".

Пример файла исходных данных INPUT.TXT:

2+2=5
?+?=??
??2?4+9?=355

Выходной файл OUTPUT.TXT для приведенного примера:

решения не существует
9+5=14
00264+91=355

Имя файла исходных данных: INPUT.TXT
Имя выходного файла: OUTPUT.TXT

рис.1

На одной из клеток шахматной доски (см.рис.1) стоит кубик. На гранях кубика написаны неотрицательные целые числа, не превосходящие 1000. Кубик можно перемещать на смежную клетку, перекатывая его через соответствующее ребро в основании. При движении считается сумма чисел, попавших в основание кубика (каждое число считается столько раз, сколько раз кубик оказывался на данном основании). Требуется найти такой путь движения кубика от начальной до заданной конечной клетки, при котором сумма чисел будет минимальной. Числа, стоящие в основании кубика в начальной и конечной позициях тоже входят в сумму. Начальная и конечная позиции различаются.

Исходные данные

Первое строка в файле содержит количество наборов исходных данных. Каждый набор записывается на отдельной строке и задается следующим образом. В начале записываются координаты начальной и конечной позиций кубика. Координата состоит из прописной буквы и следующей за ней без пробела цифры (см. пример и рис.1). Далее следуют 6 чисел, записанных на гранях кубика. Первым идет число, записанное на передней грани, далее - на задней, верхней, правой, нижней и левой гранях соответстсвенно. Исходный файл не содержит пустых строк.

Выходные данные

Для каждого набора исходных данных вывести в выходной файл на отдельной строке минимальную сумму и сам путь. Путь задается последовательным перечислением координат полей, по которым движется кубик. Путь должен начинаться начальной позицией и заканчиваться конечной позицией кубика. Координаты задаются также, как во входных данных.

Пример файла исходных INPUT.TXT:

2
a1 b2 1 1 1 1 1 1
e2 e3 0 8 1 2 1 1

Выходной файл OUTPUT.TXT для приведенного примера:

3 a1 b1 b2
5 e2 d2 d1 e1 e2 e3

Имя файла исходных данных: INPUT.TXT
Имя выходного файла: OUTPUT.TXT

В океане, в точке с координатами (x,y) потерпел крушение корабль. Недалеко от места крушения находится остров, который имеет форму N-угольника (многоугольник не обязательно выпуклый; 3< N< 50). Спасшиеся после кораблекрушения пассажиры оказались в шлюпке, которая может двигаться в любом направлении со скоростью, не превосходящей v (v> 0; шлюпка может менять направление и величину скорости во время движения; скорость v задана относительно воды). В окенане имеется постоянное течение, вектор скорости которого (vtx, vty). Требуется найти минимальное время, за которое шлюпка доберется до острова, либо определить, что из-за сильного течения шлюпка до острова доплыть не сможет.

Исходные данные

Первое число в файле задает количество наборов исходных данных. Набор содержит координаты места крушения (x,y); количество вершин острова N; координаты вершин острова, заданные в порядке обхода острова по часовой стрелке: x1,y1,x2,y2, ... , xN,yN; максимальную скорость спасательной шлюпки v; вектор скорости течения (vty, vtx). Все числа в исходном файле разделяются пробелами и (или) символами перевода строки. Координаты и скорости задаются вещественными числами.

Выходные данные

Для каждого набора исходных данных вывести в выходной файл на отдельной строке минимальное время, за которое спасательная шлюпка может добраться до острова, либо сообщение "добраться невозможно".

Примечания

1. Все величины задаются в одой системе измерения.
2. Минимальное время в ответе должно быть верно с точностью до 3-х знаков после запятой.
3. Напомним вам, что вектор скорости шлюпки относительно земли находится как сумма вектора скорости течения (vtx, vty) и вектора скорости шлюпки относительно воды (vx, vy). Поскольку шлюпка может двигаться в любом направлении со скоростью, не превосходящей v, то длина вектора (vx,vy) не должна превышать v, т.е. vx*vx< =v*v.

Пример файла исходных данных INPUT.TXT:

2
5.2 7.65 3 0 0 0 3 3 0 2.5 17.8 0
4 3 3 0 0 0 3 3 0 2 1 1

Выходной файла OUTPUT.TXT для приведенного примера:

добраться невозможно
4.828427

Имя файла исходных данных INPUT.TXT
Имя выходного файла OUTPUT.TXT

рис.2

Задано арифметическое выражение, содержащее неотрицательные целые константы (неограниченного размера), знаки арифметических операций: "+", "-" (бинарный), "/", "*" и круглые скобки. По определенным правилам выражение графически изображается в виде двоичного дерева. Операции располагаются в вершинах дерева, а операнды образуют левое и правое поддеревья вершины с данной операцией. На рис.2 приведен пример графического изображения выражения (57+14)*35.

Требуется для данного выражения определить размеры (высоту и ширину) его графического изображения. Известно, что если A и B - операнды операции r, а HA и WA - высота и ширина графического представления выражения A, HB и WB - высота и ширина графического представления выражения B, то высотой и шириной графического представления выражения ArB будут 2+max(HA,HB) и 3+WA+WB соответственно. Для константы высота графического представления - 3, а ширина равняется количеству цифр в записи константы + 2. Например, если выражение A имеет высоту и ширину 1 и 3, выражение B имеет высоту и ширину 5 и 5, то выражение A*B будет иметь высоту 7 и ширину 11.

Выходные данные

Файл исходных данных содержит одно или несколько выражений. Каждое выражение записывается на отдельной строке. Максимальная длина выражения - 80 символов. Файл исходных данных не содержит пробелов и пустых строк.

Выходные данные

Для каждого выражения вывести в выходной файл на отдельной строке высоту и ширину графического представления.

Пример файла исходных данных INPUT.TXT:

((487652875872452))
31/12-1+79

Выходной файл OUTPUT.TXT для приведенного примера:

3 17
9 24

Примечание

Дерево выражения соответствует порядку применения операций к операндам. Предполагается стандартный приоритет операций (умножение и деление выполняется раньше сложения и вычитания). Операции с одинаковым приоритетом (+ и -, * и /) выполняются в порядке слева направо. Например, для выражения 1+2*3-4-5 порядок выполнения операций (показанный дополнительными скобками) следующий: ((1+(2*3))- 4)-5.

Имя файла исходных данных INPUT.TXT
Имя выходного файла OUTPUT.TXT

Злой Карабас-Барабас посадил в два темных подвала Буратино и Мальвину. Он разрешает им обмениваться письмами, но читает их, поскольку опасается, что они договорятся о побеге. К несчастью для Карабаса, пленники заранее договорились о способе передачи секретных сообщений. Для того, чтобы зашифровать сообщение из нулей и единиц пленники составляют письмо на правильном русском языке, в котором нулям из секретного сообщения соответствуют слова четной длины, а единицам - нечетной. Знаки препинания (точки, запятые, тире, и т.п.) при дешифровке не учитываются. В зашифрованном тексте запрещается:

1. повторять предложения;
2. дважды использовать слово в одном предложении (использовать одно слово в разных предложениях не запрещается).

Напишите программу, которая вводит секретное сообщение - последовательность не более, чем из 100 нулей и единиц и выводит его в зашифрованном виде. Зашифрованный текст должен быть составлен по правилам русского языка (т.е. не содержать орфографических, пунктуационных и синтаксических ошибок).

Исходные данные

Файл содержит одну или несколько секретных последовательностей. Каждая последовательность состоит не более, чем из 100 нулей и единиц и записывается на отдельной строке. Файл исходных данных не содержит пробелов и пустых строк.

Выходные данные

Для каждого секретного сообщения вывести в выходной файл его зашифрованный вариант. Сообщения в выходном файле должны разделяться пустой строкой. Сообщение не должно содержать пустых строк. Каждое зашифрованное сообщение может располагаться на нескольких строках, переносить слова запрещается.

Пример файла исходных данных INPUT.TXT:

110001000001000110100101110
0

Выходной файл OUTPUT.TXT для приведенного примера:

Мороз и солнце; день чудесный! Еще ты дремлешь, друг
прелестный - пора, красавица, проснись: открой сомкнуты
негой взоры на встречу северной Авроры, звездою севера
явись! (А.С.Пушкин)

Вечереет.

Примечание

Различные наборы исходных данных задают различные секретные сообщения, поэтому одно предложение может встречаться в разных зашифрованных текстах.

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

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

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

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

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

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

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

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

Пример: Temperature = -1 2. Арифметический оператор

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

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

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

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

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

Пример: READ

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

где 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 символов.

Интерпретатор