−فهرست مندرجات
Algorithm Speedup
متغیر n تایی x=(x1,x2,⋯,xn) و متغیر m تایی y=(y1,y2,⋯,ym) به شما داده شده است.
می‌دانیم تابع F به صورت زیر تعریف شده است: BooleanF(x,y):
ifW(x)≠W(y)thenreturn0;
else if |W(x)| = |W(y)| = 1 then return 1;
else return F(p(x), p(y)) \wedge F(s(x), s(y)); که:
- W(x) برابر است با مجموعه عناصر x
- p(x) برابر است با بزرگ‌ترین پیشوند x که W(x) \neq W(p(x))
- s(x) برابر است با بزرگ‌ترین پسوند x که W(x) \neq W(s(x))
- \wedge علامت and منطقی است و |Z| برابر تعداد عناصر Z است.
به طور مثال اگر 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) را به‌دست آورید.
ورودی
- در سطر اول ورودی 1 \leq t \leq 13 نشان‌دهنده تعداد تست‌ها آمده است.
- سطر اول هر تست دو عدد 1 \leq n,m \leq 10^5 آمده است.
- در سطر بعدی n عدد x_1 تا x_n آمده است.
- در سطر سوم هر تست m عدد y_1 تا y_m آمده است.
- مقادیر x_i ها و y_i ها بین 1 و 100 است.
خروجی
به ازای هر تست 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 برگرداند برقرار بودن هر دو گزاره زیر است:
- اگر start(x) برابر با لیستی از x_i هایی باشد که هیچ x_{j < i} برابر با x_i وجود ندارد و ترتیب قرار گرفتن عناصر آن به همان ترتیب حضور عناصر در x است باشد ، start(x) باید با start(y) برابر باشد.
- اگر end(x) برابر با لیستی از x_i هایی باشد که هیچ x_{j > i} برابر با x_i وجود ندارد و ترتیب قرار گرفتن عناصر آن به همان ترتیب حضور عناصر در x است باشد ، end(x) باید با end(y) برابر باشد.
بدیهی است که اگر |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).
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
