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

507

سلام!

خب بدون مقدمه بریم سراغ توضیحات مسابقه الگوریتمی شماره ۴۱. این مسابقه شامل تعدادی سؤال الگوریتمی هست که قراره توانایی حل مسئله‌ی شما رو به چالش بکشن. حل سؤالات به تکنولوژی خاصی نیاز نداره و با هر زبانی که دوست داشته باشید، می‌تونید کد بزنید. ترتیب سؤالات تقریباً از ساده به سخت هست، اما پیشنهاد می‌کنیم همه سؤالات رو بخونید و سعی کنید حلشون کنید.

نکات مهم

  • حل سؤالات این مسابقه بر روی امتیاز کوئرایی شما تاثیر داره.
  • زمان برگزاری مسابقه، سه‌شنبه ۲۷ اردیبهشت ساعت ۲۰:۰۵ دقیقه هست و شما ۲ ساعت زمان دارید تا به سؤالات پاسخ بدید.

ثبت‌نام این مسابقه در صفحه مسابقه الگوریتمی شماره ۴۱ انجام می‌شه. دقت کنید که برای ثبت‌نام فقط تا ۲۷ام اردیبهشت فرصت دارید.

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


پی‌نوشت: راه‌حل‌های مسابقه

کیک‌ها در کوئرا

می‌توان با بررسی هر ۱۲ حالت مسئله به این نتیجه رسید که اگر n مقسوم‌علیه ۱۲ باشد، انجام این‌کار شدنی است.

پیچیدگی زمانی: O(1)

رشته در کوئرا

اگر مجموع ارقام n را با d(n) نشان‌دهیم، برای حساب کردن مجموع ارقام s_n می‌توان رابطه بازگشتی بر اساس تعریف s_nها به این صورت نوشت:

f(1) = 1 
f(n) = 2f(n - 1) + d(n) 

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

پیچیدگی زمانی: O(n)

نامه‌ها در کوئرا

می‌خواهیم ثابت کنیم شرط لازم و کافی شکست مهدی این است که تعداد نامه‌های به یک شرکت بیش از \frac{n}{2} باشد.

طرف اول. فرض کنید تعداد نامه‌های به یک شرکت خاص بیش از \frac{n}{2} باشد، در این صورت برای اینکه هیچ نامه‌ای در پاکت خود قرار نگیرد باید بیش از \frac{n}{2} پاکت‌نامه با آدرسی غیر از این شرکت داشته باشیم ولی تعداد پاکت‌های با این ویژگی کمتر از \frac{n}{2} است.

طرف دوم. حال می‌خواهیم بگوییم که اگر هیچ شرکتی بیش از نصف نامه‌ها را به خود اختصاص ندهد،‌ مهدی می‌تواند کار خود را انجام دهد. فرض کنید k بیشترین تعداد نامه‌ای باشد که یک شرکت به خود اختصاص می‌دهد. حال نامه‌ها را به ترتیبی قرار دهید که نامه‌های یک شرکت همگی کنار هم باشند، سپس پاکت‌ها را نیز به همان ترتیب ولی k واحد به راست شیفت دهید. می‌توان با توجه به اینکه k\leq\frac{n}{2} است، نشان داد که این روش باعث می‌شود هیچ‌ نامه‌ای در پاکت خود قرار نگیرد.

پیچیدگی زمانی: O(n + m)

شیفت در کوئرا

فرض کنید رشته s طول n داشته باشد. رشته‌ای به طول 2n می‌سازیم که از دو بار قرار دادن s کنار هم به دست می‌آید. این رشته را t بنامید. هر زیر‌رشته به طول n در t یک شیفت از s است. حال نیاز داریم که این n شیفت را با هم مقایسه الفبایی کنیم. برای مقایسه کردن شیفت i و j کافی است یک بار آرایه درهم‌ساز (hash) را برای رشته t بسازیم. حال با جست‌و‌جوی دودویی اولین تفاوت این دو شیفت را پیدا کرده و مقایسه‌ای از مرتبه O(log(n)) بین دو شیفت انجام می‌دهیم.

پیچیدگی زمانی: O(nlog(n))

پرانتزگذاری در کوئرا

می‌توان با استفاده از روش انعکاس ثابت کرد که تعداد حالت‌های مطلوب برابر است با:‌

C(2n, n) - C(2n, n - k - 1)

حال نیاز داریم که انتخاب r شیء از n شیء را برای همه اعداد کمتر یا مساوی ۱۰۰۰,۰۰۰ محاسبه کنیم که انجام اینکار با محاسبه k! و وارون آن به پیمانه 10^9+7 به‌ازای هر k از ۱ تا ۱۰۰۰,۰۰۰ شدنی است.

پیچیدگی زمانی: O(q + max(n).log(10^9 + 7))

امین انوری سرور

ممکن است علاقه‌مند باشید
مصورسازی تعاملی با پلاتلی (Plotly)
الگوی طراحی Factory
خاصیت Float در CSS
اشتراک در
اطلاع از
guest
2 دیدگاه‌
قدیمی‌ترین
تازه‌ترین بیشترین واکنش
بازخورد (Feedback) های اینلاین
View all comments
فاطمه
فاطمه
3 روز قبل

با سلام
ممنون بابت به اشتراک گذاری راه حلها، سوال دوم و سوم رو به شیوه گفته شده حل کردم ولی امتیاز کامل رو نگرفتم!🤔🤨

فاطمه
فاطمه
2 روز قبل

با سلام
برای سوال “رشته در کوئرا” سه کد زیر رو نوشتم ولی هر کدوم اشکالاتی دارن و نتونستم امتیاز کامل رو بگیرم، کسی از دوستان میتونه راهنمایی کنه؟ ممنون
روش 1 : پیاده سازی سوال

num = int(input())
s1 = "1"
for i in range(2,num+1):
    s1 = s1+str(i)+s1

print(sum([int(item) for item in (s1)]) % 1000000007)

روش 2: با توجه به این الگو
n*pow(2,0) , pow(2,1)*(n-1) , (n-2)*pow(2,2), …….

num = int(input())
Sum ,j = 0 , 0
for i in range(num,0,-1):
    Sum +=i * pow(2,j,1000000007)
    #print("i:",i,"j:",j,"pow:",pow(2,j,1000000007))
    j += 1
    #print("i:",i"j:",j,"pow:",pow(2,j,1000000007))
    
print(Sum%1000000007)

روش 3 : بازگشتی

num = int(input())
s1 = "1"
for i in range(2,num+1):
    s1 = s1+str(i)+s1

print(sum([int(item) for item in (s1)]) % 1000000007)