Challenger

المپیاد کامپیوتر , الگوریتم , برنامه نویسی , ترکیبیات , گراف , ....

Challenger

المپیاد کامپیوتر , الگوریتم , برنامه نویسی , ترکیبیات , گراف , ....

Challenger
طبقه بندی موضوعی
پیوندهای روزانه

۱۶ مطلب با موضوع «SGU» ثبت شده است

۲۴بهمن

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


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


محمد مهدی جهان آرا
۲۲بهمن

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


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


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


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


کد ++C

محمد مهدی جهان آرا
۱۸بهمن

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


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

محمد مهدی جهان آرا
۲۵دی

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


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

محمد مهدی جهان آرا
۱۶دی

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

ترجمه :

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

محمد مهدی جهان آرا
۱۳دی

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

ترجمه :

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

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

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

 

محمد مهدی جهان آرا
۱۲دی

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

ترجمه:

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

 

محمد مهدی جهان آرا
۱۲دی

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


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

ترجمه:

با اعتبار ترین کلوپ ورزشی شهر، دقیقا N عضو داره. هر کدوم از عضوها، یه درجه زیبایی و قدرت دارند. به بیان دقیق تر: i-امین عضو این کلوپ ( اعضا بر اساس هنگامی که وارد کلوپ شدن نامگزاری می شن ) قدرت Si و زیبایی Bi داره. از اون جایی که این کلوپ، خیلی با اعتباره، اعضای اون خیلی پولدارن ( خوش به حالشون :D ) و کلا خیلی فوق العاده و خفنن. در نتیجه، معمولا کمتر از هم دیگه متنفر هستن. دقیق تر بخوایم بگیم: i-امین عضو از این کلوپ، آقای هـ از j-امین عضو این کلوپ آقای د متنفره اگر ( و فقط اگر ) Si <= Sj و Bi>= Bj  یا این که Si >= Sj  و   Bi <= Bj ( اگه جفت خصوصیات آقای هـ از آقای د بیشتر باشه، اصن آقای هـ متوجه آقای د نمی شه و اگه هم جفت خصوصیات کمتر باشه، آقای د به آقای هـ احترام میزاره. )
برای جشن سال نوی 2003 ( امسال 2013 ) میر کلوپ می خواد یه جشن رو برنامه ریزی کنه. البته می ترسه اگه دو تا از اعضایی که از هم متنفرن ، جفتشون به پارتی دعوت شن، ممکنه مست کنند و دعوا بشه. به خاطر همین نباید هیچ دو تا کسی که از هم متنفرن دعوت بشن. از طرف دیگه، مدیر می خواد اعتبار کلوپش رو حفظ کنه و برای این منظور، می خواد بیشترین تعداد افراد رو دعوت کنه.

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

 

بنیامین دلشاد
۰۸آذر

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


ترجمه :

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

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


ترجمه :

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