Петя написал программу на C++, вычисляющую значение одной интересной функции f(n). Петя запустил программу при некотором значении n и отправился на кухню пить чай. О том, сколько времени работала программа, история умалчивает. Когда Петя вернулся, она уже закончила выполнение и выдала результат. Однако пока Петя пил чай, коварный вирус успел уничтожить входной файл, поэтому Петя не может восстановить, для какого значения n была запущена программа. Помогите Пете: реализуйте обратную функцию!
Основную часть программы представляет собой функция на C++ со следующим упрощенным синтаксисом:
Пробелы и переводы строк в 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]).
В первой строке содержится целое число f(n) из промежутка [0..32767]. В следующих строках содержится описание функции f. В описании могут встречаться дополнительные пробелы и переводы строки (см. примеры), которые, разумеется, не могут разрывать ключевые слова int, if, return и числа. Размер входных данных не превосходит 100 байт.
Выведите единственное число — ответ на задачу. Если решения не существует, выведите "-1" (без кавычек).
17
int f(int n)
{
if (n < 100) return 17;
if (n > 99) return 27;
}
99
13
int f(int n)
{
if (n == 0) return 0;
return f(n - 1) + 1;
}
13
144
int f(int n)
{
if (n == 0) return 0;
if (n == 1) return n;
return f(n - 1) + f(n - 2);
}
24588
Название |
---|