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

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

ترجمه :

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