Петя написал программу на C++, вычисляющую значение одной интересной функции f(n). Петя запустил программу при некотором значении n и отправился на кухню пить чай. О том, сколько времени работала программа, история умалчивает. Когда Петя вернулся, она уже закончила выполнение и выдала результат. Однако пока Петя пил чай, коварный вирус успел уничтожить входной файл, поэтому Петя не может восстановить, для какого значения n была запущена программа. Помогите Пете: реализуйте обратную функцию!
Основную часть программы представляет собой функция на C++ со следующим упрощенным синтаксисом:
- function ::= int f(int n) {operatorSequence}
- operatorSequence ::= operator | operator operatorSequence
- operator ::= return arithmExpr; | if (logicalExpr) return arithmExpr;
- logicalExpr ::= arithmExpr > arithmExpr | arithmExpr < arithmExpr | arithmExpr == arithmExpr
- arithmExpr ::= sum
- sum ::= product | sum + product | sum - product
- product ::= multiplier | product * multiplier | product / multiplier
- multiplier ::= n | number | f(arithmExpr)
- number ::= 0|1|2|... |32767
Пробелы и переводы строк в operatorSequence — необязательны.
Таким образом, имеется функция, в теле которой встречается два вида операторов. Это оператор "return arithmExpr;", возвращающий в качестве значения функции значение арифметического выражения, и условный оператор "if (logicalExpr) return arithmExpr;", который возвращает значение арифметического выражения в том и только в том случае, когда выполняется логическое выражение. Гарантируется, что никакие другие конструкции языка C++: циклы, операторы присваивания, вложенные условные операторы и т.д. и другие переменные, кроме параметра n, в функции не используются. Все константы являются целыми числами из промежутка [0..32767].
Операторы выполняются последовательно. После того, как произойдет возврат функцией некоторого значения, остальные операторы в последовательности не выполняются. Арифметические выражения вычисляются с учетом стандартного приоритета операций. Это означает, что сначала вычисляются все произведения, входящие в сумму. При вычислении произведения операции умножения и деления выполняются слева направо. Затем происходит суммирование слагаемых, при этом сложение и вычитание тоже выполняются слева направо. Операции ">" (больше), "<" (меньше) и "==" (равно) тоже имеют стандартный смысл.
Теперь внимание! Программа компилируется с помощью разработанного берляндской компанией BerSoft 15-битного компилятора Berland C++, поэтому арифметические действия выполняются нестандартным образом. Сложение, вычитание и умножение выполняются по модулю 32768 (если при вычитании получается отрицательное число, то к нему прибавляется 32768 до тех пор, пока оно не окажется в промежутке [0..32767]). Деление "/" — это обычное целочисленное деление с отбрасыванием остатка.
Примеры арифметических действий:
Гарантируется, что при любом значении n от 0 до 32767 заданная функция выполняется корректно. Это означает, что:
1. Не происходит деления на 0.
2. При выполнении функции для значения n = N рекурсивные вызовы функции f могут роисходить только для значений параметра 0, 1, ..., N - 1. Следовательно, программа никогда не уходит в бесконечную рекурсию.
3. В итоге выполнения последовательности операторов обязательно происходит возврат значения функции.
Заметим, что в силу всех введенных ограничений значение, возвращаемое функцией f, не зависит ни от глобальных переменных, ни от порядка вычисления арифметических выражений в составе логического, ни от чего либо другого, кроме значения параметра n. Поэтому функцию f можно рассматривать как функцию в математическом смысле, т.е. как однозначное соответствие каждому значению n из промежутка [0..32767] значения f(n) из того же промежутка.
Вам дано значение f(n), нужно найти n. Если подходящих значений n несколько, требуется определить максимальное (из промежутка [0..32767]).