راه‌حل‌های مسابقه انتخابی ۴ کدکاپ ۸

سلام دوست کوئرایی!

در این مطلب، به راه‌حل‌های سوالات مسابقه انتخابی ۲ کدکاپ ۸ می‌پردازیم. اگر در این مسابقه شرکت کرده‌ای و سوال یا ابهامی درباره پاسخ سوالات داری، این بلاگ پست برای شماست.

راه‌حل برنده‌ی والیبال

از آن‌جایی که داده‌ها درست هستند. همیشه برنده‌ی بازی تیمی است که آخرین امتیاز را کسب کرده باشد. پس کافی است از روی آخرین کاراکتر رشته‌ها، برنده را مشخص کنیم.

راه‌حل بازگشت ابدی

اگر چند جمله‌ی اول دنباله را بنویسیم، متوجه این الگو می‌شویم که بعد از جمله‌ی اول، یک تناوب ۴ تایی دارد.

راه‌حل عدالت شکلاتی

همواره برش کیک موازی محور yz است. پس در واقع پاسخ ما یک افراز برای بازه‌ی [0, a] از محور xها را تشکیل می‌دهد. اگر برای هر واحد صحیح مثل [i, i+1] که 0 \leq i \leq a - 1 مجموع حجم شکلات‌هایی که در این بازه قرار می‌گیرند را حساب کنیم، مسئله به یک بعد کاهش پیدا می‌کند. حجم شکلات هر شخص را می‌توان از قبل مشخص کرد. حال کافی است از چپ به راست حرکت کنیم و سهم هر شخص را مشخص کنیم.

راه‌حل مثلث گمشده

نقشه را به این صورت بسازید. بین هر دو شهر یک جاده قرار دهید به جز جفت شهرهایی که باهم در یک مثلث نیامده‌اند. این نقشه k شرط مربوط به مثلث نداشتن را دارد. (چون بین آن‌ها یال نیست.) اما کافی است بررسی کنیم آیا بین m جفت اول مثلث هست یا نه. اگر برای همه این جفت‌ها حداقل یک مثلث وجود داشت، پاسخ مسئله بله است. اما اگر وجود نداشت هیچ گرافی پیدا نمی‌شود که همه‌ی این شرط‌ها را برآورده کند. برای بررسی کردن وجود مثلث بین دو راس می‌توانیم سطرهای ماتریس مجاورت گراف متناظر را در bitset ذخیره کنیم و سپس با تقریباً \frac{n}{64} عملیات تعداد مثلث‌ها را بشماریم.

راه‌حل اندازه‌گیری کوه

می‌توانیم روی مقدار k جست‌وجوی دودویی انجام بدهیم. به این ترتیب کافی است چک کنیم آیا می‌توانیم دنباله‌ی مطلوبی با حداکثر k تغییر بسازیم یا خیر. برای این کار برای هر i سعی می‌کنیم دنباله‌ی h_1, h_2, \dots, h_i را صعودی کنیم به طوری که هر عدد حداکثر k واحد تغییر کند. شدنی بودن این کار را می‌توانیم با استفاده از برنامه‌نویسی پویا و حریصانه انجام دهیم.

سپس همین‌کار را برای دنباله‌ی h_{i+1}, \dots, h_n انجام می‌دهیم ولی این بار سعی می‌کنیم دنباله را نزولی کنیم. با استفاده از پاسخ‌ها برای این دو دنباله با پیمایش کردن برای مقدار میانی کوه می‌توانیم شدنی بودن این راه را بررسی کنیم.

راه‌حل چنگک

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

جمع‌بندی

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

باتشکر از «ارشیا سلطانی موخر»، «امین انوری»، «رومینا سحری مقدم» و «علی شفیعی» برای طراحی و تست سوالات کدکاپ ۸ مرحله‌ی انتخابی ۴.