تئوری دوم

شاززز :)

امیدوارم حال و روز خوبی داشته باشید. سری جدید سوالا آمادست و احتمالن ایده‌های حل سوالای سری قبل رو هم به انتهای این پست اضافه کنم.

سوال اول رو خیلی‌ها احتمالن دیده باشن ولی چون سوال خوبی بود تصمیم گرفتیم کسایی که ندیدنش هم ببیننش. سوال می‌گه ۹۹ تا جعبه داریم. توی هر جعبه یه تعدادی سیب هست و یه تعدادی پرتقال. ثابت کنید می‌شه ۵۰ تا از جعبه‌ها رو انتخاب کرد طوری که حداقل نصف سیب‌ها و حداقل نصف پرتقال‌ها انتخاب شده باشن.

سوال دوم هم از یکی از سوالای سایت SGU درومده و راه حل جالبی داره. سوال می‌گه که زورو و اسبش دارن با هم بازی می‌کنن. اول کار یه رشته‌ی خالی داریم. توی هر دور از بازی اسب زورو یه حرف Z یا H به انتهای رشته اضافه می‌کنه. بعدش زورو می‌تونه دو تا از حرف‌های رشته رو انتخاب کنه و جاشون رو با هم عوض کنه، می‌تونه هم تصمیم بگیره که هیچ کار نکنه. حالا زورو می‌خواد طوری بازی کنه که در پایان دور‌های فرد‌ (دور یکم، سوم، پنجم...) رشته‌ای که به وجود اومده قرینه باشه. رشته‌ی قرینه هم رشته‌ای هست که خودش و وارونش با هم برابر هستن. ثابت کنید زورو می‌تونه!

سوال سوم یکی از سوالای مورد علاقه‌ی منه. ایده‌ش مال یه سوال از Codeforces هست. امیدوارم دوستش داشته باشید. سوال می‌گه که یه آقای پستچی توی گوشه بالا سمت چپ یه جدول بزرگ هست که مختصاتاش از (۱, ۱) تا (n, n) هست. این آقا می‌خواد به n تا خونه نامه برسونه. مختصات خونه i ام (a_i, b_i) هست. ترتیب رسوندن نامه‌ها مهم نیست. هر مرحله می‌تونه یک واحد به یکی از چهار جهت اصلی بره. یه الگوریتم بدید که بتونه با تعداد O(n√n) حرکت یه مسیری رو طی کنه که از همه‌ی خونه‌ها رد بشه و به خونه‌ی اصلیش برگرده.

خوش باشید! D:

Op op op op oppa Gangnam Style!