سلام!
راه‌حل‌های سؤالات آزمون ورودی بوت‌کمپ برنامه‌نویسی رهنماکالج در ادامه توضیح داده شدند. در صورتی که متوجه راه‌حلی نشدید، می‌تونید در بخش نظرات، سؤالات و ابهام‌های خودتون رو مطرح کنید.
نکته: امکان انتشار پاسخ‌های سؤالات تکنولوژی به‌دلیل استفاده از اون‌ها در مهارت‌سنجی، وجود نداره.
اگه راه‌حل دیگه‌ای برای سؤالات دارید، خوشحال می‌شیم که راه‌حلتون رو در بخش نظرات با ما و دوستانتون به اشتراک بذارید.
کافی است بعد از ورودی‌گرفتن n و دنباله‌ی t_iها، با ایجاد یک حلقه (for) بر روی همه‌ی t_iها و یک شرط (if) بررسی کنید که آیا t_i بیشتر از ۱۵ است یا نه. در صورتی که t_i بیشتر از ۱۵ بود، رشته‌ی cooler و در غیر این صورت رشته‌ی heater را چاپ کنید.
اگر یک جدول n \times m داشته باشیم، کمترین تعداد بلوک a \times b که می‌توان در آن قرار داد به‌طوری که هیچ بلوک دیگری در آن جا نشود برابر است با:
\lfloor \frac{n - a + 1}{2a - 1} \rfloor . \lfloor \frac{m - b + 1}{2b - 1} \rfloorاثبات:
روش زیر می‌تواند با قرار دادن \lceil \frac{n - a + 1}{2a - 1} \rceil . \lceil \frac{m - b + 1}{2b - 1} \rceil بلوکِ a \times b کاری کند که هیچ بلوک دیگری نتوان در صفحه گذاشت.
در این روش a - 1 سطر اول را در نظر نگیرید، a سطر بعدی را در نظر بگیرید، a - 1 سطر بعدی را در نظر نگیرید و… این کار را تا آخرین سطری که می‌توانید انجام دهید. سپس b - 1 ستون اول را در نظر نگیرید، b ستون بعدی را در نظر بگیرید، b - 1 ستون بعدی را در نظر نگیرید و… این کار را تا آخرین ستونی که می‌توانید انجام دهید. حال اگر هم سطر و هم ستون یک خانه را در نظر گرفته‌اید، آن را بخرید. (توجه کنید در این روش همواره بلوک‌های a \times b خریداری می‌شوند.)
حال باید ثابت کنیم هیچ روشی نمی‌تواند با تعداد کمتری بلوک، این کار را انجام دهد.
مجدداً a سطر اول را در نظر بگیرید، a - 1 سطر بعدی را در نظر نگیرید، a سطر بعدی را در نظر بگیرید و… این کار را تا آخرین سطری که می‌توانید انجام دهید. سپس b ستون اول را در نظر بگیرید، b - 1 ستون بعدی را در نظر نگیرید، b ستون بعدی را در نظر بگیرید و… این کار را تا آخرین ستونی که می‌توانید انجام دهید. حال اگر هم سطر و هم ستون یک خانه را در نظر گرفته‌اید، آن را بخرید. (توجه کنید در این روش همواره بلوک‌های a \times b خریداری می‌شوند.)
هر روشی که بلوک‌ها را بگذاریم تا هیچ بلوک دیگری نتوان گذاشت، باید یک بلوک برای نواحی بالا در نظر گرفته شود. (به عبارت دیگر هیچ دوتایی از این ناحیه‌ها را نمی‌توان با یک بلوک پوشاند.) همچنین اگر یکی از این نواحی با بلوک‌های گذاشته‌شده اشتراک پیدا نکند، می‌توان در آن‌جا یک بلوک قرار داد. (که این یعنی خواسته سؤال برآورده نشده است.)
پس حداقل به اندازه تعداد نواحی بالا، باید بلوک در صفحه بگذاریم. بنابراین پاسخ مسئله حداقل برابر است با:
\lfloor \frac{n + a + 1}{2a - 1} \rfloor . \lfloor \frac{m + b + 1}{2b - 1} \rfloorمسئله را به‌صورت یک گراف جهت‌دار مدل می‌کنیم؛ به این صورت که اگر شخص u رابطه‌ی دهن‌لقی با v داشته باشد، یک یال جهت‌دار از u به v رسم می‌کنیم.
حال مسئله به پیدا‌کردن کوتاه‌ترین مسیر از رأس t به رأس s کاهش پیدا می‌کند. این مسئله را می‌توان با الگوریتم BFS از مرتبه‌ی زمانی O(n + m) حل کرد که آن را در فصل ۱۴ کالج تفکر الگوریتمی پیشرفته و ساختمان‌داده‌ها آموزش داده‌ایم.
مسئله، شمارشِ تعداد مثلث‌های قائم‌الزاویه با اضلاع طبیعی و طول وتر n است. پاسخ این مسئله معادل تعداد جواب‌های این معادله در مجموعه اعداد طبیعی است. (یعنی هر جواب این معادله با یک مثلث قائم‌الزاویه در تناظر یک‌به‌یک است.)
\begin{matrix}
a^{2} + b^{2} = n^{2} & & \big(a \leq b\big)
\end{matrix}زیر‌مسئله اول
با ایجاد دو حلقه‌ی تو‌در‌تو و حالت‌بندی روی a (از 1 تا n) و b (از a تا n) می‌توان بررسی کرد که آیا این دو مقدار یک جواب برای معادله هستند یا خیر.
پیچیدگی زمانی: O(n^2)
زیر‌مسئله دوم
با ایجاد یک حالت‌بندی روی a (از 1 تا n) مقدار b را می‌توان به‌صورت زیر به دست آورد:
a^2 + b^2 = n^2 \quad \Rightarrow \quad b^2 = n^2 - a^2 \quad\Rightarrow \quad b = \sqrt{n^2 - a^2}تنها کافی است شرط \sqrt{ n^{2} - a^{2} } \geq a را بررسی کنیم تا جواب‌های معادله را به‌درستی بشماریم.
پیچیدگی زمانی: O(n^2)
زیر‌مسئله سوم
فرض کنید تعداد جواب‌های این معادله به‌شرطی که a, b, n نسبت به هم اول باشند، برابر با f(n) باشد.
در این صورت می‌توان نشان داد که پاسخ مسئله برابر است با:
چون اگر g مقسوم‌علیه مشترک a, b, n باشد، با تقسیم کردن g^2 به دو طرف تساوی می‌توان آن را با یک جواب f(\frac{n}{g}) متناظر کرد.
حال کافی است بتوانیم مقدار f(n) را حساب کنیم. می‌توان ثابت کرد که اگر a, b, n نسبت به هم اول باشند، دو عدد صحیح و مثبت u و v چنان موجود است که:
a = u^2 - v^2, \quad b = 2uv, \quad n = u^2 + v^2, \quad \quad (v \leq u)
اکنون با ایجاد یک حلقه روی u (از 1 تا \sqrt{n}) می‌توان مقدار v را پیدا کرد و سپس از روی آن می‌توان a و b را پیدا کرد و به این ترتیب می‌توانیم همه‌ی جواب‌های این معادله را بررسی کنیم.
پیچیدگی زمانی: O(div(n). \sqrt{n}) (منظور از div(n) تعداد مقسوم‌علیه‌های عدد n است.)
بیاید این n دوست را به‌صورت زیر مرتب کنیم:
- کسی که مهارت فرانت‌اند (f_i) کمتری دارد، اندیس کمتری داشته باشد.
- اگر دو نفر مهارت فرانت‌اند (f_i) یکسانی دارند، کسی که مهارت بک‌اند (b_i) بیشتری دارد، اندیس کمتری داشته باشد.
- اگر دو نفر مهارت فرانت‌اند و بک‌اند یکسانی دارند، به هر ترتیبی که دوست دارند قرار بگیرند.
می‌توان ثابت کرد تنها زمانی هیچ‌کس در یک زیرمجموعه از این دوستان احساس حقارت نمی‌کند که دنباله‌ی آن‌ها در ترتیب بالا، بر اساس مهارت بک‌اند (b_i) نزولی باشد.
حال در دنباله و ترتیب جدید، dp[i] را به این صورت تعریف می‌کنیم: «بیشترین مجموع پول نقدی که می‌توان با یک زیرمجموعه از افراد 1 تا i انتخاب کرد به‌طوری که حتماً i انتخاب شود و هیچ‌کس احساس حقارت نکند.»
با تعریف بالا می‌توان رابطه‌ی زیر را نوشت:
dp[i] = \max_{b_j > b_i,\, j < i} \{dp[j]\} + m_i برای اینکه بتوانیم این رابطه‌ی بازگشتی را محاسبه کنیم، باید بعد از محاسبه‌ی هر dp[i] آن را بر اساس b_i در یک ساختمان داده مثل درخت فنویک (fenwick tree) یا درخت بازه‌ای (segment tree) ذخیره کنیم تا بتوانیم درج و محاسبه‌ی این ماکسیمم را از O(\log{n}) انجام دهیم.
بعد از محاسبه‌ی کل آرایه‌ی dp، پاسخ مسئله برابر است با:
\max_{1\leq i \leq n} \{dp[i]\} پیچیدگی زمانی: O(n.\log{n})
