G. Урвуу функц

хугацааны хязгаарлалт 5 секунд

санах ойн хязгаарлалт 64 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Петя нэгэн сонирхолтой функц $f(n)$-ыг тооцоолдог программыг C++ дээр бичжээ. Петя нэгэн тодорхой $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$ доторх хоосон зайг өөрсдөө сонгож болно.

Түүнчлэн бидэнд 2 төрлийн оператор-оос тогтох нэгэн функц байх юм. "return $arithmExpr$;" гэсэн оператор нь уг илэрхийллийн утгыг функцийн утга болгон буцаах ба "if ($logicalExpr$) return $arithmExpr$;" гэсэн нөхцөлт оператор нь зөвхөн логик нөхцөл нь үнэн байх үед уг арифметик илэрхийллийн утгыг буцаадаг ажээ. Мөн C++ хэлний бусад хэрэгсэл буюу циклүүд, тушаал олгох операторууд болон хайрцагласан нөхцөлт операторуудыг уг функц дотор ашиглаагүй байх бөгөөд $n$ параметрээс бусад бүх хувьсагчдыг уг функц дотор ашиглаагүй байна. Бүх тогтмол тоонууд нь $[0..32767]$ гэсэн интервал доторх бүхэл тоонууд байх юм.

Операторуудыг дарааллын дагуу гүйцэтгэнэ. Функц ямар нэгэн утга буцаасны дараа уг дараалалд байх бусад операторуудыг гүйцэтгэхээ болих юм. Арифметик илэрхийллүүдийг гүйцэтгэхдээ тооны үйлдлийг гүйцэтгэх стандарт дарааллын дагуу гүйцэтгэх ба өөрөөр хэлбэл хамгийн эхэнд нийлбэр дотор байх бүх үржвэрүүдийг тооцоолно гэсэн үг юм. Үржих болон хуваах үйлдлүүдийн үржвэрийг тооцоолох явцдаа зүүнээс баруун хүртэлх дарааллын дагуу гүйцэтгэх юм. Дараа нь нэмэгдэхүүнүүдийг нэмэх бөгөөд нэмэх болон хасах үйлдлүүдийг зүүнээс баруун хүртэлх дарааллын дагуу гүйцэтгэнэ. ">" (их), "<" (бага) болон "==" (тэнцүү) гэсэн үйлдлүүд нь мөн адил үндсэн утгаа агуулж байх юм.

Одоо та анхаарлаа хандуулах хэрэгтэй! Программ нь Берланд-ын Берсофт хэмээх нэгэн компанийн бүтээсэн $15$-битийн С++ шалгагч программаар шалгагдах бөгөөд ийм учраас арифметик үйлдлүүдийг энгийн биш аргаар гүйцэтгэх юм. Нэмэх, хасах болон үржих үйлдлүүдийг $32768$ модулаар бодож гүйцэтгэнэ. Хэрэв хасах үйлдлийн хариу нь сөрөг тоо байвал уг хариуг $[0..32767]$ интервалд харьяалагдтал $32768$-г уг тоон дээр нэмэх юм. Хуваах "/" үйлдэл нь энгийн бүхэл тооны хуваах үйлдэл бөгөөд бид энд үлдэгдлийг тооцохгүй хаях юм.

Доор арифметик үйлдлүүдийн жишээг үзүүлэв:

$0$-ээс $32767$ хүртэлх бүх $n$-ын утгуудын хувьд өгөгдсөн функц нь алдаагүй зөв ажиллаж байх юм. Өөрөөр хэлбэл:

1. Тоог $0$-д хуваах ямар нэгэн хуваах үйлдэл хэзээ ч бодлогод гарч ирэхгүй.

2. $n = N$ утгатай байхад функцийг ажиллуулахад $f$ функцийн рекурсив(дахин давтагддаг) дуудлагууд нь зөвхөн $0, 1, ..., N - 1$ гэсэн параметрийн утгууд дээрх функцийн утгууд байж болох юм. Тийм учраас программ нь хэзээ ч хязгааргүй тооны рекурсив дуудлага хийхгүй байна.

3. Операторуудын дарааллыг гүйцэтгэсний дараа үр дүнд нь функц үргэлж ямар нэгэн утга буцаана.

Бүх хязгаарлалтаас хамааран $f$ функцийн буцаах утга нь бүх хувьсагчид эсвэл логик үйлдлийн нэгэн хэсэг байх арифметик илэрхийллийн тооцооллыг гүйцэтгэх дараалал эсвэл $n$ параметрийн утгаас бусад ямар ч утгаас огт хамааралгүй болохыг энд дурдах хэрэгтэй юм. Ийм учраас $f$ функцийг өөрийнх нь математик шинжийнх(өөрөөр хэлбэл $[0..32767]$ интервал дахь ямар ч $n$-ын утгын хувьд мөн тус интервал дахь $f(n)$-ын утга цор ганц байдлаар харгалзаж байгаа юм) нь дагуу функц гэж үзнэ.

$f(n)$-ын өгөгдсөн утгын хувьд та $n$-г олох ёстой юм. Хэрэв тохиромжтой $n$-ын утга нь цор ганц биш байвал та хамгийн ихийг нь олно уу ($[0..32767]$ гэсэн интервалаас олно).

Оролт

Эхний мөрөнд $[0..32767]$ интервалд байх бүхэл тоо $f(n)$ өгөгдөнө. Дараагийн мөрүүдэд $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
Сэтгэгдлүүдийг ачааллаж байна...