تمرین ۲
ددلاین تحویل: ۱ خرداد ۲۳:۵۹
مقدماتی:
سوال ۱ — پوشاندن نوار
یک نوار مستطیلی \(1 \times n\) داریم. میخواهیم این نوار را بهطور کامل با دو قطعهی \(1 \times 1\) و \(1 \times 2\) بپوشانیم. هر قطعه باید کاملاً داخل نوار قرار گیرد و هیچ دو قطعهای نباید همپوشانی داشته باشند. الگوریتمی با زمان اجرای \(\mathcal{O}(n)\) برای محاسبه تعداد روشهای پوشاندن این نوار ارائه دهید.
سوال ۲ — ترکیب تاسها
یک تاس \(k\) وجهی داریم که روی وجههای آن، اعداد \(1, 2, \dots, k\) نوشته شدهاست. به چند روش میتوان یک یا چند تاس انداخت، که مجموع تاسها برابر با \(n\) شود.
برای مثال اگر \(n=3\) و \(k=6\) باشد ۴ حالت داریم: \(1+1+1\) و \(1+2\) و \(2+1\) و \(3\).
الگوریتمی با زمان اجرای \(\mathcal{O}(nk)\) برای حالت کلی مسئله ارائه دهید.
سوال ۳ — کمینه سکه
در کشوری، \(n\) نوع سکه با ارزشهای \(c_1,c_2,\dots,c_n\) وجود دارد و از هر نوع سکه، تعداد نامحدودی در اختیار داریم. میخواهیم مبلغ \(m\) را با استفاده از کمترین سکه ممکن پرداخت کنیم. الگوریتمی از \(\mathcal{O}(nm)\) ارائه دهید تا کمترین سکه لازم برای پرداخت را پیدا کند.
برای مثال اگر \(n=3, m = 9\) و \(c=\{1,2,5\}\) باشد، کمترین سکه لازم برابر با \(3\) است.
سوال ۴ — قورباغه
\(n\) سنگ بهترتیب از چپ به راست از \(1\) تا \(n\) شمارهگذاری شدهاند و ارتفاع سنگ \(i\)-ام برابر \(h_i\) است. قورباغهای در ابتدا روی سنگ \(1\) قرار دارد و میخواهد به سنگ \(n\) برسد. اگر قورباغه از سنگ \(i\) به سنگ \(j\) بپرد، باید \(j \in \{i+1,i+2,\dots,i+k\}\) باشد. هزینه این پرش برابر با \(|h_i-h_j|\) است. کمینه هزینه لازم برای رسیدن از سنگ \(1\) به سنگ \(n\) را محاسبه کنید.
سوال ۵ — فرجه
دکتر آبام برای بین دو ترم \(n\) روز فرجه ترتیب دیدهاند. شما در هر روز یکی از سه تفریحی که در زندگیتان دارید را انجام میدهید. و از انجام هر کدام به ترتیب \(A_i, B_i, C_i\) واحد لذت میبرید. اما اگر دو روز متوالی یک تفریح را انجام دهید، فرجه زهرمارتان میشود. بیشترین لذتی که میتوانید از این \(n\) روز تجربه کنید را در \(\mathcal{O} (n)\) محاسبه کنید.
سوال ۶ — پرش به جلو
یک آرایه به طول \(n\) از اعداد طبیعی داریم. هر مرحله اگر در خانه \(i\) اُم آرایه باشیم به خانه \(i + a_i\) میپریم. اگر هم مقدار \(n < i + a_i\) باشد، از آرایه خارج میشویم.
الگوریتمی با پیچیدگی زمانی \(\mathcal{O} (n)\) ارائه دهید که به ازای هر \(i\) ، تعداد پرشهایی که طول میکشد تا از آرایه خارج شود را حساب کند.
سوال ۷ — بیشینه مجموع زیرآرایه (Maximum-Subarray-Sum)
آرایهای از اعداد صحیح (مثبت و منفی) \(a_1,a_2,\dots,a_n\) به طول \(n\) داده شده است. میخواهیم یک زیرآرایه متوالی انتخاب کنیم بهطوریکه مجموع عناصر آن بیشینه شود. الگوریتمی با زمان اجرای \(\mathcal{O}(n)\) ارائه دهید که این مقدار بیشینه را محاسبه کند.
برای مثال اگر \(A=\langle -7, 10, 2, -5, 3, 7, -100, 16 \rangle\) باشد با انتخاب عضو دوم تا ششم به مجموع \(17\) میرسیم که ماکسیمم است.
سوال ۸ — بلندترین مسیر در DAG
فرض کنید یک گراف جهتدار با \(n\) راس و \(m\) یال داریم به این صورت که اگر بین دو راس \(i < j\) یالی وجود داشته باشد جهت آن از \(i\) به \(j\) خواهد بود. الگوریتمی با پیچیدگی زمانی \(\mathcal{O}(n + m)\) ارائه دهید که بلندترین مسیر در این گراف را پیدا کند.
پاسخ - محمد محمودیه
سوال ۹ — مسیرها در جدول
یک جدول \(n \times m\) داریم که برخی از خانههای آن مسدود هستند. سطرها از بالا به پایین از \(1\) تا \(n\) و ستونها از چپ به راست از \(1\) تا \(m\) شماره گذاری شدهاند. از خانه \((1,1)\) میخواهیم به خانه \((n,m)\) برویم. در هر مرحله فقط اجازه داریم یک خانه به راست یا یک خانه به پایین حرکت کنیم و ورود به خانههای مسدود مجاز نیست. الگوریتمی با زمان اجرای \(\mathcal{O}(nm)\) برای محاسبه تعداد مسیرهای ممکن ارائه دهید.
سوال ۱۰ — مجموع زیرمستطیل
یک جدول \(n \times m\) داریم که در خانه \((i , j)\) آن مقدار \(a_{i,j}\) نوشته شده است. میخواهیم به پرسشهای از جنس مجموع زیرمستطیل پاسخ دهیم. الگوریتمی با پیشپردازش از مرتبه زمانی \(\mathcal{O}(n m)\) ارائه دهید که بتواند هر پرسش را با \(\mathcal{O}(1)\) پاسخ دهد. پرسشها به صورت دو زوج \((x_1 , y_1)\) و \((x_2,y_2)\) به شما داده میشود که به ترتیب برابر با خانه بالا-چپ و پایین-راست زیرمستطیل خواسته شده است.
پاسخ - مهدیار مستشارهریس
سوال ۱۱ — LIS
یک آرایه به طول \(n\) داریم. مقدار خانه \(i\) اُم برابر \(a_i\) است. الگوریتمی با پیچیدگی زمانی \(\mathcal{O}(n ^ 2)\) ارائه دهید که طول بلندترین زیردنباله صعودی آرایه را محاسبه کند.
سوال ۱۲ — کوله پشتی
شما به عنوان یک دزد وارد مغازه شدید. در مغازه \(n\) کالا با شمارههای 1 تا \(n\) وجود دارد. فرض کنید وزن کالا \(i\)اُم برابر با \(w_i\) و قیمت آن برابر با \(v_i\) باشد. شما یک کوله پشتی دارید که مجموع وزن کالاهایی که در آن قرار میدهید نمیتواند از \(W\) بیشتر باشد. هدف شما این است که تعدادی از این کالاها را انتخاب کرده و در کوله پشتی قرار دهید به طوری که مجموع ارزش آنها بیشینه باشد.
الف) با ارائه یک مثال نقض نشان دهید که این الگوریتم اشتباه است. کالاها را به ترتیب از بزرگترین \(\frac{v_i}{w_i}\) تا کمترین مقدار آن مرتب میکنیم. سپس به ترتیب کالاها را پیمایش میکنیم و هر کالایی که در کوله پشتی جا میشد را به آن اضافه میکنیم.
ب) الگوریتمی با پیچیدگی زمانی \(\mathcal{O}(n W)\) ارائه دهید که بیشترین مجموع ارزشی که میتوان در کوله پشتی جا داد را حساب کند.
سوال ۱۳ — عددگذاری در آرایه
یک آرایه به طول \(n\) داریم که مقدار خانه \(i\) اُم آن برابر با \(a_i\) است. میدانیم به ازای هر \(i\) یا مقدار \(1 \leq a_i \leq m\) است یا \(a_i = -1\) است. میخواهیم جوری \(-1\) ها را با اعداد طبیعی بین \(1\) تا \(m\) جایگزین کنیم که در نهایت به ازای هر \(1 \leq i \leq n - 1\) داشته باشیم: \(| a_i - a_{i + 1} | \leq 1\) . الگوریتمی با پیچیدگی زمانی \(\mathcal{O}(n m)\) ارائه دهید که تعداد روشهای انجام این کار را محاسبه کند.
پاسخ - اشکان تاریوردی
سوال ۱۴ — LCS
دو رشته \(s\) و \(t\) داریم که به ترتیب طول هر کدام \(n\) و \(m\) است. الگوریتمی با پیچیدگی زمانی \(\mathcal{O}(n m)\) ارائه دهید که بلندترین زیردنباله مشترک این دو رشته را پیدا کند. یعنی بلندترین رشته \(w\) را پیدا کند که \(w\) هم زیردنباله ای از \(t\) و هم زیردنبالهای از \(s\) باشد.
سوال ۱۵ — تقسیم بر 2
فرض کنید یک تابع بازگشتی \(f\) داریم که پایه آن مقدار \(f(1)\) است و مقدار \(f(n)\) تنها وابسته به مقادیر \(f(\lfloor \frac{n}{2} \rfloor)\) و \(f(\lceil \frac{n}{2} \rceil)\) است. ثابت کنید تعداد ورودیهای متمایزی که تابع \(f\) با آنها فراخوانی میشود از مرتبه \(\mathcal{O}(\log n)\) است.
پاسخ - شایان سبزی
سوال ۱۶ — بلندترین زیردنباله پالیندروم
یه رشته \(s\) به طول \(n\) داریم. الگوریتمی با پیچیدگی زمانی \(\mathcal{O}(n^2)\) ارائه دهید که طول بلندترین زیردنباله پالیندروم \(s\) را حساب کند.
زیردنباله یعنی چند کاراکتر از رشته را به ترتیب انتخاب کنیم، ولی لازم نیست کنار هم باشند. مثلا اگر \(s = \texttt{abcbd}\) باشد، رشتهی \(\texttt{abd}\) یک زیردنبالهی آن است.
سوال ۱۷ — ضرب ماتریسها
فرض کنید \(n\) ماتریس \(A_1 , A_2 , \dots , A_n\) و یک آرایه \(p\) به طول \(n + 1\) داریم به طوری که ابعاد ماتریس \(A_i\)، \(p_i \times p_{i + 1}\) است و میخواهیم مقدار \(A_1 \times A_2 \times \dots \times A_n\) را حساب کنیم.
میدانیم ضرب یک ماتریس \(a \times b\) در یک ماتریس \(b \times c\) نیاز به انجام \(a \times b \times c\) عملیات ضرب دارد و حاصل آن یک ماتریس \(a \times c\) خواهد بود.
حال میخواهیم طوری این عبارت را پرانتزگزاری کنیم که در مجموع کمترین تعداد عملیات ضرب را انجام دهیم. الگوریتمی با پیچیدگی زمانی \(\mathcal{O} (n ^ 3)\) ارائه دهید تا کمینه تعداد عملیات ضرب مورد نیاز را محاسبه کند.
سوال ۱۸ — لذت در کارنیوال
شما در یک کارنیوال ابدی شرکت کرده اید.از طریق ارتباطی که با کائنات برقرار کردید اطلاعات \(n\) تا از رویدادهای کارنیوال به شما الهام شده است.شما میدانید رویداد \(i\) در زمان \(s_i\) آغاز شده، در زمان \(t_i\) به پایان میرسد و با شرکت کردن در آن \(p_i\) واحد لذت میبرید. اما شرکت کردن در این رویدادها علیرغم میل باطنیتان به حضور فیزیکی شما در مکان برگزاری آنها وابسته است. از این رو شرکت کردن همزمان در دو رویداد برای شما امکانپذیر نیست. اما میتوانید از زمان لازم برای جابهجایی بین مکانها صرف نظر کنید. بیشترین لذتی که میتوان از این \(n\) رویداد برد را در زمان \(\mathcal{O} (n \log n)\) محاسبه کنید.
پاسخ - ایلیا فرصتی
سوال ۱۹ — فاصله ویرایشی
دو رشته \(s\) و \(t\) به ترتیب با طولهای \(n\) و \(m\) داریم. میخواهیم با تکرار عملیاتهای زیر رشته \(s\) را به رشته \(t\) تبدیل کنیم.
عملیات 1: یکی از حروف رشته \(s\) را به دلخواه حذف میکنیم. هزینه این عملیات \(a\) است.
عملیات 2: یک حرف به هر جای دلخواه از \(s\) اضافه میکنیم. هزینه این عملیات \(b\) است.
عملیات 3: یک حرف \(s\) را به دلخواه به یک حرف دیگر تغییر میدهیم. هزینه این عملیات \(c\) است.
الگوریتمی با پیچیدگی زمانی \(\mathcal{O}(n m)\) ارائه دهید که کمترین هزینه موردنیاز برای تبدیل \(s\) به \(t\) را محاسبه کند.
پاسخ - محمدپارسا شاهمحمدی
سوال ۲۰ — قفسه کتاب
در یک کتابخانه \(n\) کتاب وجود دارد. کتاب \(i\) ام دارای ضخامت \(t_i\) و عرض \(w_i\) است. میخواهیم این کتابها را در یک قفسه کتاب قرار دهیم به این صورت که ابتدا تعدادی از این کتابها را به صورت عمودی در پایین قفسه کتاب کنار هم قرار میدهیم. سپس باقی کتابها را به صورت افقی روی کتابهای عمودی قرار میدهیم. شرط انجام اینکار این است که مجموع ضخامت کتابهای طبقه پایین حداقل به اندازه مجموع عرض کتابهای طبقه بالا باشد. (به بیان دیگر \(\sum t_i\) کتابهای عمودی بیشتر از یا مساوی با \(\sum w_i\) کتابهای افقی باشد). الگوریتمی با پیچیدگی زمانی \(\mathcal{O}(n \cdot \sum t_i)\) ارائه دهید که کمینه مقدار \(\sum t_i\) کتابهای طبقه پایین را پیدا کند.
پاسخ - سپهر علیپور
سوال ۲۱ — LIS 2
یک آرایه به طول \(n\) داریم. مقدار خانه \(i\) اُم برابر \(a_i\) است. الگوریتمی با پیچیدگی زمانی \(\mathcal{O}(n \log n)\) ارائه دهید که طول بلندترین زیردنباله صعودی آرایه را محاسبه کند.
سوال ۲۲ — مستطیلها
ما \(n\) تا مستطیل داریم که از 1 تا \(n\) شمارهگذاری شدهاند. طول و عرض مستطیل \(i\)اُم را به ترتیب با \(w_i\) و \(h_i\) نشان میدهیم. الگوریتمی با پیچیدگی زمانی \(\mathcal{O}(n \log n)\) ارائه دهید که اندازه بزرگترین زیرمجموعهای از مستطیلها را حساب کند که هر دو مستطیلی که داخل این زیرمجموعه هستند را در نظر بگیریم یکی از آنها کامل در دیگری جا شود. (اگر این دو مستطیل را \(i\) و \(j\) در نظر بگیریم یعنی یا \(h_i > h_j , w_i > w_j\) و یا \(h_j > h_i , w_j > w_i\) برقرار باشد.)
پیشرفته
سوال ۲۳ — کوله پشتی 2
شما به عنوان یک دزد وارد مغازه شدید. در مغازه \(n\) کالا با شمارههای 1 تا \(n\) وجود دارد. فرض کنید وزن کالا \(i\)اُم برابر با \(w_i\) و قیمت آن برابر با \(v_i\) باشد. شما یک کوله پشتی دارید که مجموع وزن کالاهایی که در آن قرار میدهید نمیتواند از \(W\) بیشتر باشد. هدف شما این است که تعدادی از این کالاها را انتخاب کرده و در کوله پشتی قرار دهید به طوری که مجموع ارزش آنها بیشینه باشد. الگوریتمی با پیچیدگی زمانی \(\mathcal{O}(n \cdot \sum v_i)\) ارائه دهید که این مقدار را حساب کند.
پاسخ - پارسا ضمیری
سوال ۲۴ — وضعیت LIS
یک آرایه به طول \(n\) داریم که مقدار عضو \(i\) اُم آن برابر با \(a_i\) است. شما باید الگوریتمی با پیچیدگی زمانی \(\mathcal{O}(n \log n)\) ارائه دهید که به ازای هر \(1 \leq i \leq n\) مشخص کند که اندیس \(i\) اُم آرایه در کدام گروه زیر قرار میگیرد:
گروه 1: اندیسهایی که در تمام LIS های آرایه ظاهر شدهاند.
گروه 2: اندیسهایی که در بعضی ولی نه همه LIS های دنباله ظاهر شدهاند.
گروه 3: اندیسهایی که در هیچکدام از LIS های دنباله ظاهر نشدهاند.
پاسخ - متین غیاثی
سوال ۲۵ — کیسهها و سکهها
شما \(n\) کیسه و \(s\) سکه دارید. هدف شما این است که تشخیص دهید که میتوانیم یا نمیتوانیم این \(s\) سکه را بین این کیسه ها تقسیم کنید به طوری که بعد از تقسیم سکهها، بتوان بعضی از کیسهها را طوری داخل هم قرار داد به طوری که در نهایت داخل کیسه \(i\) اُم در مجموع \(a_i\) سکه باشد . (سکهها میتوانند به صورت مستقیم داخل کیسه باشند یا داخل یکی از کیسههایی باشند که داخل کیسه \(i\) اُم قرار دارد). با پیچیدگی زمانی \(\mathcal{O}(n s)\)مسئله را حل کنید.
پاسخ - سهیل سیاح ورگ
سوال ۲۶ — درخت جستوجوی دودویی بهینه
دو آرایه به طول \(n\) از کلیدهای \(k_1, k_2, \dots , k_n\) و احتمالات جستوجوی \(p_1, p_2, \dots , p_n\) داده شده است. میخواهیم یک درخت جستوجوی دودویی(BST) بسازیم که هزینه موردانتظار جستوجو در آن کمینه باشد. هزینه جستوجوی یک BST برابر با \(\sum (h_i \times p_i)\) است که \(h_i\) ارتفاع راس \(i\) اُم است.
الگوریتمی با پیچیدگی زمانی \(\mathcal{O}(n^3)\) ارائه دهید که این هزینه کمینه را محاسبه کند.
پاسخ - آروین بقال اصل
سوال ۲۷ — حذف پالیندروم
یک دنباله به طول \(n\) داریم که مقدار عدد \(i\) اُم برابر \(a_i\) است. هر مرحله میتوانیم یک بازه متوالی از دنباله که پالیندروم است را از دنباله حذف کنیم (بعد از حذف این بازه اگر دنباله دو تیکه شد آنها را کنار هم میگذاریم تا تشکیل یک دنباله واحد دهند.) الگوریتمی با پیچیدگی زمانی \(\mathcal{O}(n^3)\) ارائه دهید که کمترین تعداد عملیات لازم برای حذف کامل دنباله را حساب کند.
پاسخ - رسا محمدی
سوال ۲۸ — برج قرمز سبز
شما \(r\) بلوک قرمز و \(g\) بلوک سبز دارید و میخواهید با آنها یک برج بسازید. اگر برج \(h\) طبقه داشته باشد، طبقهٔ اول باید شامل \(h\) بلوک باشد، طبقهٔ دوم \(h-1\) بلوک، و به همین ترتیب تا طبقهٔ آخر که شامل یک بلوک است. همچنین هر طبقه باید تماما از یک رنگ تشکیل شده باشد. فرض کنید \(h\) بیشترین ارتفاع ممکنی باشد که میتوان با بلوکهای موجود ساخت. تعداد برجهای متفاوت با ارتفاع \(h\) را حساب کنید. دو برج متفاوتاند اگر حداقل در یک طبقه، رنگ بلوکهای آنها متفاوت باشد. الگوریتمی با پیچیدگی زمانی \(\mathcal{O}((r+g)\sqrt{r+g})\) ارائه دهید که پاسخ را محاسبه کند.
پاسخ - محمدعلی مسچی
سوال ۲۹ — رنگ کردن حصار
حمید تصمیم گرفته است حصار قدیمی خود را به رنگ موردعلاقهاش، آبی، رنگ کند. حصار از \(n\) تختهٔ عمودی تشکیل شده که پشت سر هم قرار گرفتهاند و هیچ فاصلهای بین تختههای مجاور وجود ندارد. تختهها از چپ به راست از ۱ شمارهگذاری شدهاند. عرض هر تخته برابر ۱ متر است و ارتفاع تختهٔ \(i\) اُم برابر \(a_i\) متر میباشد. حمید یک قلممو با عرض ۱ متر خریده است. او میتواند با قلممو حرکتهای عمودی و افقی انجام دهد. در طول هر حرکت، تمام سطح قلممو باید همواره با حصار در تماس باشد. هدف این است که تمام حصار به طور کامل رنگ شود. توجه کنید که میتوان یک قسمت از حصار را چندین بار رنگ کرد. الگوریتمی با پیچیدگی زمانی \(\mathcal{O}(n^2)\) ارائه دهید که کمترین تعداد حرکت لازم برای رنگ کردن کامل حصار را محاسبه کند.
سوال ۳۰ — تخممرغ
یک ساختمان \(n\) طبقه داریم و \(e\) تخم مرغ سخت. میدانیم که طبقهای مانند \(2 \leq x \leq n\) وجود دارد که اگر تخم مرغها از طبقه \(x\) یا بالاتر بیافتند میشکنند و اگر از طبقه \(x - 1\) یا پایینتر بیافتند، نمیشکنند. (یعنی اگر تخم مرغ را از طبقه اول بیاندازیم حتما نمیشکند و اگر از طبقه آخر بیاندازیم حتما میشکند) در هر آزمایش میتوانیم یک تخم مرغ را از یک طبقه دلخواه بیاندازیم. اگر این تخم مرغ بشکند، دیگر نمیتوان از آن استفاده کرد ولی اگر نشکند باز هم میتوان از آن استفاده کرد. هدف پیدا کردن طبقه \(x\) است.
میخواهیم تشخیص دهیم که در حالتی که بهترین روشی که میتوانیم آزمایش کنیم تا در بدترین حالت کمترین تعداد آزمایش را کرده باشیم را انجام دهیم در این بدترین حالت چه تعداد آزمایش انجام دادهایم.
ساب 1) الگوریتمی با پیچیدگی زمانی \(\mathcal{O}(n^2 e)\) ارائه دهید که این تعداد آزمایش را محاسبه کند.
ساب 2) الگوریتمی از پیچیدگی زمانی \(\mathcal{O}(n^2 \log n)\) ارائه دهید.
ساب 3) الگوریتمی از پیچیدگی زمانی \(\mathcal{O}(n \log n)\) ارائه دهید.
ساب 4) الگوریتمی از پیچیدگی زمانی \(\mathcal{O}(\sqrt{n} \log n)\) ارائه دهید.
پاسخ - آرش قوامی
سوال ۳۱ — LCS of permutations
دو جایگشت از اعداد 1 تا \(n\) داریم. میخواهیم طول بلندترین زیردنباله مشترک آنها را پیدا کنیم. الگوریتمی با پیچیدگی زمانی \(\mathcal{O}(n \log n)\) ارائه دهید.
پاسخ - محمدرضا ایزدی
سوال ۳۲ — کران پایین LCS
فرض کنید دو رشته \(s\) و \(t\) به طول \(n\) داریم. الگوریتمی با پیچیدگی زمانی \(\mathcal{O}(n k)\) ارائه دهید که تشخیص دهد آیا طول بلندترین زیردنباله مشترک این دو رشته حداقل \(k\) هست یا نه.
پاسخ - زهرا قصابی
سوال ۳۳ — مسیر همیلتونی
یک گراف ساده \(n\) راسی داریم. الگوریتمی با پیچیدگی زمانی \(\mathcal{O}(2^n n^2)\) ارائه دهید که مشخص کند آیا گراف مسیری دارد که شامل تمام رئوس گراف باشد یا خیر.
سوال ۳۴ — دور همیلتونی
یک گراف ساده \(n\) راسی داریم. الگوریتمی با پیچیدگی زمانی \(\mathcal{O}(2^n n^2)\) ارائه دهید که مشخص کند آیا گراف دوری دارد که شامل تمام رئوس گراف باشد یا خیر.
پاسخ - نیما نظری
سوال ۳۵ — ترکیب مجاورهای برابر
یک آرایه به طول \(n\) از اعداد طبیعی داریم که مقدار درایه \(i\) اُم آن برابر با \(a_i\) است. هر مرحله میتوانیم دو عضو مجاور که مقدار هر دوی آنها برابر است را با هم ترکیب کنیم و به یک عضو با مقدار یک واحد بیشتر تبدیل کنیم. به بیان دیگر اگر دو \(x\) مجاور در آرایه را ترکیب کنیم، یک عدد \(x+1\) به وجود میآید. هدف ما این است که با تکرار این عملیات به بزرگترین عددی که میتوانیم برسیم.
الگوریتمی با پیچیدگی زمانی \(\mathcal{O}(n \log n)\) ارائه دهید که بزرگترین عددی که میتوانیم به آن برسیم را حساب کند
سوال ۳۶ — پوشاندن نوار 2
یک نوار مستطیلی \(1 \times n\) داریم. میخواهیم این نوار را به طور کامل با قطعات \(1 \times 1\) و \(1 \times 2\) بپوشانیم. هر قطعه باید کامل داخل نوار قرار بگیرد و هیچ دو قطعهای نباید همپوشانی داشته باشند. الگوریتمی با پیچیدگی زمانی \(\mathcal{O}(\log n)\) ارائه دهید که که تعداد روشهای انجام اینکار را محاسبه کند.
پاسخ - روژین تقیزادگان
سوال ۳۷ — مشمخ
به یک آرایه \(a\) به طول \(k\) از اعداد طبیعی خوب میگوییم اگر برای هر \(i\) داشته باشیم \(1 \leq a_i \leq n\) و هم چنین به ازای هر \(1 \leq i \leq k - 1\) شرط \(a_i | a_{i + 1}\) برقرار باشد.
الگوریتمی با پیچیدگی زمانی \(\mathcal{O}(n k \log n)\) ارائه دهید که تعداد این دنباله ها را بشمارد.
پاسخ - محمد بنیاحمدی
سوال ۳۸ — جستوجو وزندار
علی و رضا یک بازی روی آرایهای مرتبشده (صعودی) به طول \(n\) انجام میدهند:
-
علی یک عدد \(x\) انتخاب میکند.
-
رضا باید با طرح سوالاتی، اولین خانهای از آرایه که از \(x\) بزرگتر است را پیدا کند (یا متوجه شود همه خانهها از \(x\) کوچکترند).
-
رضا در هر سوال یک اندیس \(i\) انتخاب میکند و علی پاسخ میدهد که آیا عنصر خانه \(i\) ام از \(x\) بزرگتر است یا خیر. هزینه پرسیدن این سوال \(c_i\) است.
رضا تلاش میکند با یک استراتژی بهینه، بیشترین پولی که ممکن است بپردازد (هزینه در بدترین حالت) را کمینه کند. از طرفی، علی عدد \(x\) را طوری انتخاب میکند که این هزینه بیشینه شود. با فرض اینکه هر دو نفر کاملاً بهینه عمل میکنند، الگوریتمی با پیچیدگی زمانی \(\mathcal{O}(n \log n \cdot c^2)\) ارائه دهید که هزینه نهایی رضا را محاسبه کند.
سوال ۳۹ — RGB
شما میخواهید یک دنباله به طول \(n\) بسازید که هر عضو آن یکی از 3 رنگ قرمز، آبی و سبز باشد. همچنین \(m\) شرط به شما داده شده است. شرط \(i\) اُم شامل سه مقدار \(l_i\) و \(r_i\) و \(x_i\) است و به این معناست که در بازه \([l_i , r_i]\) باید از دقیقا \(x_i\) رنگ متمایز استفاده شود.
الگوریتمی با پیچیدگی زمانی \(\mathcal{O} (n ^ 2 (n + m))\) ارائه دهید تا تعداد دنبالههای رنگی متمایزی که در شرط ها صدق میکند را محاسبه کند.
سوال ۴۰ — مسیرها در جدول ۲
یک جدول \(n \times m\) داریم که دقیقاً \(k\) خانه \((x_1, y_1), (x_2, y_2), \dots, (x_k, y_k)\) از آن مسدود هستند. از خانه \((1,1)\) میخواهیم به خانه \((n,m)\) برویم. در هر مرحله فقط اجازه داریم یک خانه به راست یا یک خانه به پایین حرکت کنیم و ورود به خانههای مسدود مجاز نیست. هدف محاسبهی تعداد مسیرهای ممکن است.
برای حالت کلی مسئله، الگوریتمی از \(\mathcal{O}(n+m+k^2)\) ارائه دهید.
سوال ۴۱ — جدول سکهها
یک جدول \(n \times n\) داریم. در خانهی واقع در سطر \(i\) و ستون \(j\)، تعداد \(a_{i,j}\) سکه قرار دارد. آلیس و باب هر دو از خانهی \((1,1)\) شروع میکنند و میخواهند به خانهی \((n,n)\) برسند. هر کدام از آنها در هر حرکت فقط میتواند یک خانه به پایین برود یا یک خانه به راست برود. آلیس و باب در طول مسیر خود، سکههای خانههایی را که از آنها عبور میکنند جمع میکنند. اگر هر دو نفر از یک خانه عبور کنند، سکههای آن خانه فقط یکبار جمع میشود و دوبار حساب نمیشود. هدف این است که دو مسیر برای آلیس و باب انتخاب کنیم بهطوریکه مجموع تعداد سکههای جمعآوریشده بیشینه شود. الگوریتمی از \(\mathcal{O}(n^3)\) ارائه دهید که بیشترین تعداد سکهی قابل جمعآوری را محاسبه کند.
سوال ۴۲ — مسیرهای مجزا
یک جدول \(n \times m\) داریم که بعضی از خانههای آن مسدود هستند. آلیس از خانهی \((1,2)\) شروع میکند و میخواهد به خانهی \((n-1,m)\) برسد. باب از خانهی \((2,1)\) شروع میکند و میخواهد به خانهی \((n,m-1)\) برسد. هر کدام از آنها در هر حرکت فقط میتواند یک خانه به پایین برود یا یک خانه به راست برود.
آلیس و باب میخواهند طوری حرکت کنند که هرگز همدیگر را نبینند؛ یعنی مسیرهای آنها هیچ خانهی مشترکی نداشته باشد. همچنین هیچکدام از آنها نمیتوانند از خانههای مسدود عبور کنند. هدف این است که تعداد زوجمسیرهای ممکن را بشماریم بهطوریکه آلیس و باب هر دو به مقصد خود برسند، از خانههای مسدود عبور نکنند، و در هیچ خانهای با یکدیگر برخورد نکنند.
الگوریتمی \(\mathcal{O}(nm)\) برای مسئله ارائه دهید.