تطابق رشته


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

اگر به رفتار استف‌های کدکاپ ۳ در طول مسابقه دقت کرده‌باشید، درمی‌یابید که همه استفا عاشق مصطفی هستند.

در کدکاپ ۳ به هر کس ژتونی برای نهار داده شده که روی آن، رشته‌ای از حروف کوچک انگلیسی نوشته شده‌است.

محمود که یکی از استف‌های زحمت‌کش مسابقات است عقیده دارد از بین همه استف‌های عاشق مصطفی، مصطفی خودش عاشق استفی است که رشته نوشته شده روی ژتونش بیشترین درجه تطابق و طول تطابق با رشته خودش را داشته باشد. از این رو او می‌خواهد درجه تطابق و طول تطابق رشته‌ خودش را با رشته مصطفی حساب کند.

درجه تطابق و طول تطابق دو رشته به شکل زیر به دست می‌آید:

رشته مصطفی را با ss و رشته محمود را با tt نشان می‌دهیم، طول هر دوی این رشته‌ها برابر nn است. فرض کنید یک گراف دو بخشی با 2n2n رأس داریم که رأس‌های بخش اول متناظر با کاراکترهای رشته‌ی ss و رأس‌های بخش دوم متناظر با کاراکترهای رشته‌ی tt است. به ازای هر دو اندیس ii و jj (1i,jn1 \le i, j \le n) که کاراکتر ii-ام از رشته‌ی ss و کاراکتر jj-ام از رشته‌ی tt با یک‌دیگر برابر باشد یک یال بین رأس‌های متناظر این دو کاراکتر در گراف می‌گذاریم. طول تطابق رشته‌های ss و tt را برابر تعداد یال‌های بزرگ‌ترین تطابق در این گراف، و درجه تطابق رشته‌های ss و tt را برابر تعداد بزرگ‌ترین تطابق‌های این گراف می‌نامیم.

یک تطابق در گراف یک زیرمجموعه از یال‌های آن گراف است که هیچ دو یالی از آن در رأسی مشترک نیستند.

دو تطابق را متفاوت فرض می‌کنیم اگر مجموعه‌ی یال‌های آن‌ها متفاوت باشد.

حال محمود با دادن رشته مصطفی و رشته خودش به شما، از شما می‌خواهد که طول تطابق و باقی‌مانده درجه تطابق رشته خودش با رشته مصطفی به 109+710^9 + 7 را برای او بدست آورید.

ورودی🔗

در خط اول ss، که رشته مصطفی است، و در خط دوم رشته tt، که رشته محمود است، به شما داده می‌شود. دقت کنید که هر دو رشته‌ فقط از حروف کوچک انگلیسی تشکیل شده است. 1s,t200 000 1 \le |s| , |t| \le 200\ 000

خروجی🔗

در یک خط دو عدد جدا شده با فاصله از هم چاپ کنید که عدد اول طول تطابق دو رشته و عدد دوم باقی‌مانده درجه تطابق دو رشته به 109+710^9 + 7 است.

مثال🔗

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

salam
szszs
Plain text

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

1 3
Plain text

توضیح: در نمونه اول طول تطابق ۱ بوده (متناظر با رشته‌ s) و تعداد زیر دنباله‌های رشته محمود که با رشته مصطفی مطابق هستند و طولشان نیز یک می‌باشد برابر ۳ است.

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

mostafa
estafah
Plain text

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

5 2
Plain text

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

ab
ba
Plain text

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

2 1
Plain text

مرید تنبل


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

اگر به رفتار استف‌های کدکاپ ۳ در طول مسابقه دقت کرده‌باشید، درمی‌یابید که همه استفا عاشق مصطفی هستند.

تیمور که یکی از استف‌های زحمت‌کش مسابقات است عقیده دارد که از بین همه استف‌های عاشق مصطفی، مصطفی خودش عاشق استفی است که بتواند معماهای سخت را حل کند.

مصطفی معمایی طرح کرده و آن را برای همه استف‌ها فرستاده است تا آن را حل کنند.

او جدولی m×nm \times n برای استف‌ها فرستاده که هر خانه از آن x یا y است. استف‌ها می‌توانند در هر مرحله یک خانه از جدول را انتخاب کنند و محتوای‌ درون آن خانه را به x ، ‍y یا ‍‍z تبدیل کنند. استفی که بتواند در کمترین مراحل کاری کند که شرایط زیر برقرار باشد، این معما را حل کرده است.

۱- مسیری از یکی از خانه‌های سطر اول به یکی از خانه‌های سطر آخر وجود داشته باشد که خانه‌های آن فقط y و ‍z باشد.

۲- مسیری از یکی از خانه‌های ستون اول به یکی از خانه‌های ستون آخر موجود باشد که خانه‌های آن فقط x و ‍z باشد.

یک مسیر، دنباله‌ای از خانه‌های جدول است که در آن هر خانه به جز خانه آخر، با خانه بعدی‌اش مجاور ضلعی است.

از آنجایی که تیمور حوصله‌ی این سوسول بازی‌ها را ندارد از شما خواسته تا به او کمک کنید تا نظر مصطفی را جلب کند.

ورودی🔗

در خط اول ابتدا عدد nn که تعداد سطر‌های جدول است و سپس عدد mm که تعداد ستون‌های جدول است به شما داده می‌شود.

در هر یک از nn خط بعدی، یک رشته‌ به طول mm از حروف x و y داده شده است.

1n,m1 000 1 \le n , m \le 1 \ 000

خروجی🔗

در یک خط کمترین مراحل تغییر لازم برای برآورده کردن شرط‌های مصطفی را چاپ کنید.

مثال🔗

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

2 2
xy
yx
Plain text

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

2
Plain text

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

3 5
xyxyy
yyyxy
yyyyx
Plain text

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

3
Plain text

اسم فامیل


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

اگر به رفتار استف‌های کدکاپ ۳ در طول مسابقه دقت کرده‌باشید، درمی‌یابید که همه استفا عاشق مصطفی هستند.

علاوه بر استف‌ها، بچه‌های تیم علمی هم عاشق مصطفی هستند.

نگارنده‌ی این سوال نیز که یکی از عشاق مخلص مصطفی است هر چقدر سعی کرد نتوانست این سوال را به استف‌ها و مصطفی ربط دهد. در آخر مجبور شد این سوال را بدون هیچ حاشیه و داستانی برای شما بیان کند.

دو دنباله از اعداد طبیعی با نام aa و bb به طول nn داریم که اعضای آن‌ها را به ترتیب با aia_i و bib_i نشان می‌دهیم.

مقدار f(a,b)f(a,b) برابر است با تعداد اعضای مجموعه‌ی {(ai,bi)0in}\{(a_i, b_i) | 0 \leq i \leq n \}.

علامت (x,y)(x, y) به معنای زوج مرتب است، و دو زوج مرتب متفاوت اند اگر و فقط اگر در مولفه اول یا در مولفه دوم متفاوت باشد. مثلا (1,2)(1, 2) با (2,1)(2, 1) متفاوت است.

حال ما می‌خواهیم طوری ترتیب دنباله bb را تغییر دهیم که مقدار f(a,b)f(a, b) بیشینه شود. این مقدار بیشینه چند است؟

ورودی🔗

در خط اول nn که طول دنباله aa و bb است به شما داده می‌شود.

در خط بعدی nn عدد جدا شده با فاصله که اعضای دنباله‌ی aa است به شما داده می‌شود.

در خط بعدی nn عدد جدا شده با فاصله که اعضای دنباله‌ی bb است به شما داده می‌شود.

1n,ai,bi200 000 1 \le n, a_i, b_i \le 200 \ 000

خروجی🔗

در یک خط مقدار بیشینه تابع f(a,b)f(a, b) را چاپ کنید.

مثال🔗

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

5
3 2 2 2 3
1 1 5 2 2
Plain text

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

5
Plain text

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

5
1 2 1 2 1
4 2 4 2 4
Plain text

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

4
Plain text

پرانتزکوبی


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

اگر به رفتار استف‌های کدکاپ ۳ در طول مسابقه دقت کرده‌باشید، درمی‌یابید که همه استفا عاشق مصطفی هستند.

امیر روی میز سرور (که مصطفی پشت آن می‌نشیند) تکه کاغذی پیدا کرده است که روی آن یک رشته پرانتزگذاری معتبر به صورت رنگی نوشته شده است و هر حرف آن به رنگ خاصی است. او پی برد که یکی از استف‌ها با سلیقه‌ی خاصی پرانتزگذاری را به صورت رنگی برای بدست آوردن دل مصطفی نوشته است. او متوجه می‌شود که استف عاشق از سبک رنگ آمیزی کوبیسم استفاده کرده است.

رشته پرانتزگذاری ss با طول nn را در نظر بگیرید. برای هر حرف ii ،mim_i را برابر با اندیس پرانتز باز یا بسته متناظر با حرف ii رشته در نظر بگیرید. از آنجا که این پرانتزگذاری معتبر است، مقدار mim_i به ازای هر ii وجود دارد. برای مثال اگر دنباله پرانتزگذاری ما (())() باشد، دنباله‌ی mm برابر با {4,3,2,1,6,5}\{4, 3, 2, 1, 6, 5\} خواهد بود. این رشته یک رنگ آمیزی کوبی است اگر ویژگی‌های زیر را داشته باشد:

  1. هر حرف به یکی از رنگ‌های ۱ تا kk رنگ شده باشد.
  2. رنگ حرف ii و رنگ حرف mim_i باید برابر باشد.
  3. اگر mii1m_i \ne i-1 رنگ حرف ii با i1i-1 متفاوت باشد.
  4. اگر mii+1m_i \ne i+1 رنگ حرف ii با i+1i+1 متفاوت باشد.

امیر می‌خواهد تعداد رنگ‌آمیزی‌های کوبی متفاوت ss با kk رنگ را زیر آن تکه کاغذ بنویسد تا مصطفی را بیشتر حیرت‌زده کند! از آنجا که این عدد خیلی بزرگ‌ است، باقی‌مانده آن را بر 109+710^9 + 7 برایش بدست بیاورید.

ورودی🔗

در سطر اول ورودی دو عدد nn و kk آمده است. سپس در سطر بعد رشته پرانتزگذاری ss آمده‌است. تضمین می‌شود ss یک پرانتزگذاری معتبر است.

1kn200 0001 \le k \le n \le 200\ 000 s=n|s| = n

خروجی🔗

در تنها سطر خروجی باقی‌مانده تعداد روش‌های رنگ‌آمیزی کوبی ss با kk رنگ را بر 109+710^9+7 چاپ کنید.

مثال🔗

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

4 2
(())
Plain text

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

2
Plain text

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

6 3
(())()
Plain text

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

12
Plain text

قله‌ی ترافیک روی درخت


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

اگر به رفتار استف‌های کدکاپ ۳ در طول مسابقه دقت کرده‌باشید، درمی‌یابید که همه استفا عاشق مصطفی هستند.

کشور کوئرا از nn شهر تشکیل شده است که این nn شهر با n1n - 1 جاده دوطرفه به هم متصل شده‌اند به طوری که از هر شهر می‌توان با طی کردن تعدادی جاده به شهر شماره ۱ رسید.

شهر شماره ۱ پایتخت کشور کوئراست و هرساله مجموعه مسابقات کدکاپ در این شهر برگزار می‌شود.

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

متاسفانه مسابقه کدکاپ با تعمیر جاده‌های کشور کوئرا توسط وزارت راه و ترابری، مصادف شده است و جاده‌ی شماره ii که دو شهر xix_i و yiy_i را به هم وصل می‌کند از روز lil_i تا روز rir_i در درست تعمیر است و امکان عبور از آن وجود ندارد. (یعنی اگر در روز kk‌ ام به شهر xix_i برسیم به طوری که likri l_i \le k \le r_i، باید تا روز ri+1r_i + 1 صبر کنیم تا بتوانیم به شهر yiy_i برویم)

به دلیل پیشرفت فناوری‌های ترابری در کشور کوئرا مدت زمانی که طول می‌کشد تا از یک جاده عبور کنیم (به شرط باز بودن آن) به صفر ثانیه رسیده‌است. یعنی در طول سفر از یک شهر به شهر دیگر تنها چیزی‌ که باعث معطل شدن ما می‌شود بسته بودن جاده‌‌ها است.

حال مصطفی می‌خواهد بداند به ازای هر شهر، استف‌هایی که آن شهر برای کدکاپ می‌فرستد روز چندم به محل برگزاری مسابقات یعنی شهر ۱ می‌رسند. از آنجایی که کار سرورهای کدکاپ هنوز تمام نشده مصطفی این مسئولیت خطیر را به شما می‌سپرد.

دقت کنید که تمامی استف‌ها در ثانیه‌ صفر از مبدا خود به سمت شهر ۱ راه می‌افتند.

ورودی🔗

در یک خط عدد nn که تعداد شهرهای کشور کوئراست به شما داده می‌شود.

در n1n - 1 خط بعدی، درهر خط ۴ عدد xix_i و yiy_i و lil_i و rir_i به شما داده می‌شود که به این معناست که جاده ii ام شهر xix_i و yiy_i را به هم وصل می‌کند و در زمان lil_i تا rir_i در دست تعمیر است.

2n500 000 2 \le n \le 500 \ 000 1xi,yin 1 \le x_i , y_i \le n 0liri500 000 0 \le l_i \le r_i \le 500 \ 000

تضمین می‌شود که با جاده‌های داده شده، از همه‌ی شهرها می‌توان به شهر شماره ۱ رسید.

خروجی🔗

در nn خط به ازای هر شهر یک عدد چاپ کنید که نشان می‌دهد استف‌های آن شهر در روز چندم به شهر ۱ ام می‌رسند.

مثال🔗

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

2
1 2 1 2
Plain text

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

0
0
Plain text

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

3
1 2 3 4
2 3 0 2
Plain text

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

0
0
5
Plain text

رباتْ کریم


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

اگر به رفتار استف‌های کدکاپ ۳ در طول مسابقه دقت کرده باشید، درمی‌یابید که همه استفا عاشق مصطفی هستند.

چند روز پیش تولّد مصطفی بود و به همین مناسبت استف‌ها برای او یک ربات به اسم کریم خریدند. کریم در یک زمین بازی مستطیلی به ابعاد n×mn \times m قرار می‌گیرد و یک دنباله از دستورات را دریافت می‌کند و طبق آن‌ها در زمین بازی حرکت می‌کند. دور زمین بازی دیوار کشیده شده است و بعضی از مربّع‌های 1×11 \times 1 شامل مانع هستند؛ در صورتی که کریم به دیوار دور زمین یا یکی از این موانع برخورد کند، منفجر می‌شود و مصطفی ناراحت می‌شود.

هر دستوری که کریم دریافت می‌کند، با یکی از حروف D(حرکت به سمت پایین)، U(حرکت به سمت بالا)، R(حرکت به سمت راست) یا L(حرکت به سمت چپ) نمایش داده می‌شود. بنابراین اگر کریم مجموعه‌ی دستورات DDRUL را دریافت کند، ابتدا به اندازه‌ی ۲ خانه (مربّع 1×11 \times 1) به پایین می‌رود. سپس یک خانه به راست، یک خانه به بالا و در نهایت یک خانه به چپ می‌رود.

مصطفی بسیار ریسک‌پذیر است؛ او به پیشنهاد تیم علمی مبنی بر انجام یک بازی بسیار خطرناک با کریم جواب مثبت داده! بازی سه مرحله دارد. در مرحله‌ی اوّل*، تیم علمی یک دنباله از دستورات کریم را بیان می‌کنند. در مرحله‌ی *دوم مصطفی باید کریم را در یکی از n.mn.m خانه‌ی زمین بازی که شامل مانع نیست، قرار دهد. در مرحله‌ی سوم نیز، تیم علمی می‌تواند ترتیب دستورات در دنباله‌ای که مشخّص کرده بود را عوض کند. مثلن اگر دنباله‌ی دستورات ابتدایی RRDDLLUU باشد، پس از آن که مصطفی کریم را در یکی از خانه‌های زمین بازی قرار داد، تیم علمی می‌تواند دنباله‌ی دستوراتش را به URLDURLD تغییر دهد.

در مرحله‌ی بعد نیز دنباله‌ی دستورات جدید را به کریم می‌دهیم و کریم طبق آن دستورات شروع به حرکت می‌کند. اگر کریم منفجر شود، مصطفی می‌بازد و ناراحت می‌شود، و در غیر این صورت مصطفی برنده‌ی میدان خواهد شد!

می‌دانیم به ازای برخی از دنباله‌های دستورات که تیم علمی در مرحله‌ی اوّل انتخاب می‌کند، مصطفی در مرحله‌ی دوم کریم را هر جای زمین بازی قرار دهد، در مرحله‌ی سوم تیم علمی می‌تواند جابه‌جایی‌های دستورات را طوری انجام دهد که مصطفی ببازد. در بین این دنباله‌های دستورات، طول کوتاه‌ترین دنباله را بیابید.

ورودی🔗

در خط اول دو عدد nn و mm ابعاد جدول به شما داده می‌شود.

در هر یک از nn خط بعدی، mm کاراکتر داده می‌شود. چنان‌چه خانه‌ی jjام در سطر iiام زمین بازی شامل مانع باشد، کاراکتر jjامِ خط iiام برابر # و در غیر این صورت برابر . خواهد بود.

1n,m2 000 1 \le n, m \le 2 \ 000

خروجی🔗

در یک خط طول کوتاه‌ترین دنباله‌ی ممکن با شرایط گفته شده را چاپ کنید.

مثال🔗

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

3 3
...
...
.##
Plain text

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

3
Plain text

به طور مثال دنباله‌ی دستورات RUU برای این مثال مطلوب است.

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

3 4
####
.###
.#..
Plain text

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

2
Plain text

رمز عبور


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

اگر به رفتار استف‌های کدکاپ ۳ در طول مسابقه دقت کرده‌باشید، درمی‌یابید که همه استفا عاشق مصطفی هستند. شایعه شده‌است که او از یکی از استف‌ها خوشش میاید و اسم او را در دفترچه یادداشت دیجیتالش نوشته‌است! هر کسی در زندگی‌اش رمزهایی دارد، مصطفی نیز دفترچه‌اش بی‌رمز نیست و رمزی طولانی دارد!

ساعت ۴ صبح دیروز، مصطفی که بعد از آماده‌سازی‌های کدکاپ خیلی خسته بود، حواسش نبود و کلید اسرارش را فاش کرد! او به جواد که کنار او نشسته بود جدولی نشان می‌دهد (شکل زیر) و می‌گوید که ۴ دنباله aa، bb، cc و dd به طول nn دارد که دنباله‌های cc و dd تنها از ۰ و ۱ تشکیل شده‌اند. او از این دنباله جدولی n×nn \times n می‌سازد که در خانه‌ی واقع در سطر ii و ستون jj عدد ai×bj×(cidj)a_i \times b_j \times (c_i \oplus d_j) قرار دارد (\oplus نماد عملگر XOR است). سپس به جواد می‌گوید که رمز دفترچه یادداشت دیجیتالش جمع اعداد زیرجدولی k×kk \times k است که جمع اعدادش بیشینه است!

جدول مصطفی

اکنون مصطفی از فرط خستگی خوابش برده‌است. جواد موفق شده‌است ۴ دنباله aa، bb، cc و dd را بیابد. حال شما باید رمز دفترچه یادداشت دیجیتال مصطفی را بیابید.

ورودی🔗

سطر اول ورودی شامل دو عدد nn و kk است. سپس در سطر دوم دنباله a1,...,ana_1, ..., a_n شامل nn عدد آمده‌است. سپس به همین شکل در سطر سوم دنباله bb و در سطر چهارم دنباله cc و در سطر پنجم دنباله dd آمده‌است. همه اعداد ورودی اعدادی صحیح هستند.

2kn200 0002 \le k \le n \le 200\ 000 0ai,bi1 0000 \le a_i, b_i \le 1\ 000 0ci,di10 \le c_i, d_i \le 1

خروجی🔗

در تنها سطر خروجی رمز دفترچه یادداشت دیجیتال مصطفی را چاپ کنید.

مثال🔗

ورودی نمونه🔗

3 2
3 4 1
2 1 3
1 0 1
0 1 0
Plain text

خروجی نمونه🔗

13
Plain text