خانه توسعه‌دهنده با کوئرا | توسعه‌دهنده مسابقات و رویدادها مسابقه الگوریتمی شماره ۴۱ + راه‌حل‌ها

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

۲۴ اردیبهشت ۱۴۰۱

زمان مطالعه: 2 دقیقه

1459

سلام!

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

نکات مهم

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

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

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

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

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

می‌توان با بررسی هر ۱۲ حالت مسئله به این نتیجه رسید که اگر $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))$

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

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

ممکن است علاقه‌مند باشید

۶ ابزار حذف نویز صدا با هوش مصنوعی برای ادیت بی‌دردسر فایل‌ها

شایان ضیایی

2 هفته پیش

یک گام به جلو در مسیر آموزش ؛ نسخه جدید سامانه آموزشی کوئرا منتشر شد!

reyhaneh karami

3 هفته پیش

با بهترین ابزارهای هوش مصنوعی برای برنامه نویسی آشنا شوید

شایان ضیایی

1 ماه پیش

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)

first_input = input() n = int(first_input.split()[0]) m = int(first_input.split()[1]) secend_input = input() l = list(map(int, secend_input.split())) # def main(n, m, l): # first main func # while m: # if n/2 < l.count(m): # return 'NO' # m -= 1 # return 'YES' def main(n, m, l): # secend main func ( more optimal ) most_frequent = max(set(l), key = l.count) most_frequent_count = l.count(most_frequent) if most_frequent_count > n/2: return 'NO' return 'YES' print(main(n, m, l))

اشتراک در

15 دیدگاه‌

قدیمی‌ترین

تازه‌ترین بیشترین واکنش

بازخورد (Feedback) های اینلاین

View all comments

فاطمه

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), …….

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

نویسنده

پاسخ به فاطمه

سلام
وقتتون بخیر
ممنون از اینکه راه‌حل‌هاتون رو با ما به اشتراک گذاشتید!

مشکل روش اول و سوم (که فکر کنم فرقی هم ندارن) اینه که خود رشته s_n رو می‌سازه. می‌توانید با استقرای ریاضی ثابت کنید طول رشته s_n دقیقا برابر 2 بتوان n منهای یک است. پس ساختن این رشته برای مقدارهای بزرگ زمان‌بر (حتی حافظه‌بر!) هست.

ولی توی روش گفته شده رد سوال فقط مجموع ارقام s_{n-1} رو در ۲ ضرب می‌کنیم اینطوری حداکثر O(n) عملیات انجام می‌دیم. (به طور خلاصه به جای ذخیره خود رشته، مجموع ارقام رشته رو به پیمانه ذخیره می‌کنیم.)

اما مشکل راه حل دوم که مشکل اساسی هست اینه که باید مجموع ارقام رو ذخیره کنید. (و این توی سوال بلد شده) یعنی اگر مثلا عدد ۱۳ رو داریم باید جمع ارقامش که ۴ هست رو اضافه کنید نه خود ۱۳. پس می‌تونید در نظر بگیرید که عدد i چند بار اومده و به‌جای ضرب کردن خود i، جمع ارقام i رو ضرب کنید.

فکر کنم با این تغییر مشکل برنامه شما برطرف خواهد شد. اگر بازهم موردی توی حرفام درست نبود و یا سوالی بود، خوشحال می‌شیم که با ما در میان بگذارید!

محمد عقیل

سلام اردر راهی که برا سوال ۴ دادید nlog^2n هست!

پاسخ به محمد عقیل

توجه کنید اگر توان‌های base به پیمانه mod در روش درهم‌سازی را پیش‌پردازش کنید و در یک آرایه ذخیره کنید؛ برابری دو زیر رشته را می‌توانید از مرتبه O(1) بررسی کنید، پس برای جست‌وجوی دودویی O(log(n)) نیاز دارید و چون برای هر کدام از n شیفت این کار را انجام می‌دهیم در کل مرتبه زمانی از O(nlog(n)) خواهد بود.

سجاد

سلام
من سوال 3 (نامه‌ها در کوئرا) را با این کد حل کردم امتیاز 91 گرفتم و برای چنتا تست اخر ارور time limit میگیرم به نظرتون مشکل از کندی زبان پایتون هستش یا این کد هنوز میتونه بهینه تر باشه ؟

پاسخ به سجاد

اگر درست متوجه شده باشم، در برنامه شمابرای شمارش تعداد تکرارهای هر عدد، ممکن است روی کل آرایه پیمایش کنید و برنامه شما از ‌O(nm) طول بکشد. به همین دلیل ممکن است برنامه شما با خطا مواجه شود، مستقل از این مشکل، اگر با کامپایلر pypy3 به جای python3 ارسال کنید، برنامه شما سریع‌تر اجرا می‌شود.

محمد زمانی خادمانلو

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

پاسخ به محمد زمانی خادمانلو

سلام
وقتتون بخیر
برای محاسبه کردن معکوس عدد a به‌ پیمانه یک عدد اول مثل p، کافی است با توجه به قضیه فرما a بتوان p – 2 را به پیمانه p حساب کنید تا معکوس a به پیمانه p محاسبه شود. به همین ترتیب می‌توانید معکوس هر عدد را از مرتبه O(log(p)) حساب کنید.

پاسخ به امین انوری سرور

پس عدد a را هر بار در خودش ضرب کنم p-2 مرتبه و باقیمانده را ذخیره کنم؟

بله درسته، البته نباید این کار را از O(p) انجام دهید، بلکه با روش‌های محاسبه بازگشتی، این مقدار را از O(log(p)) محاسبه کنید.

دلیل درست بودن این رابطه «قضیه فرما» است که می‌گوید، برای هر a که عامل p ندارد؛ باقی‌مانده a بتوان p – 1 به p، با 1 است.

امین

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

پاسخ به امین

سلام، وقتتون بخیر!
پیشنهاد می‌کنم برای آشنایی با این مبحث، از کتاب «ترکیبیات» علیرضا علیپور، انتشارات فاطمی استفاده کنید. همچنین با جستوجو کردن عدد کاتالان و قضیه انعکاس مطالب مفیدی مثل این پیوند می‌توانید پیدا کنید.

امیررضا سلطانی

1 سال قبل

با سلام. من سوال رشته ها در کوئرا رو حل کردم ولی متاسفانه 96 از 100 می گیرم.
مشکل چیه؟

کد من این هست:

n = int(input())


def s(n):
    if n == 1:
        return 1
    return 2 * s(n-1) + n // 10 + n % 10


print(s(n) % (10 ** 9 + 7))

nasim

سلام. من خود صورت سوال پرانتزگذاری رو متوجه نمیشم. امکانش هست روی یکی از مثال های خروجی توضیح بدین؟