___ سوال E : گرالت و ترول ریاضی دان ( ایده : سید مهدی سلیمان نژاد )

اول از همه باید تعداد ارقام دو تا عدد رو چک کنیم ، برای همین موقع ورودی گرفتن تعداد ارقام دوتا عدد رو محاسبه میکنیم (lp , lq)

اگه تعداد ارقام یکسان نباشن ، هرکدوم که تعداد بیشتری داره بزرگتره . اما اگه تعداد یکسانی داشته باشن باید دنبال اولین رقم از سمت چپ باشیم که تو دوتا عدد متفاوتن پس از سمت چپ شروع به پیمایش دوتا عدد میکنیم و داخل حلقه این موارد رو چک می کنیم :

- اگه مقدار رقمی یکی از اعداد بیشتر از اون یکی باشه ، اون عدد بزرگتره.

- اگه مقدارشون با هم یکی باشه دو حالت پیش میاد :

- اگه تعداد ارقام یکسانه پس نمیشه تصمیم گیری کرد و ازش رد میشیم.

- ولی اگه تعداد یکسان نباشه (فرضا [p[i] > q[i) ، به رقم بعدی تو عدد q یعنی [q[i+1 نگاه می کنیم . از اونجایی که هیچ رقم تکراری پشت سر هم تو ورودی نیست، مطمئنا این رقم یا کوچکتر یا بزرگتر از رقم [p[i خواهد بود و می تونیم اینجا به جستجومون خاتمه بدیم .

اگه حلقه تا آخر اجرا بشه و هیچ تفاوتی بین دو تا عدد پیدا نکنه پس دو تا عدد مساوین .

کد

* داخل کد برنامه یه نوع متغیر pair وجود داره که به معنی جفت هستش . این متغیر می تونه دو تا متغیر از نوع های مختلف دیگه رو داخل خودش نگه داره که به اولی با اسم first و به دومی با اسم second میشه دسترسی داشت.



___ سوال F : اژدها به تلگرام وارد می شود ( ایده : سید مهدی سلیمان نژاد )

خلاصه : WATA های داخل ورودی رو با فاصله جایگزین کنین و فاصله های اضافی رو پاک کنین ( ابتدا و انتها و فاصله های پشت سر هم ).

برای حل این سوال می تونیم از ابتدا یه متغیر کمکی h هم سایز رشته ورودی و یه عدد hi=0 رو که تعداد ارقام داخل  h رو نشون میده رو تعریف کنیم ( دقت کنین که hi هم سایز رشته رو نگه میداره و هم مثل یه اشاره گر میتونه بهمون کنه که بدونیم کجای رشته هستیم. )

از سمت چپ رشته ورودی حرکت می کنیم و هر کاراکتری که میاد رو به رشته اضافه میکنیم و hi رو یدونه اضافه می کنیم. اما بلافاصله چک میکنیم که آخرین 4  تا کاراکتر کلمه WATA رو تشکیل ندن! درصورتی که WATA درست شده باشه کافیه hi رو 4 تا کم کنیم که مثل حذف کردن WATA از رشته هستش. بعد باید کاراکتر فاصله رو به رشته اضافه کنیم ، که برای جلوگیری از تولید فاصله های اضافی ، چک میکنیم که ابتدای رشته نباشه و کاراکتر قبلی فاصله نباشه .

در انتها اگه آخر رشته فاضله باشه اون رو هم پاک می کنیم و رشته رو تا hi چاپ می کنیم .

کد


___ G : زوج های باحال ( ایده : فراز آزادی )

ابتدا به یه نکته باید توجه کنیم که اگه اعداد رو مرتب کنیم ( فعلا فرض کنید عددا غیر تکرارین ) و آرایه [a[1],a[2],…,a[n به دست بیاد ، تنها درصورتی میتونیم جواب پیدا کنیم که عدد [a[1 به عدد [a[n ضرب بشه .

چون اگه [a[1 به یه عدد مثل [a[x ضرب بشه و یه عدد  مثل  [a[y به [a[n ضرب بشه ، مطمئنا [a[n]*a[y] > a[1]*a[x خواهد بود و جوابی برای مسئله نمیتونیم پیدا کنیم .

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

کد تیم without mehdi


G++ : ( این سوال به آشنایی با ساختمان داده ها و توانایی پیاده سازی بالا نیاز داره )

تفاوت این دو سوال در اینه که G++ می تونه اعداد منفی هم داشته باشه .

اگه علامت ها رو نادیده بگیریم نکته ی گفته شده در بالا برای این سوال هم صادقه ، یعنی مطمئنا [a[1 باید در [a[n ضرب بشه . پس ما میدونیم از لحاظ رقمی ضرب اعداد جفت شدمون باید چند باشه اما از علامتش اطلاعی نداریم .

برای همین میتونیم یه بار برای |[a[1]*a[n| =ـz طو یه بار هم برای |[a[1]*a[n|- =ـz ، عملیات زیر رو انجام بدیم :

یکی از اعداد داخل ورودی که تا الان استفاده نشده رو انتخاب می کنیم مثل x و مقدار y=z/x رو به دست میاریم . حالا اگه این y وجود داشته باشه هر دوی x و y رو با هم از ورودی حذف می کنیم و اونارو با هم جفت می کنیم و در صورتی که چنین y ای وجود نداشته باشه متوجه میشیم جوابی برای مسئله با مقدار فعلی z نداریم .

فقط در صورتی که ورودی صفر داشته باشیم ، باید احتیاط کنیم و جواب رو با روش دیگه ای محاسبه کنیم چون تو محاسبه ی y=z/x برنامه بخاطر عمل تقسیم بر صفر میتونه متوقف بشه.

کد


___ سوال H : فرشید و بازی جدیدش ( ایده : محمد افتخاری )

برای این سوال ما می تونیم با 3 تا سوال “0123” ، “4567” و “8989” تمام ارقامی که تو جواب وجود دارن رو پیدا کنیم که میشن ارقامی که چراغشون سبز یا زرد میشه.

حالا که هر چهار تا عدد رو داریم میتونیم تمام حالت های ممکنه چینش این 4 رقم رو که میشه 24 حالت به دست بیاریم و تستشون کنیم، مطمئنا جواب یکی از ایناست و ما 24+3 = 27 سوال در بدترین حالت پرسیدیم.

کد 

- روش متفاوت و ساده تیم Angelo, Lola and Sherwood



H++ :

ما تو این حالت فقط 7 تا سوال میتونیم بپرسیم و هیچکدوم از روشای بالا جوابگو نیست . 

مشکل ما بعد از تشخیص رقما تو 3 تا سوال اینه که چطور مکان 4 تا عددی که میدونیم تو جواب هستن رو پیدا کنیم ؟

با فرض این که عددا a,b,c,d هستن ، اگه ما بیایم این 4 تا سوال رو بپرسیم : “abcd” ، “dabc” ، “cdab” ، “bcda” ( هر بار عدد رو یدونه شیفت چرخشی به سمت چپ میدیم ) می تونیم جای همه ی رقم ها رو تشخیص بدیم چون هر کدوم از عددا تو یکی از خونه ها یبار تست میشن . اما اگه یکی از این 4 تا جواب نباشه ما 7 تا سوالمون رو پرسیدیم و دیگه نمیتونیم جواب نهایی رو چاپ کنیم! برای این که مشکل رو حل کنیم کافیه به رقمایی که چراغ سبز میگیرن دست نزنیم و بقیه رو شیفت بدیم ، اینطوری به ازای هر چراغ سبزی که میگیریم یکی از رقما کمتر میشن و مطمئنا تو 4 تا سوال جواب رو پیدا می کنیم . جزئیات رو توضیح نمیدم که خودتون روش فکر کنین :)

کد روش توضیح داده شده  و  بقیه ی کدها




____ I : لک لک های آبی و صورتی + نیلیا ( ایده : محمد افتخاری ) ( این سوال به آشنایی با ساختمان داده و الگوریتم و توانایی پیاده سازی بالا نیاز دارد )
مسئله ی مهم برای حل این سوال اینه که در هر لحظه که دستور food داده میشه کدوم غذا رو برای خوردن انتخاب کنیم ؟ میشه اثبات کرد که جواب به طور حریصانه ، انتخاب دورترین غذایی هستش که آبی زمان کافی برای رفت و برگشتش رو داشته باشه .
پس ما نیاز داریم تو هر لحظه بدونیم دورترین غذایی که آبی میتونه بیاره کدومه. چون مشکی ها در حال تغییر مکان هستن غذاهای در دسترس ثابت نیستن .پس برای حل مسئله ما نیاز به درخت های جستجو داریم یکی برای غذاها و یکی برای مشکی ها که کلیدشون فاصله ی غذاها یا مشکی ها هستش.

به ازای هر query :

- Food : مطمئنا نزدیکترین مشکی زودتر از بقیه به صورتی و بچه ها میرسه پس فاصله نزدیکترین مشکی رو پیدا می کنیم و دورترین غذایی که فاصله ی رفت و برگشتش کمتر از زمان رسیدن این مشکی هست رو انتخاب می کنیم و از درخت حذفش می کنیم . در صورتی که هیچ غذایی پیدا نشه زمان رفتن هستش .

- Move : براساس فاصله ی مشکی که میخواد کوچ کنه ، داخل درخت مشکی ها جستجو می زنیم و حذفش می کنیم و یه عضو جدید با فاصله ی جدید به درخت اضافه می کنیم و اطلاعات مشکی مورد نظر رو آپدیت می کنیم .