المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله‌ی سوم:دوره‌ی ۲۷:سوال ۵

تابع پرانتز

هوشنگ به تازگی با پرانتزگذاری ها آشنا شده است. یک دنباله‌ی پرانتزی دنباله ای از '$($` و '$)$` است. یک پرانتزگذاری حالت خاصی از دنباله‌های پرانتزی است، به این صورت که:

  • $()$ یک پرانتزگذاری است.
  • اگر $s$ یک پرانتزگذاری باشد، $(s)$ هم یک پرانتزگذاری است.
  • اگر $s$ و $t$ پرانتزگذاری باشند، $st$ هم یک پرانتزگذاری است.

هوشنگ عمل ‍‍«جابه‌جایی» روی یک پرانتزگذاری را اینگونه تعریف می‌کند: جابه‌جا کردن دو حرف مجاور، که اولی (سمت چپی) پرانتز بسته و دومی (سمت راستی) پرانتز باز باشد. می‌توان اثبات کرد که هر پرانتزگذاری بعد از هر عمل جابه‌جایی همچنان یک پرانتزگذاری می‌ماند.

هوشنگ ساعت‌ها این عمل را روی پرانتزگذاری‌های مختلف آزمایش کرده و دو تابع $f$ و $g$ را تعریف کرده است. ورودی هر دو تابع یک پرانتزگذاری است. $f(s)$ تعداد پرانتزگذاری‌های مختلفی است که پس از انجام دقیقاً یک عمل جابه‌جایی روی $s$ می‌توان به آن‌ها رسید. $g(s)$ تعداد پرانتزگذاری‌های مختلفی است که پس از انجام تعدادی (صفر یا بیشتر) عمل جابه‌جایی روی $s$ می‌توان به آن‌ها رسید.

هوشنگ از شما خواسته به سوالات زیر درباره این توابع پاسخ دهید.

$1$- الف ($11$ نمره) : باقی‌مانده‌ی تقسیم مجموع $g(s)$ برای همه ی $s$ های مختلف (پرانتزگذاری‌های مختلف) به طول $14$، بر $\Delta$ چند است؟

$2$- ب ($11$ نمره) : باقی‌مانده‌ی تقسیم مجموع $f(s)$ برای همه ی $s$ های مختلف (پرانتزگذاری‌های مختلف) به طول $70$، بر $\Delta$ چند است؟

$3$- ج ($11$ نمره) : باقی‌مانده‌ی تقسیم مجموع $g(s)$ برای همه ی $s$ های مختلف (پرانتزگذاری‌های مختلف) به طول $144$، بر $\Delta$ چند است؟


ابزار صفحه