Loading [MathJax]/jax/output/HTML-CSS/jax.js

المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:متفرقه:سوال های تمرینی دوره ی تابستان:سوال ۳۶

Parentheses

یک رشته‌ي کامل را به صورت زیر تعریف می‌کنیم:

  • () یک رشته‌ی کامل است.
  • [] یک رشته‌ی کامل است.
  • اگر S یک رشته‌ی کامل باشد، (S) یک رشته‌ی کامل است.
  • اگر S یک رشته‌ی کامل باشد، [S] یک رشته‌ی کامل است.
  • اگر S, T رشته‌های کامل باشند، ST نیز که از قراردادن T به دنبال S به‌دست می‌آید، رشته‌ای کامل است.

هر رشته‌ی کامل را می‌توان به این صورت ناقص کرد که تمام کاراکترهای '[' و ']' آن را به ')' تبدیل کرد. به شما از ورودی یک رشته‌ی ناقص داده می‌شود. شما باید تعداد رشته‌های کاملی را پیدا کنید که ناقص آن‌ها، برابر با رشته‌ی ورودی باشد.

ورودی

  • ابتدا n (طول رشته) به شما داده می‌شود. سپس رشته‌ی ورودی به شما داده می‌شود.
  • 1n10000

خروجی

شما باید باقی‌مانده‌ی تعداد رشته‌های خواسته شده را در تقسیم بر 1,000,000,009 بیابید.

محدودیت‌ها

  • محدودیت زمان: ۱ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت

ورودی و خروجی نمونه

ورودی نمونه خروجی نمونه
4
((()
2

پاسخ

منتظر پر کردن این قسمت توسط علاقمندان هستیم.


ابزار صفحه