پاسخ - SGU 242

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

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

پاسخ - SGU 411

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

ترجمه : به شما دورشته A و B از حروف کوچک انگلیسی داده شده است، شما باید بزرگترین زیر رشته ی مشترک بین دو رشته که آینه ای (palindrome)هم باشد را در خروجی چاپ کنید. طول هر کدام از رشته ها از 2000 حرف تجاوز نمی کند.

ورودی : در دو خط ورودی رشته های A و B آمده است.

خروجی : در تنها خط خروجی بزرگترین زیر رشته ی مشترک بین A و B که آینه ای هست را چاپ کنید. تضمین شده پاسخ پرسش همواره به ازای ورودی های داده شده غیر تهی خواهد بود .

کد ++C

پاسخ - SGU 363

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

ترجمه : به یک مرکز فروش با m بادجه در طول روز n مشتری مراجعه می‌کنند. هرکس زمانی که به مرکز فروش می‌رسد به صفی می‌رود که کمترین تعداد افراد در آن حضور داشته باشند و اگر چند صف با این ویژگی وجود داشتند او صفی را انتخاب می‌کند که شماره‌ی آن کوچکتر باشد. وقتی نوبت در صف به نفر i ام می‌رسد, t_i ثانیه طول می کشد تا کار او انجام شود و سپس او از صف خارج می شود. اگر یک نفر درست زمانی به فروشگاه بیاید که چند نفر در حال انجام سفارش در بادجه ها هستند, او ابتدا صبر می کند تا این افراد از صف خود خارج شوند سپس صف خودش را انتخاب می‌کند. می دانیم نفر i ام در ثانیه k_i به فروشگاه می‌آید می‌خواهیم بدانیم هرکس چه صفی را انتخاب می‌کند و چه زمانی از فروشگاه خارج می‌شود.

پاسخ - SGU 226

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

ترجمه :

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

پاسخ - SGU 249

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

ترجمه:

جدولی با ابعاد  ارائه دهید که در آن اعداد 0 تا  هر کدام دقیقن یک بار آمده باشند و هر دو خانه ای که ضلع مشترک دارند، اعداد درونشان در نمایش بیتی دقیقن در یک خانه تفاوت داشته باشند. جدول چرخه ای است. یعنی خانه های ستون اول و آخر که در سطر یکسان هستند و همچنین خانه های سطر اول و آخر که در ستون یکسان هستند را با هم همسایه گیرید.

 

پاسخ - SGU 199

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

قبل نوشت: ترجمه نسبتا آزاد است.

ترجمه:

با اعتبار ترین کلوپ ورزشی شهر، دقیقا N عضو داره. هر کدوم از عضوها، یه درجه زیبایی و قدرت دارند. به بیان دقیق تر: i-امین عضو این کلوپ ( اعضا بر اساس هنگامی که وارد کلوپ شدن نامگزاری می شن ) قدرت S_i و زیبایی B_i داره. از اون جایی که این کلوپ، خیلی با اعتباره، اعضای اون خیلی پولدارن ( خوش به حالشون :D ) و کلا خیلی فوق العاده و خفنن. در نتیجه، معمولا کمتر از هم دیگه متنفر هستن. دقیق تر بخوایم بگیم: i-امین عضو از این کلوپ، آقای هـ از j-امین عضو این کلوپ آقای د متنفره اگر ( و فقط اگر ) S_i <= S_j و B_i>= B_j  یا این که S_i >= S_j  و   B_i <= B_j ( اگه جفت خصوصیات آقای هـ از آقای د بیشتر باشه، اصن آقای هـ متوجه آقای د نمی شه و اگه هم جفت خصوصیات کمتر باشه، آقای د به آقای هـ احترام میزاره. )

برای جشن سال نوی 2003 ( امسال 2013 ) میر کلوپ می خواد یه جشن رو برنامه ریزی کنه. البته می ترسه اگه دو تا از اعضایی که از هم متنفرن ، جفتشون به پارتی دعوت شن، ممکنه مست کنند و دعوا بشه. به خاطر همین نباید هیچ دو تا کسی که از هم متنفرن دعوت بشن. از طرف دیگه، مدیر می خواد اعتبار کلوپش رو حفظ کنه و برای این منظور، می خواد بیشترین تعداد افراد رو دعوت کنه.

یه برنامه بنویسید که بگه کی باید به پارتی دعوت بشه.

 

پاسخ - SGU 520

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

ترجمه :

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

پاسخ - SGU 143

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

ترجمه :

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

پاسخ - SGU 269

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