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

1220

سلام!

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

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

جوایز مسابقه

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

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

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

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


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

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

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

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

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

حقوق سعید

اگر 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 آن هستیم، به یک الگوریتمِ به اندازه کافی سریع نیاز داریم.

آموزش برنامه نویسی با کوئرا کالج
امین انوری سرور

اشتراک در
اطلاع از
guest

25 دیدگاه‌
قدیمی‌ترین
تازه‌ترین بیشترین واکنش
بازخورد (Feedback) های اینلاین
View all comments
فاطمه
فاطمه
1 سال قبل

هورا !!!
بالاخره آرزوی من برآورده شد! “راهنمای حل سوالات بعد از مسابقه”💪🏻💪🏻💪🏻
انشالله برآورده شدن همه آرزوها! 😅😊آمین 🙏🏻🌺

کوئرا بلاگ
ادمین
1 سال قبل
پاسخ به  فاطمه

😊☘️

فاطمه
فاطمه
1 سال قبل

با سلام
در سوال “حقوق سعید” ، من هم از فرمول گفته شده در راهنمایی استفاده کردم ولی با برخی از تست ها با خطای Time Limit Exceeded مواجه می شه و این کد منه:

n,q = map(int,input().split()) 
s = [0]+list(map(int,input().split()))
Sum = sum(s) 
for i in range(q): 
    temp = int(input()) 
    print(int(pow(2,(temp-n-1)) * Sum) % (1000000007))
آخرین ویرایش1 سال قبل توسط فاطمه
محمد زمانی خادمانلو
محمد زمانی خادمانلو
1 سال قبل
پاسخ به  فاطمه

سرعت الگوریتم شما خیلی پایین هست.
مثلا می خواهید باقیمانده 2 به توان n را بر عدد 1023 بدست بیاورید. یک راه اینه که 2 به توان n را محاسبه کنید و سپس باقیمانده بگیرید. راه دیگر این است که باقیمانده توان های مختلف 2 بر 31 را بدست بیاورید تا به الگوی مناسبی برسید. مثلا اگر بدانید 2 به توان 10 برابر 1024 می شود و باقیمانده 1024 بر 1023 برابر عدد یک هست. این کمک میکنه تا تنها باقیمانده n بر 10 را بدست بیاورید=m و سپس 2 به توان m را محاسببه کرده و باقیمانده اش را بر 1023 بدست بیاورید. البته برای این سوال راه های زیادی وجود دارد ولی من مشابه این روش استفاده کردم.

کوئرا بلاگ
ادمین
1 سال قبل
پاسخ به  فاطمه

مشکل برنامه شما از اینجاست که ابتدا ۲ بتوان k را محاسبه کرده و سپس باقی‌مانده آن را بر ۱۰۰۰،۰۰۰،۰۰۷ محاسبه می‌کنید.

با توجه به بزرگ بودن k ممکن است محاسبه مقدار اصلی این عدد خیلی زمان‌بر شود و به همین دلیل خطای time limit exceeded را دریافت می‌کنید.

برای رفع این مشکل در محاسبه توان، باید خودتان تابع توان را پیاده‌سازی کنید و در هر مرحله صرفاً باقی‌مانده را ذخیره کنید.

بدون اسم
بدون اسم
1 سال قبل
پاسخ به  فاطمه
pow(2, temp-n-1, 1000000007) * Sum % 1000000007
فاطمه
فاطمه
1 سال قبل
پاسخ به  بدون اسم

سپاس از راهنمایی شما 🌸
مشکل برطرف شد! … همیشه درگیر این جزئیات هستم!😅

محمد زمانی خادمانلو
محمد زمانی خادمانلو
1 سال قبل

سلام علیکم
امتیاز کوئرایی این مسابقه کی ثبت میشه؟

کوئرا بلاگ
ادمین
1 سال قبل

سلام دوست عزیز

این مورد پیگیری و بهتون اطلاع داده میشه

کوئرا بلاگ
ادمین
1 سال قبل

دوست کوئرایی عزیز سلام

بابت تأخیر در پاسخگویی عذر می‌خواهیم. امتیاز این مسابقه تا روز شنبه ثبت خواهد شد.

محمد زمانی خادمانلو
محمد زمانی خادمانلو
1 سال قبل
پاسخ به  کوئرا بلاگ

سلام علیکم
هنوز بعد گذشت یک هفته امتیاز کوئرایی ثبت نشده

محمد زمانی خادمانلو
محمد زمانی خادمانلو
1 سال قبل
پاسخ به  کوئرا بلاگ

سلام علیکم وقتتون بخیر
هنوز ریت مسابقه تاثیر داده نشده.

کوئرا بلاگ
ادمین
1 سال قبل

سلام دوست عزیز

بابت تاخیر پیش اومده واقعاً عذر میخوایم. الان ریتینگ مسابقات قبلی همه زده شده

علیرضا
علیرضا
1 سال قبل

سلام.سوال مسابقه رو از کجا میتونیم پیدا کنیم؟

کوئرا بلاگ
ادمین
1 سال قبل
پاسخ به  علیرضا

دوست عزیز سلام

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

محمد پارسا
محمد پارسا
1 سال قبل

سلام لطفا این مسابقه و مسابقه های الگوریتمی و تکنولوژی قبلی رو ریتش رو تاثیر بدید
با تشکر:))

کوئرا بلاگ
ادمین
1 سال قبل
پاسخ به  محمد پارسا

سلام دوست کوئرایی عزیز

خبرهای خوبی در راهه و قراره تابستون امسال تغییرات خوبی روی مسابقه‌‌های rated قبلی داشته باشیم.

محمد زمانی خادمانلو
محمد زمانی خادمانلو
1 سال قبل
پاسخ به  کوئرا بلاگ

سلام علیکم
حدودا چند روز دیگر امتیاز کوئرایی مسابقات ثبت میشه؟
دلیل وقفه بررسی تقلب های احتمالی در کد هاست؟

کوئرا بلاگ
ادمین
1 سال قبل

سلام

امتیاز این مسابقه تا روز شنبه ثبت خواهد شد.

محمد زمانی خادمانلو
محمد زمانی خادمانلو
1 سال قبل
پاسخ به  کوئرا بلاگ

سلام علیکم
ولی هنوز امتیاز این مسابقه ثبت نشده است.

سروش
سروش
1 سال قبل

سلام و عرض ادب و احترام
آیا امکان داره که کد سوال هارو ببینیم

کوئرا بلاگ
ادمین
1 سال قبل
پاسخ به  سروش

دوست عزیز سلام

متاسفانه فعلاً تصمیمی برای انتشار کد راه‌حل‌ها نداریم.

فاطمه
فاطمه
1 سال قبل
پاسخ به  سروش

فعلا مرحله “اعلام راه حل ها” بعد از کلی پیشنهاد و درخواست فعال شده! 😅 😂 😂 😂
تا مرحله “دیدن کدها” خیلی راه داریم! 😉

علیرضا
علیرضا
1 سال قبل

سوال لامپ ها بررسی نشد

کوئرا بلاگ
ادمین
1 سال قبل
پاسخ به  علیرضا

سلام

این سوال از نوع سؤالات چالشی است، یعنی لزوماً راه‌حل کاملی برای سؤال وجود ندارد؛ اما بررسی اینکه آیا راه‌حل شما درست کار می‌کند یا نه به‌راحتی امکان‌پذیر است.

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