پاسخ - 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 ) میر کلوپ می خواد یه جشن رو برنامه ریزی کنه. البته می ترسه اگه دو تا از اعضایی که از هم متنفرن ، جفتشون به پارتی دعوت شن، ممکنه مست کنند و دعوا بشه. به خاطر همین نباید هیچ دو تا کسی که از هم متنفرن دعوت بشن. از طرف دیگه، مدیر می خواد اعتبار کلوپش رو حفظ کنه و برای این منظور، می خواد بیشترین تعداد افراد رو دعوت کنه.

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

 

رونق گرفتن وبلاگ!

درود.

تصمیم گرفتیم که وبلاگ رو فعال تر کنیم ، و از این به بعد کارای جدیدی انجام میدیم تو بلاگ .

سوال هفتگی: هر هفته جمعه یک سوال ترکیبیات یا گراف زیبا و یک سوال الگوریتم زیبا می ذاریم و تا هفته ی بعدش ، می تونید جواباتونو میل کنید. هفته ی بعد نام افرادی که جواب درست فرستادن رو می ذاریم + حل سوال + سوال بعدی. بعد هم سوالات می رن تو آرشیو سوالات هفتگی.

که بخش ترکیبیات و گراف با منه و الگوریتمش با محمدمهدی‌جهان‌آرا :D

اگه پیشنهاد و یا سوالی داشتید به ما میل بزنید.

[e-mail]

[e-mail]

شاد باشید.

:)

---

پ.ن : بخش آرشیو سوالات و کتاب ها آپدیت شد .

مرحله یک دوره بیستم!

سلام :)

ما نیت کردیم دست گرمی آزمون مرحله اول دوره 20 رو بدیم :D

بعد گفتیم هر کی هم می خواد با ما بده.

در این راستا

ما قرار گذاشتیم هر کی خواست بده سه ساعت وقت بزاره و تا 5شنبه جواباشو بفرسته :D

هر کی دوس داشت جواباشو میل کنه ما درصد بگیریم (هرچند خودتونم می تونید این جوری کلاس کار بالاتره :دی)

[e-mail]

رده بندی هم اعلام می شه (اگه استقبال بشه) :D

سوالات مرحله ی اول - دوره ی بیستم (inoi.ir)

موفق باشید :D

توضیحات:

سوال دو حذف هست!

سوال شانزده می گه: بر روی یک عدد 8 بیتی(اشتباهن 16 بیتی نوشته شده!)

سوال 22 مثالش غلطه!

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

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

ترجمه :

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

پاسخ - SGU 520

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

ترجمه :

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

پاسخ - SGU 155

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

 

ترجمه :

یک درخت BST ، یک درخت ریشه دار است که هر راس در آن حداکثر دو فرزند دارد و کلید تمام راس های زیر درخت سمت چپ هر راس از کلید آن راس کوچکتر و کلید تمام راس های زیر درخت سمت راست هر راس از آن بزرگتر اند .

درخت cartesian یک نوع خاص از درخت های BST است که در آن هر راس دو کلید دارد و کلید دوم هر راس از کلید دوم همه راس هایی که در زیر درخت آن هستند کوچک تر است .

پاسخ - SGU 499

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

 

ترجمه :

n نفر داریم که دو به دو با هم دوست اند ، هر کدام از افراد یک «عدد دوستی» دارد . میزان دوستی دو نفر را برابر با بزرگترین مقسوم علیه مشترک(ب.م.م) عدد دوستی آن دو نفر میدانیم .می خواهیم بدانیم بیشترین میزان دوستی بین این n نفر چقدر است .

 

ورودی :

در اولین خط ورودی عدد n داده می شود

و در n خط بعدی اعداد دوستی افراد داده می شود .

همه ی اعداد دوستی بین 1 و 1000000 هستند (شامل خود این اعداد)

 

خروجی :

در تنها خط خروجی بیشترین میزان دوستی بین این n نفر را چاپ کنید .

 

نتایج مرحله دوم اعلام شد

سلام
بالاخره نتایج مرحله دوم اعلام شد ، امسال همونطور که شایعه شده بود 80 نفر گرفتن ، یه سری قبول شدن و یه سری که واقعا لایق قبولی بدون قبول نشدن ...
به همه کسایی که قبول شدن تبریک می گم و امیدوارم مرحله 3 عادلانه و خوبی رو داشته باشن و ازش حداکثر لذت رو ببرن :)
به کسایی که قبول نشدن هم تبریک میگم ، به خاطر المپیادی بودنشون ، باور کنید اگه واقعا به المپیاد علاقه داشتید و به خاطر علاقه اونو دنبال کردید ، هرگز چیزی از دست نمی دید .
امسال یکی از بهترین سالای زندگی من بود تا اینجا ، چندتا دوست خیلی خوب پیدا کردم ، تجربه های خیلی خوبی داشتم ، فک کنم 10-15 سال بزرگ شدم (!) :D

فقط چندتا چیز :
1- نتایج هنوز قطعی نیست !
2- شانس هم تاثیر داره ، پس بدانید و آگاه باشید ، خفن ترین آدمها هم ممکنه قبول نشن ، پس زیاد مهم نیست !
3- دعا کنید برام مرحله 3 رو گند نزم ! لطفا البته !
4- توی مرحله 3 ، ACM و دانشگاه می بینمتون ;)

برای همه آرزوی موفقیت می کنم

خوشبگذره
بای !

بعدا نوشت : هزار کوه گرت سد ره شوند برو / هزار ره گرت از پا در افکنند بایست ...