لینک‌های مفید برای شرکت در مسابقه:

در حین مسابقه، می‌توانید سؤالات خود را از بخش «سؤال بپرسید» مطرح کنید.

آلیس افسرده می‌شود


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

محمد مُرد (محمد پس از انتقام خون پارسا به کتاب‌های صادق هدایت روی آورد و پس از مدتی به هیچ رسید "دنیا همه هیچ و اهل دنیا همه هیچ! / ای هیچ برای هیچ بر هیچ مپیچ." و سپس در روز ۹/۱۵ ...).

رومینا وضعیت رو که دید گفت خودم میرم دنبال آلیس پیداش می‌کنم. اما امان از کرونا. کرونا باعث شده بود آلیس افسردگی بگیره و خودش رو توی اتاق سحر آمیز حبث کنه. رومینا می‌خواست آلیس رو پیدا کنه و از کنج تنهایی درش بیاره که دستگیره‌ی در گفت برای باز شدن باید باید مسئله‌ی زیر را حل کنی!

یک رشته به طول nn شامل کاراکترهای [,],(,)[ , ] , (, ) داریم. تعداد براکت گذاری‌های معتبر به طول kk با حذف هیچ یا تعدادی از کاراکترهای این رشته را می‌خواهیم.

رشته‌ی SS یک براکت گذاری معتبر است اگر از کنار هم گذاری دو براکت گذاری معتبر T,FT, F به صورت TFTF یا از یک براکت گذاری معتبر TT به صورت [T][T] یا (T)(T) به دست آید.

دقت کنید که رشته‌های مقابل براکت گذاری‌های معتبری هستند: [()],[],(),[([])()][ ( ) ] , [ ], ( ) , [ ( [ ] ) ( ) ]
و رشته‌های مقابل نامعتبرند :‌ [(]),(][ ( ] ) , ( ]

میخوای دست به دماغم بزنی باید سوال جواب بدی :/

ورودی🔗

ورودی شامل دو خط است که در خط اول دو عدد طبیعی nn و kk با فاصله از هم آمده‌اند. 1n1051 \le n \le 10^5 1k161 \le k \le 16 در خط دوم یک رشته به طول nn از کاراکتر‌های [,],(,)[ , ] , (, ) آمده است.

خروجی🔗

در یک خط باقی مانده‌ی تعداد براکت گذاری‌های معتبر به طول kk را بر 109+710^9 + 7 چاپ کنید.

مثال🔗

ورودی نمونه ۱🔗

6 2
((()))
Plain text

خروجی نمونه ۱🔗

9
Plain text

به ۳ حالت می‌توانیم پرانتز باز را انتخاب کنیم و به ۳ حالت پرانتز بسته را، در نتیجه ۹ حالت داریم.

ورودی نمونه ۲🔗

6 2
([()])
Plain text

خروجی نمونه ۲🔗

5
Plain text

اگر دو کاراکتر انتخاب شده پرانتز باشند ۴ حالت داریم در غیر این صورت تنها یک حالت داریم. پس جواب نهایی ۵ می‌شود.

ارسال پاسخ برای این سؤال
در حال حاضر شما دسترسی ندارید.