پاسخ - SGU 242

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

ترجمه : n دانشجو شب گذشته را در یک میهمانی با هم گذرانده‌اند، حالا صبح شده و آنها باید به کلاس‌های خود بروند. مشکل اینجاست که همه‌ی دانشجو‌ها در یک دانشگاه تحصیل نمی‌کنند! آنها تصمیم میگیرند تا حداقل 2 نفر به هر کدام از k دانشگاه شهر بروند. البته بعضی از افراد می‌توانند روز را در خانه بگذرانند. هر کدام از دانشجو‌ها لسیتی از دانشگاه‌های شهر دارد که فقط حاظر به رفتن به یکی از آنهاست. به شما عدد n و k و لیست علاقه مندی‌ها و هر دانشجو را داده اند شما باید بگویید این کار ممکن است یا نه، و در صورتی که اینکار ممکن بود به ازای هر دانشگاه شماره‌ی دانشجو‌هایی که به آن دانشگاه می‌روند را چاپ کنید.

پاسخ - SGU 213

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

ترجمه : شما در یک کهکشان زندگی می کنید که در آن N ستاره وجود دارد و شما اهل ستاره‌ی شماره S هستید. در این کهکشان می توان مستقیما از ستاره‌ای به ستاره‌ای دیگر رفت اگر و تنها اگر بین آنها خط هوایی فضایی باشد. به تازگی حکومت ستاره‌ی شماره T با حکومت ستاره‌ی شماره S وارد جنگ شده، شما به عنوان فرمانده وظیفه دارید برای همایت از مهین خود راه رسیدن به سیاره‌ی خود را بر حکومت ستاره‌ی شماره‌ی T ببنید. هر خط هوایی فضایی بین دو ستاره بسته می‌شود اگر شما یک کشتی فضایی در آن مستقر کنید. به دلیل زیاد بودن منابع شما هیچ محدودیتی در تعداد کشتی‌ها ندارد ولی تنها مشکلی که شما دارید این است که هر کشتی یه قطعه‌ی کنترل کننده‌ی سری به نام کریستال دارد. ما می‌دانیم دشمن به اطلاعات همه‌ی کریستال‌هایی که ما استفاده خواهیم کرد به جز یکی دسترسی خواهد داشت. حالا باید کشتی ها را به گونه‌ای مستقر کنیم که اگر همه‌ی کریستال‌ها به جز یکی هم لو رفت مسیری از ستاره T به ستاره ما وجود نداشته باشد. در ضمن برای امنیت بیشتر باید تا انجایی که می توانیم از کریستال‌های مختلف استفاده کنیم (در تعداد و انواع کربستال ها محدودیت نداریم)

پاسخ - SGU 226

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

ترجمه :

گراف جهت دار G به شما داده شده است . هر یال آن با یکی از سه رنگ 1 و 2 و 3 رنگ شده است . از شما می خواهیم کوتاه ترین مسیر از راس 1 به راس n را طوری بیابید که هیچ دو یال متوالی در مسیر همرنگ نباشد.

پاسخ - SGU 103

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

ترجمه :

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

• مدت زمانی که طول می کشد تا از هر جاده عبور کنیم
• مدت زمان هر دو رنگ برای چراغ هر ایستگاه
• رنگ اولیه و زمان باقی مانده برای تغییر این رنگ در هر ایستگاه

شما باید کوتاه ترین مسیر بین دو ایستگاه داده شده در ورودی را پیدا کنید . اگر بیش از یک جواب وجود داشت می توانید یکی را به دلخواه در خروجی چاپ کنید .

 

پاسخ پرسش CF-111-D

Codeforces / Round #111 / Problem D: Edges in MST

صورت اصلی سوال :http://www.codeforces.com/contest/160/problem/D

ترجمه :

درخت پوشای کمینه (MST) : یک درخت پوشای کمینه از یک گراف وزن دار ، یک زیر درخت پوشا از آن است که مجموع وزن یال های آن کمینه باشد . واضح است که یک گراف همواره حداقل یک MST دارد و نیز می تواند چند MST داشته باشد .

یک گراف همبند وزن دار ساده به شما داده می شود . شما باید برای هر یال تعیین کنید این یال در همه MST های گراف ظاهر می شود یا در حداقل یکی از آنها ظاهر می شود یا در هیچکدام از آنها ظاهر نمی شود .

ورودی :
در خط اول ورودی دو عدد n و m داده می شود (تعداد راس ها و یال های گراف)
( , )
سپس در m خط بعدی ، مشخصات یال های گراف می آید ، در خظ i+1 ام سه عدد a_i,b_i,w_i می آید که به ترتیب دو سر یال i ام و وزن آن هستند .
 

خروجی :
m خط چاپ کنید ، در خط i ام اگر یال i ام در همه ی MST ها ظاهر میشود "any" را  ، اگر در حداقل یکی از MST ها ظاهر می شود "at least one" را و اگر در هیچکدام ظاهر نمی شود "none" را چاپ کنید .

پاسخ - SGU 520

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

ترجمه :

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

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

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

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

 

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

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

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

پاسخ - SGU 143

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

ترجمه :

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