مسابقه الگوریتمی شماره ۳۹ + راه‌حل‌ها

سلام!

این مسابقه ۳۹امین مسابقه الگوریتمی کوئرا از ابتدا تاکنون است و حل سوالات آن روی امتیاز کوئرایی شما تأثیر دارد. مسابقه شامل ۶ یا ۷ سوال است که چالش این سوالات، توانایی حل مسئله الگوریتمی است. حل سوالات نیازمند تکنولوژی خاصی نیست و با هر زبانی که دوست دارید، می‌توانید کد بزنید. ترتیب سوالات تقریبا از ساده به سخت است، اما پیشنهاد می‌کنیم همه سوالات را بخوانید و برای حل کردن آن‌ها وقت بگذارید.

زمان برگزاری مسابقه، پنج‌شنبه ۱ اردیبهشت ساعت ۱۶:۰۵ دقیقه است و شما ۲ ساعت ۳۰ دقیقه زمان دارید تا به سوالات پاسخ دهید.

جوایز مسابقه

• پنج نفر اول: یک تیشرت کوئرایی
• به پنج نفر از نفرات برتر: به قید قرعه یک تیشرت کوئرایی

ثبت‌نام در مسابقه

برای ثبت‌نام و کسب اطلاعات بیشتر در مورد مسابقه به صفحه مسابقه الگوریتمی شماره ۳۹ مراجعه کنید. توجه کنید که تا تاریخ ۱۴۰۱٫۰۲٫۰۱ فرصت دارید تا ثبت‌نام خود را کامل کنید.

منتظرتون هستیم 🙂

پی‌نوشت: راه‌حل‌ها

امیدواریم که از مسابقه الگوریتمی شماره ۳۹ لذت برده باشید. در ادامه راه‌حل‌های سؤالات مسابقه توضیح داده شده‌اند.

در صورتی که متوجه راه‌حلی نشدید، می‌توانید در بخش نظرات سؤالات و ابهام‌های خود را مطرح کنید. همچنین اگر راه‌حل دیگری برای سؤالات دارید، خوشحال می‌شویم که راه‌حل خود را در بخش نظرات با ما و دوستانتان به اشتراک بگذارید.

سیبل تیراندازی

کافی است سه حالت خواسته‌شده را پیاده‌سازی کنید.

حقوق سعید

اگر sum را مجموع حقوق این کارمند در n ماه اول در نظر بگیریم. یعنی:

sum=a_{1}+a_{2}+ ...+a_{n}

می‌توان نشان داد که حقوق این شخص در ماه kام (n+1 \leq k) برابر است با:

2^{k-n-1}\times sum

انتساب آرایه

اگر عددی در دنباله b باشد که در دنباله a نداشته باشیم، رسیدن به این هدف ممکن نیست. (چون عملیات انتساب مجموعه اعداد دنباله a را گسترش نمی‌دهد.)

پس تنها حالت‌هایی باقی‌مانده که مجموعه اعداد موجود در دنباله b زیرمجموعه اعداد موجود در دنباله a است.

اگر همه اعداد دنباله b متمایز باشند، دنباله a از همان ابتدا برابر b باشد. (چون انجام دادن هر عملیاتی باعث ایجاد شدن عدد تکراری می‌شود.)

پس حالت‌هایی باقی‌مانده که در دنباله b یک عدد حداقل ۲ بار ظاهر شده است. اکنون می‌خواهیم نشان دهیم همواره می‌توان در این حالات از a به b رسید.

حالت اول: در دنباله a عددی وجود دارد که در دنباله b نیامده است. در این حالت می‌توانیم از جایگاه این عدد مثل متغیر کمکی استفاده کنیم و دنباله b را کاملاً بسازیم و در نهایت مقدار مطلوب را در این خانه قرار دهیم.

حالت دوم: در دنباله a عددی وجود دارد که دو بار ظاهر شده است. در این حالت می‌توان یکی از این اعداد را به صورت متغیر کمکی در نظر گرفت و دست به کپی دیگر آن نزنیم و جای دو متغیر دیگر را تغییر دهیم. به این ترتیب می‌توانیم هر جایگشتی را درست کنیم و یا تعداد تکرارهای یک عدد در دنباله را زیاد و کم کنیم.

عددگذاری گراف

می‌توان با بررسی یک رأس به این نتیجه رسید که اگر درجه یک رأس بیش از ۲ باشد، انجام این کار شدنی نیست.

پس اگر در گراف داده‌شده درجه همه رأس‌ها حداکثر ۲ باشد؛ مولفه‌های این گراف تعدادی مسیر هستند.

اگر یک مسیر به طول l داشته باشیم، این عدد‌گذاری روی این مسیر باید یک دنباله متوالی از اعداد صحیح باشد. (چه صعودی، چه نزولی)

• اگر k کمتر از l باشد، نمی‌توان چنین عدد‌گذاری انجام داد.
• اگر k بیشتر یا مساوی l باشد و l بزرگ‌تر از ۱ باشد، این عددگذاری به 2(k+1-l) روش ممکن خواهد بود.
• اگر l برابر ۱ باشد، این عددگذاری به k روش ممکن است.

توجه کنید اگر عددگذاری برای هر مؤلفه همبندی را محاسبه کنیم، پاسخ کلی مسئله بنابر اصل ضرب، برابر ضرب تعداد حالت‌های این مؤلفه‌ها خواهد بود.

دنباله دلخواه

این سؤال می‌تواند راه‌حل‌های مختلفی داشته باشد که همگی درست هستند. اما یک راه‌حل قابل‌قبول به این صورت است.

فرض کنید تا الان عدد ۲ تا k را نوشته‌ایم ولی k+1 را ننوشته‌ایم. اکنون می‌خواهیم عدد k+1 را اضافه کنیم. برای این کار یک مضرب مشترک از k و k+1 را در نظر می‌گیریم که تا الان در دنباله نیامده است.

این عدد را l بنامیم. بعد از k (که در مرحله قبل نوشتیم) عدد l و سپس عدد k+1 را قرار می‌دهیم. با توجه به نحوه انتخاب l می‌دانیم هر دو عدد مجاور نسبت به هم اول نیستند.

با ادامه دادن این روند همه اعداد از ۲ تا n در دنباله ظاهر می‌شوند و طول دنباله از 2n بیشتر نمی‌شود؛ اما ممکن است کمتر شود. برای اینکه طول دنباله را دقیقاً برابر 2n کنیم، کافی است مضارب عدد آخر که در دنباله ظاهر نشده‌اند را به انتهای آن اضافه کنیم.

می‌توان تحقیق کرد که روش فوق برای nهای کمتر یا مساوی ۱۰،۰۰۰ هیچوقت عددی بیشتر یا مساوی ۱۰۰۰،۰۰۰،۰۰۰ در دنباله قرار نمی‌دهد. پس روش فوق قابل‌قبول است.

دنباله غریب

می‌توان ثابت کرد که همواره:

n^{2}+1 \leq f_{n} \leq n^{2}+n

همچنین با توجه به نامساوی بالا می‌توان برای اعداد اول مثل p نشان داد که:

f_{p}=p^{2}+1

پس برای محاسبه f_{n}​ کافی است روند بازگشت را تا مرحله‌ای به عقب برگردیم که به یک عدد اول برسیم و جواب را از روی آن پیدا کنیم.

به این نکته توجه کنید که از هر عدد مثل n اگر تقریباً log(n) عدد به عقب برگردیم، حتماً یک عدد اول می‌بینیم.

همچنین برای بررسی اول بودن nی که به دنبال پیدا کردن f آن هستیم، به یک الگوریتمِ به اندازه کافی سریع نیاز داریم.