مقدمه

به‌ نام خدا، سلام!

مسیر یادگیری در کوئرا کالج

آنچه خواهید دید!

توضیحاتی در مورد شبه‌کدها

طرح درس، گواهی و  امتیازات

بزن بریم!

۱. ورود به دنیای الگوریتم‌ها

اهداف فصل

خصوصیات الگوریتم

الگوریتم چیست

مراحل حل مسئله

مقایسه الگوریتم‌ها

زمان اجرای برنامه

شمارش عملیات‌ها

جست‌وجو در دنباله ۱

جست‌وجو در دنباله ۲

تبدیل به حسابی ۱

میانه صحیح

تبدیل به حسابی ۲

۲. تحلیل زمانی الگوریتم‌ها

عدم اهمیت ضریب‌ها

تعریفِ ابتداییِ اردر

چند مثال از اردر

مقایسه اردر‌ها

بزرگ‌ترین زیربازه ۱

بزرگ‌ترین زیربازه ۲

نیمه مرتب

شمارش مثلث‌ها ۱

شمارش مثلث‌ها ۲

شمارش مثلث‌ها ۳

مرتب‌سازی و تحلیل زمانی

مرتب‌سازی حبابی

۳. الگوریتم‌های استقرایی

استقرای ریاضی

استقرای قوی

مرتب‌سازی انتخابی

مرتب‌سازی درجی

بزرگ‌ترین زیربازه ۳

الگوریتم هورنر

مجموع ارقام

۴. الگوریتم‌های بازگشتی

آشنایی اولیه

چند مثال ساده

پشته فراخوانی

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

مثال‌های تحلیل توابع بازگشتی

دنباله بازگشتی

فرکتال

ب.م.م

برج هانوی

کد گرِی

𝑛تایی مرتب

تناظر زیر مجموعه‌ها با اعداد دودویی

بخش‌بندی

۵. الگوریتم‌های حریصانه

خریدن کتاب

زندگی کارمندی

پمپ بنزین

کاف‌کیک

انرژی خور

تخته

بیشترین تعداد بازه

اشتباهات رایج

آبمیوه فروشی حریصانه

جاسوسی

تمرین‌های دوره‌ای ۱

استارت-آپ باکلاس

پله‌نوردی

علسوپا

پالیندرومینیا

ضرب متناظر دو دنباله

بسته‌های شکر

تعمیر پشت‌بام

شرکت پالایش و پخش نخود در برره

مساوات

۶. برنامه‌نویسی پویا

دومینوار

بزرگترین زیر‌بازه

آجرچینی

بزرگترین زیر جدول

انتخاب

بیشینه مسیر جدول

چالش مسیر‌یابی

مسئله‌ی کوله پشتی

یا همه یا هیچ یا یکی

بهینه‌سازی حافظه کوله پشتی

بزرگ‌ترین زیردنباله مشترک

ضرب ماتریس

بزرگ‌ترین زیردنباله اکیدا صعودی

بریم توچال!

۷. الگوریتم‌های پس‌گرد

مسائل پس‌گرد

تعداد جایگشت

دنباله‌ پس‌گردنی

سودوکو

𝑛 وزیر

یک اسب

۸. روش تقسیم‌ و حل

ادغامات

محاسبهٔ توان

تابع توان‌دار

قلّه

جستجوی دودویی

بشمر!

نابه‌جایی

مرتب‌سازی سریع

pivot کجاست؟

دسته به دسته

تمرین‌های دوره‌ای ۲

مرد مالیاتچی و جاعل

تعداد ۱۱ بخش پذیرها (۲)

مثلث‌ها

خواب پوپک

باقر حال نداره ولی پول داره

تکامل

انتقام از TA‌ سخت‌گیر

رژیم سخت

دنباله تورج‌پسند

سینما، سینما

بازرگانی سوکرات و پسران

شیر

متوازی‌الاضلاع ممنوع!

آجر چینی (۲)

بازار موبایل

منظره‌ای به‌ یاد ماندنی

۹. ساختمان‌داده‌ها

پشته

پرانتز‌گذاری معتبر

هیستوری

صف

الگوی من کیه؟

صف دو‌طرفه

آرایه پویا

لیست پیوندی

پیاده‌سازی ساختمان‌داده‌های قبلی با لیست پیوندی

ویرایشگر متن

درخت هرمی

کافه‌ سالاد

میانه‌روی

درخت دودویی جستجو و ساختار مجموعه‌ای

برنامه‌ریزی فرودگاه

برش کیک

پول یا وجدان؟

۱۰. پیش‌پردازش و بهینه‌سازی

مجموع جزئی

خواستار

مجموع جزئی در ماتریس

مربع

کادوی مشتی

درخواست مینیمم عدد در بازه

کمینه در بازه

مرتب‌سازی درجی رشته‌ها

مجموع جزئی در آرایه متغَیّر

بیشینه در آرایه متغیّر

۱۱. الگوریتم‌های گراف

گراف

دی‌اِف‌اِسِ پیش‌گو

بی‌اِف‌اِسِ مسیر‌یاب

پیدا کردن دور در گراف‌ها

گراف‌های دوبخشی

پیدا کردن کمر گراف

مسافرت

پادشاه

دوست‌یابی

جدول

قطـــر

تمرین‌های دوره‌ای ۳

وسیله کمک آموزشی

زینی

بتایپ

قطار کامیابی

هیچ‌وقت مغرور نشو!

دنباله متوازن

مرتفع

گراف قرمز و آبی

ترور

میان‌ترم هندسه

اسم فامیل

صفا

مساحت محصور

عدد روی تخته

دنباله

کمینه بیشینه اختلاف!

ضمیمه

منابع خوب

نکاتی درباره باقی‌مانده و سرریز کردن (Overflow)

تحلیل الگوریتم‌ها

پیاده‌سازی ساختمان‌‌داده‌ها بخش اول

پیاده‌سازی ساختمان‌‌داده‌ها بخش دوم

مرتب‌سازی در زبان ++C

استفاده از pair در ++C

ساختمان‌های داده در ++C

کتابخانه‌ها و توابع پرکاربرد ++C

روش‌های دیگر خواندن ورودی در ++C

پرکابردهای پایتون بخش اول

پرکابردهای پایتون بخش دوم

| سطح این سوال نسبت به سوالات قبل بالاتر است و به‌ منظور آشنایی بیشتر شما با تاثیر طراحی الگوریتم‌های مناسب در بهینه کردن راه‌حل‌ها قرار داده شده است. درصورت ابهام می‌توانید از راهنمایی‌ها استفاده کنید و یا در قسمت سوالات خصوصی مشکلاتتان را مطرح کنید. |
|:-:|

+ محدودیت زمان: ۲ ثانیه
+ محدودیت حافظه: ۶۴ مگابایت

----------

یک دنباله شامل $n$ عدد صحیح مثل $a_1, a_2, \dots, a_n \,$ داریم. 

در هر عملیات می‌توانیم یک عضو دلخواه از این دنباله را **یک واحد کاهش یا افزایش** دهیم. به عبارت دیگر در یک عملیات می‌توانیم یک $i$ از $1$ تا $n$ انتخاب کنیم و عدد $i$ام دنباله یا همان $a_i$ را به $a_i + 1$ یا $a_i - 1$ تغییر دهیم.

می‌خواهیم با کمترین تعداد عملیات **همه اعداد این دنباله را برابر** کنیم، مقدار نهایی دنباله و کمینه تعداد عملیات را بیابید. به عبارت دیگر می‌خواهیم عددی صحیح مانند $M$ پیدا کنیم به طوری که عبارت زیر کمینه شود.
$$\sum_{i = 1}^{n} |a_i - M|$$

به هر $M$ که این خاصیت را داشته باشد **میانه** دنباله $a_1, a_2, \dots, a_n \,$ می‌گویند.
# ورودی
در سطر اول ورودی عدد صحیح و مثبت $n$ که نشان‌دهنده‌ی طول دنباله است داده می‌شود.
$$1 \leq n \leq 100 \ 000$$
در سطر دوم ورودی $n$ عدد صحیح مثل $a_1, a_2, \dots, a_n \,$ که با فاصله از هم جدا شده‌اند داده می‌شود.
$$1 \leq a_i \leq 10^9$$
# خروجی
در تنها سطر خروجی دو عدد صحیح که با یک فاصله از هم جداشده‌اند که عدد اول نشان‌دهنده‌ی $M$ و عدد دوم نشان‌دهنده‌ی تعداد عملیات‌های لازم است ($f(M)$) را چاپ کنید.

اگر چند $M$ وجود دارد که تعداد عملیات‌های آن کمینه است، **کوچک‌ترین** آن‌ها را چاپ کنید.

# مثال
## ورودی نمونه ۱
```
2
3 7
```

## خروجی نمونه ۱
```
3 4
```

## ورودی نمونه ۲
```
5
1 2 3 4 5
```

## خروجی نمونه ۲
```
3 6
```

<details class="blue"> 

<summary>

%align_center_start%

# برای دیدن **«راه‌حل»** کلیک کنید.
لطفاً قبل از دیدن راه‌حل مسئله روی سوال بین ۱۵ تا ۳۰ دقیقه فکر کنید!

%align_end%

</summary>

----------

### گام اول

اگر مقدار $M$ مشخص باشد تعداد عملیات‌های لازم برای اینکه همه اعداد دنباله را برابر $M$ کنیم مشخص است. چون هزینه کمترین عملیاتی که برای رسیدن $a_i$ به $M$ نیاز داریم برابر $|M - a_i|$ است؛ بنابراین کمینه تعداد کل عملیات‌ها برابر است با:

$$
\sum_{i = 1}^{n} |a_i - M|
$$

پس می‌توانیم کمینه تعداد عملیات لازم تا رساندن هر عدد به $M$ را با $f(M)$ نشان دهیم.

حال مسئله‌ای که باقی می‌ماند این است که «کدام $M$ مناسب است؟».

### گام دوم

فرض کنید $M^\ast$ همان عددی باشد که برای کمینه کردن تعداد عملیات‌ها مناسب است. (اگر چند عدد این خاصیت را دارند یکی را به دلخواه در نظر بگیرید.)

فرض کنید در دنباله $a_1,a_2,\dots,a_n$، $l$ عدد از $M^{\ast}$ کوچک‌تر، $g$ عدد از $M^{\ast}$ بزرگ‌تر و $n-g-l$ عدد برابر $M^{\ast}$ باشند.

### گام سوم

حال می‌خواهیم $f(M^\ast + 1)$ را برحسب $f(M^\ast)$ حساب کنیم. (یعنی بررسی کنیم اگر یک واحد $M^\ast$ افزایش یابد، تعداد عملیات‌ها چقدر تغییر می‌کند.)

$$f(M^\ast + 1) = f(M^\ast) + l - g + (n - g - l) = f(M^\ast) + n - 2g$$

+ اعدادی که مساوی $(n - g - l)$ و یا کوچک‌تر $(l)$ از $M^\ast$ بودند، با افزایش یک واحدی $M^\ast$ نیاز به یک عملیات بیشتر دارند.
+ اعدادی که بزرگ‌تر $(g)$ از $M^\ast$ بودند، با افزایش یک واحدی $M^\ast$ نیاز به یک عملیات کمتر دارند.

به طور مشابه می‌توانیم همین کار را برای $f(M^\ast - 1)$ انجام دهیم. یعنی داریم:
$$f(M^\ast - 1) = f(M^\ast) + g - l + (n - g - l) = f(M^\ast) + n - 2l$$

+ اعدادی که مساوی $(n - g - l)$ و یا بزرگ‌تر $(g)$ از $M^\ast$ بودند، با کاهش یک واحدی $M^\ast$ نیاز به یک عملیات بیشتر دارند.
+ اعدادی که کوچک‌تر $(l)$ از $M^\ast$ بودند، با کاهش یک واحدی $M^\ast$ نیاز به یک عملیات کمتر دارند.

### گام چهارم

حال می‌دانیم $f(M^\ast)$ کمینه است پس از $f(M^\ast + 1)$ و $f(M^\ast - 1)$ کمتر یا مساوی است. پس با توجه به دو تساوی بالا داریم:

$$f(M^\ast) \leq f(M^\ast + 1) \Rightarrow f(M^\ast) \leq f(M^\ast) + n - 2g \Rightarrow$$

$$0 \leq n - 2g \quad \Rightarrow \quad g \leq \frac{n}{2}$$

همچنین به طور مشابه:
$$f(M^\ast) \leq f(M^\ast - 1) \Rightarrow f(M^\ast) \leq f(M^\ast) + n - 2l \Rightarrow$$

$$0 \leq n - 2l \quad \Rightarrow \quad l \leq \frac{n}{2}$$

### گام پنجم

یادآوری می‌کنیم که $g$ و $l$ به ترتیب تعداد اعدادی هستند که از $M^\ast$ بیشتر و کمتر است. پس اگر بخواهیم $M$‌ای را پیدا کنیم که از $f(M)$ کمینه باشد. باید به سراغ عددی در دنباله برویم که کمتر یا مساوی نصف اعداد از آن بزرگ‌تر و کمتر یا مساوی نصف اعداد از آن کوچک‌تر است. 

پس اگر دنباله $a_1, a_2, \dots, a_n$ را به ترتیب **صعودی مرتب** کنیم.

اگر $n$ فرد باشد:
$$M = a_{\frac{n + 1}{2}}$$
اگر $n$ زوج باشد:
$$a_{\frac{n}{2}} \leq M \leq a_{\frac{n}{2} + 1}$$

مرتبه زمانی (در فصل‌های بعدی مفصل به آن پرداخته می‌شود.) از $O(n.log(n))$ است.

<details class="blue"> 

<summary>
اگر برای فهمیدن راه‌حل سوال به **شبه‌کد** آن نیاز دارید، بر روی این قسمت کلیک کنید!
</summary>

```
sort a increasing

if n is odd:
    M = a[(n + 1) / 2]
else:
    M = a[n / 2])

ans = 0
for i from 1 to n:
    ans += |a[i] - M|
```

</details>

</details>

Java 17

Java 8

Python 2

الگوریتم پیشرفته و ساختمان‌داده‌ها