متغیر $n$ تایی $x = (x_1,x_2,\cdots,x_n)$ و متغیر $m$ تایی $y=(y_1,y_2,\cdots,y_m)$ به شما داده شده است.
می‌دانیم تابع $F$ به صورت زیر تعریف شده است: $$ Boolean F(x,y):$$
$$ if W(x) \neq W(y) then return 0; $$
$$ else if |W(x)| = |W(y)| = 1 then return 1; $$
$$ else return F(p(x), p(y)) \wedge F(s(x), s(y));$$ که:
به طور مثال اگر $x = (2, 3, 7, 2, 7, 4, 7, 2, 4)$ باشد ، $W(x) = \{2, 3, 4, 7\}$ ، $p(x) = (2, 3, 7, 2, 7)$ و $s(x) = (7, 2, 7, 4, 7, 2, 4)$.
به شما متغیر های $x$ و $y$ داده شده است ، شما باید $F(x,y)$ را به‌دست آورید.
به ازای هر تست $F(x,y)$ مربوط به آن تست را چاپ کنید.
| ورودي نمونه | خروجي نمونه |
|---|---|
| 2 4 5 3 1 2 1 1 3 1 2 1 7 7 1 1 2 1 2 1 3 1 1 2 1 3 1 3 | 0 1 |
پاسخ
می‌توان نشان داد که شرط این که تابع $f$ مقدار true برگرداند برقرار بودن هر دو گزاره زیر است:
بدیهی است که اگر $|w(x)|$ برابر با $1$ باشد، شرط لازم و کافی برای این که تابع $f$ مقدار true برگرداند، دو شرط بالاست.
حال اگر $|w(x)| \geq 2$ باشد ، تنها در صورتی تابع $f$ مقدار true برمی‌گرداند که هر دو شرط برای $s(x),s(y)$ و $p(x),p(y)$ برقرار باشد که در این صورت هر دو شرط برای $x,y$ نیز برقرار است.
پس کافیست دو لیست $start$ و $end$ را برای $x$ و $y$ تولید کنیم و آن‌ها را با هم مقایسه کنیم و در صورتی پاسخ مثبت چاپ کنیم که هر دو برابر بودند.
پيچيدگي
دو لیست $start$ و $end$ را می‌توان با پیچیدگی زمانی $o(n \times \log n)$ برای $x$ و $y$ ساخت و مقایسه آن‌ها در زمان $o(n)$ امکان‌پذیر است. پس پیچیدگی الگوریتم برابر است با $o(n \log n)$.