پاسخ - SGU 520

متن اصلی سوال : http://acm.sgu.ru/problem.php?contest=0&problem=520

ترجمه :

در یک کشور با n شهر آتش سوزی رخ داده ، به طوری که در ابتدا شهر پایتخت (با شماره ی 1) در روز یک آتش می گیرد و سپس در هر روز بعد همه ی همسایه های شهر های در حال سوختن نیز ، آتش می گیرند .
دو مامور آتش نشان یک روبات را برای خاموش کردن آتش به صورت نوبتی کنترل می کنند ( روز های فرد "Vladimir" و روز های زوج "Nikolay" ) ، این ربات در هر روز می تواند به یکی از شهر های مجاور برود ، و اگر روزی در یک شهرِ در حال سوختن باشد ، نابود می شود .
می دانیم که هیچ کدام از آتش نشان ها دوست ندارند در نوبت خودشان ربات نابود شود ، چون مجبور به پرداخت کردن جریمه به دولت می شود ، و همینطور می دانیم هر دوی آنها بسیار باهوش هستند .
می خواهیم بدانیم در نهایت چه کسی مجبور به پرداخت جرمیه می شود .

پاسخ پرسش CF-169-C

Codeforces / Contest 169 / Porblem C : Substring and Subsequence

صورت اصلی سوال : http://codeforces.com/contest/169/problem/C

ترجمه :

دو رشته با نام های s و t داریم.

می خواهیم تعداد زوج های x و y را پیدا کنیم که دارای شرایط زیر باشند :

• x زیر رشته ی s باشد
  
• y زیر مجموعه ی t باشد
• مقادیر x و y یکسان باشند
  

توجه کنید که تعریف زیر مجموعه و زیر رشته کاملا مجزا از هم است .

زیر رشته : یعنی بخشی از یک رشته به صورت پیوسته (از کاراکتر i ام تا کاراکتر j ام).

زیر مجموعه : یعنی تعدادی از کاراکتر های یک رشته (که البته می تواند شامل کاراکتر تکراری نیز باشد)

توجه کنید که در زیر مجموعه حروف زیر مجموعه ترتیب قرار گرفتن خود در t را حفظ می کنند.

پاسخ - SGU 269

متن اصلی سوال : http://acm.sgu.ru/problem.php?contest=0&problem=269
ترجمه :
یک board را اینگونه تعریف می کنیم - مجموعه ای از ردیف های از چپ به راست که هر ردیف تعدادی خانه از 1 تا 250 تا دارد و تعداد ردیف ها و اندازه هر ردیف در ورودی داده می شود ....

بزرگ‌ترین زیردنباله مشترک

Longest common subsequence

شرح مساله(ویکی پدیا) :

دو رشته زیر را در نظر بگیرید:

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