Topological Sorting - مرتب سازی توپولوژیکی

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

« در نظریه گرافها، یک مرتب سازی موضعی یا ترتیب موضعی یک گراف بدون دور جهت دار، یک ترتیب خطی از همه رئوس آن است به طوری که هر گره قبل از همه گره‌هایی می‌آید که از آن به آنها یال خارج شده است. »

 

شرح الگوریتم : 

در هر مرحله می توانیم راس هایی را که هیچ یال ورودی ایی ندارند را در لیست قرار بدهیم

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

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

Codeforces / Contest 197 / Problem C : Lexicographically Maximum Subsequence

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

ترجمه :
رشته s ار حروف کوچک انگلیسی داده شده ، بزرگترین زیر رشته lexicographically این رشته را بیابید .

یک زیر رشته از s تعدادی از حروف s است که به ترتیب ظاهر شدنشان در رشته در زیر رشته می آیند .

یک زیر رشته x از زیر رشته y بزرگتر است اگر اندازه x بزرگتر از y باشد در حالی که همه کاراکتر های ۱ تا |y| در دو رشته مساوی باشند یا اینکه یک مقدار r وجود داشته باشد به طوری که همه ی کاراکت های ۱ تا r در دو رشته برابر باشند و کاراکتر  r+1 ام x بزرگتر از کارکتر r+1 ام y باشد .

پاسخ - SGU 180

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

ترجمه :

دنباله ای از N عدد صحیح بزرگ تر از صفر داریم داریم( N<=65537 ) به صورت A1, A2,.. AN و هر Ai<=10^9 . می خواهیم تعداد نا به جایی ها را در این دنباله از اعداد بیابیم .

نا به جایی : هر i و j که i<j و Ai>Aj .

ورودی :

خط اول عدد N و در خط بعدی N عدد دنباله به ترتیب آمده اند .

خروجی :

در تنها خط خروجی ، تعداد نا به جایی ها را چاپ کنید .

پاسخ - SGU 143

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

ترجمه :

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

پاسخ پرسش CF-157-E

Codeforces / Contest 157 / Problem E : Cipher

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

ترجمه :

یک رشته ی s از حرف کوچک لاتین به ما داده می شود ، در هر مرحله می توانیم دو حرف مجاور در رشته را انتخاب کنیم و یکی را به حرف قبلی خودش و دیگری با حرف بعد از خودش تغییر دهیم . واضح است که نمی توانیم حرف a را به حرف قبل از خودش و حرف z را به حرف بعد از خودش تبدیل کنیم .

برای مثال رشته ی abc را می توانیم به رشته ی bac ، acb و یا bbb (در دو مرحله) تبدیل کنیم .

می خواهیم به ازای رشته ی s تعداد رشته هایی را بیابیم که می توان این رشته را به آن ها تبدیل کرد .

توجه کنید این رشته ها شامل خود این رشته نمی شوند .

پاسخ - SGU 101

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

ترجمه متن سوال :

تعدادی مستطیل 1*2 داریم (دمینو) که در هر خانه آن یک عدد نوشته شده . می خواهیم این دمینو ها را جوری کنار هم بچینیم که خانه های مجاور دمینو های مختلف یک عدد داشته باشند .

1- مجاز به چرخاندن دمینو ها هم هستیم

2- عدد های رو دمینو ها از 0 تا 6 هستند .

پاسخ پرسش 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

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

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

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

Project Euler Problem 31

صورت اصلی سوال : http://projecteuler.net/problem=31
ترجمه :
در انگلستان واحد پول بر پایه پند و پنس است .
(£1=100p)
در کل هشت نوع سکه وجود دارد : 1p, 2p, 5p, 10p, 20p, 50p, £1-100p and £2-200p
برای مثال می تونیم دو پند رو به شکل زیر درست کنیم :
1£1 + 150p + 220p + 15p + 12p + 31p

چند راه متفاوت برای ساختن 2 پند وجود به طوری از هر سکه به تعدادی نا محدود در اختیار داشته باشیم ؟

___________________________________________

شرح راه حل : مسئله را با بهره گیری از برنامه ریزی پویا حل می کنیم ...
کد راه حل : http://snipt.net/JahanaraCo/project-euler-problem-31