| Имя входного файла: | input.txt |
| Имя выходного файла: | output.txt |
Задано уравненение вида A+B=C, где A, B и C - неотрицательные целые числа, в десятичной записи которых некоторые цифры заменены знаками вопроса "?". Например, ?65+443=2?4. Требуется подставить вместо знаков вопроса цифры, так чтобы равенство стало верным, либо определить, что это невозможно. Найти только одно из возможных решений.
Файл исходных данных содержит одну или несколько строк, в каждой из которых записано одно уравнение в виде A+B=C. Уравнение состоит не более, чем из 80 символов. Файл исходных данных не содержит пробелов и пустых строк.
Для каждого уравнения вывести в выходной файл на отдельной строке решение - верное равенство, полученное из исходного уравнения заменой знаков вопроса цифрами, либо сообщение "решения не существует".
| input.txt | output.txt |
2+2=5 ?+?=?? ??2?4+9?=355 | решения не существует 9+5=14 00264+91=355 |
| Имя входного файла: | input.txt |
| Имя выходного файла: | output.txt |
На одной из клеток шахматной доски (см. рисунок) стоит кубик. На гранях кубика написаны неотрицательные целые числа, не превосходящие 1000. Кубик можно перемещать на смежную клетку, перекатывая его через соответствующее ребро в основании. При движении считается сумма чисел, попавших в основание кубика (каждое число считается столько раз, сколько раз кубик оказывался на данном основании). Требуется найти такой путь движения кубика от начальной до заданной конечной клетки, при котором сумма чисел будет минимальной. Числа, стоящие в основании кубика в начальной и конечной позициях тоже входят в сумму. Начальная и конечная позиции различаются.
Первое строка в файле содержит количество наборов исходных данных. Каждый набор записывается на отдельной строке и задается следующим образом. В начале записываются координаты начальной и конечной позиций кубика. Координата состоит из прописной буквы и следующей за ней без пробела цифры (см. пример и рисунок). Далее следуют 6 чисел, записанных на гранях кубика. Первым идет число, записанное на передней грани, далее - на задней, верхней, правой, нижней и левой гранях соответстсвенно. Исходный файл не содержит пустых строк.
Для каждого набора исходных данных вывести в выходной файл на отдельной строке минимальную сумму и сам путь. Путь задается последовательным перечислением координат полей, по которым движется кубик. Путь должен начинаться начальной позицией и заканчиваться конечной позицией кубика. Координаты задаются также, как во входных данных.
| input.txt | output.txt |
2 a1 b2 1 1 1 1 1 1 e2 e3 0 8 1 2 1 1 | 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). Все числа в исходном файле разделяются пробелами и (или) символами перевода строки. Координаты и скорости задаются вещественными числами.
Для каждого набора исходных данных вывести в выходной файл на отдельной строке минимальное время, за которое спасательная шлюпка может добраться до острова, либо сообщение "добраться невозможно".
| input.txt | output.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 | добраться невозможно 4.828427 |
| Имя входного файла: | input.txt |
| Имя выходного файла: | output.txt |
Задано арифметическое выражение, содержащее неотрицательные целые константы (неограниченного размера), знаки арифметических операций: "+", "-" (бинарный), "/", "*" и круглые скобки. По определенным правилам выражение графически изображается в виде двоичного дерева. Операции располагаются в вершинах дерева, а операнды образуют левое и правое поддеревья вершины с данной операцией. На рисунке приведен пример графического изображения выражения (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 символов. Файл исходных данных не содержит пробелов и пустых строк.
Для каждого выражения вывести в выходной файл на отдельной строке высоту и ширину графического представления.
Дерево выражения соответствует порядку применения операций к операндам. Предполагается стандартный приоритет операций (умножение и деление выполняется раньше сложения и вычитания). Операции с одинаковым приоритетом (+ и -, * и /) выполняются в порядке слева направо. Например, для выражения 1+2*3-4-5 порядок выполнения операций (показанный дополнительными скобками) следующий: ((1+(2*3))-4)-5.
| input.txt | output.txt |
((487652875872452)) 31/12-1+79 | 3 17 9 24 |
| Имя входного файла: | input.txt |
| Имя выходного файла: | output.txt |
Злой Карабас-Барабас посадил в два темных подвала Буратино и Мальвину. Он разрешает им обмениваться письмами, но читает их, поскольку опасается, что они договорятся о побеге. К несчастью для Карабаса, пленники заранее договорились о способе передачи секретных сообщений. Для того, чтобы зашифровать сообщение из нулей и единиц пленники составляют письмо на правильном русском языке, в котором нулям из секретного сообщения соответствуют слова четной длины, а единицам - нечетной. Знаки препинания (точки, запятые, тире, и т.п.) при дешифровке не учитываются. В зашифрованном тексте запрещается:
Напишите программу, которая вводит секретное сообщение - последовательность не более, чем из 100 нулей и единиц и выводит его в зашифрованном виде. Зашифрованный текст должен быть составлен по правилам русского языка (т.е. не содержать орфографических, пунктуационных и синтаксических ошибок).
Файл содержит одну или несколько секретных последовательностей. Каждая последовательность состоит не более, чем из 100 нулей и единиц и записывается на отдельной строке. Файл исходных данных не содержит пробелов и пустых строк.
Для каждого секретного сообщения вывести в выходной файл его зашифрованный вариант. Сообщения в выходном файле должны разделяться пустой строкой. Сообщение не должно содержать пустых строк. Каждое зашифрованное сообщение может располагаться на нескольких строках, переносить слова запрещается.
| input.txt | output.txt |
110001000001000110100101110 0 | Мороз и солнце; день чудесный! Еще ты дремлешь, друг прелестный - пора, красавица, проснись: открой сомкнуты негой взоры на встречу северной Авроры, звездою севера явись! (А.С.Пушкин) Вечереет. |
Задача 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) команд в медленном (безопасном) режиме.
Все тоже самое, только имена переменных и метки могут состоять из 25 символов.
У Вас в распоряжении есть интерпретатор суперкомпьютера. Описание работы интерпретатора находится в архиве вместе с программой интерпретатора. Интерпретатор совершает случайные ошибки суперкомпьютера с заданной частотой. Вы можете использовать интерпретатор для отладки своей программы, но вы должны понимать, правильная работа "надежность" программы на случайных ошибках не гарантирует ее "надежности" в целом. При тестировании будет использоваться "хитрый" интерпретатор суперкомпьютера, который помимо случайных ошибок будет нарочно пытаться "сломать" вашу программу.