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

یادداشت‌های یک معلم علاقه‌مند به نوشتن از آنچه آموخته و یاد می‌دهد
 

تمرین مسابقه برنامه‌نویسی

مسئله Column Addition
تصور کنید سه ردیف عدد زیر هم به ما داده شده است که ادعا می‌شود ردیف سوم حاصل جمع دو ردیف اول است. این عملیات در پس‌زمینه انجام می‌گیرد که کنترل آن خارج از اختیار ما است و خروجی آن لزوما نشانگر جمع صحیح نیست. اما می‌توانیم هر تعداد ستون دلخواه از آن را حذف کنیم تا به جمع درستی برسیم. به عنوان نمونه، در مثال زیر می‌توانیم با حذف ستون‌های دوم و چهارم به جمع درستی برسیم:

مسئله Jolly Jumpers

دنباله‌ای از $n$ عدد صحیح را Jolly Jumper گویند هر گاه قدر مطلق اختلاف عناصر متوالی آن، همه اعداد 1 تا $n-1$ را تولید کند. برای مثال دنباله

1  4  2  3

Jolly Jumper است. چرا که قدرمطلق اختلاف عناصر متوالی آن 3، 2 و 1 است. همچنین هر دنباله با تنها یک جمله، Jolly Jumper محسوب می‌شود. شما باید برنامه‌ای بنویسید که مشخص کند آیا یک دنباله Jolly Jumper است یا نه؟

مستندات دوره آمادگی مسابقات برنامه‌نویسی دانشگاه استنفورد

مستندات دوره «Introduction to Programming Contests» دانشگاه استنفورد با تدریس Jaehyun Park (مربی تیم‌های ACM-ICPC این دانشگاه) شامل اسلایدها، سوالات برگزیده برای تمرین در موضوعات مختلف ریاضیات، ساختمان داده‌ها و الگوریتم‌ها به همراه نکات برنامه‌نویسی از پیوند زیر قابل مشاهده و دریافت هستند:

مسئله Encrypted SMS

اعضای کمیته علمی ACM‌ امسال از ایمیل برای بحث در مورد سوالات استفاده می‌کنند. آنها می‌دانند که ایمیل ابزار امنی برای ارتباط در مورد چنین موضوعات حساسی نیست. بنابراین فایل‌های فشرده رمزگذاری شده را تبادل می‌کنند. برای تبادل کلمه عبور فایل نیز از SMS رمز شده با ساختار تایپ multi-tap استفاده می‌کنند.

ویدئوهای آموزشی کلاس Programming Challenges

کتاب Programming Challenges: The Programming Contest Training Manual اثر Steven Skiena و Miguel Revilla یکی از کتاب‌های مناسب تمرین گام به گام برای شرکت در مسابقات برنامه‌نویسی‌ای همچون المپیاد کامپیوتر و ACM-ICPC است. این کتاب مورد تایید UVa Online Judge بوده و تمام سوالات تمرینی کتاب نیز از این مخزن است.

مسئله انتخابات

جناب خان که با کسب و کار لبوی خود میلیاردر شده است، می‌خواهد رئیس جمهور شود! در کشور او که از چندین ایالت تشکیل شده است، از روشی با عنوان هیئت انتخاب (یا هیئت الکترال) برای انتخاب رئیس جمهور استفاده می‌شود. در چنین ساختاری شمارش رأی در هر ایالت به صورت مستقل انجام می‌شود و هر ایالت متناسب با جمعیت خود تعدادی نماینده در هیئت انتخاب کنندگان رئیس جمهور دارد. تمام نمایندگان یک ایالت در نهایت به نامزدی رأی می‌دهند که در آن ایالت اکثریت آرا را کسب کرده باشد. اگر نامزدها رأی برابر داشته باشند، هر ایالت قوانین خاص خود برای انتخاب نهایی را دارد. در نهایت رئیس جمهور کسی است که بیش از نصف مجموع رأی‌های هیئت انتخاب را از آن خود کند.

مسئله اعداد اردوش

پل اردوش (اردیش - Paul Erdős) ریاضیدان مشهور و برجسته قرن بیستم است که تا پایان عمر خود تلاش گسترده‌ای برای انتشار مقالات علمی داشت و همکاری با وی در انتشار مقاله یک افتخار بزرگ برای هر ریاضیدان محسوب می‌گردد.

مسئله بشکه‌های آب

$n$ بشکه آب با تعدادی لوله به هم وصل شده‌اند. هر بشکه استوانه‌ای عمودی با سطح مقطع یک متر مربع و ارتفاع نامحدود است که با عدد یکتا بین 1 تا $n$ شماره‌گذاری شده است. $i$-امین لوله بشکه $ x_i $ و $y_i$ را به هم متصل می‌کند. یک سر این لوله در ارتفاع $h_i$ متر به بشکه $ x_i $ متصل است و سر دیگر آن در همان ارتفاع به بشکه $y_i$ متصل است. در زمان صفر بشکه‌ها خالی هستند و یک جریان آب به صورت پیوسته با سرعت یک متر مکعب بر ساعت در بشکه شماره یک می‌ریزد. اگر آب بشکه‌ای به ارتفاع لوله‌ای برسد، آب در لوله جریان پیدا می‌کند و می‌تواند وارد بشکه دیگر شود. فرض کنید قطر لوله‌ها ناچیز است و سرعت آب در لوله‌ها بسیار زیاد است.

مسئله‌ تاریخچه جدول

جدولی با n سطر و m ستون در نظر بگیرید. در تمام خانه‌های این جدول عدد 0‌ نوشته شده است. در ابتدای کار حامد در خانه‌ای از جدول ایستاده است. او عدد این خانه را پاک می‌کند و عدد 1 را به جای آن می‌نویسد. حامد شروع به حرکت می‌کند و در هر ثانیه یک خانه به بالا، راست، پایین یا چپ می‌رود. او با وارد شدن به هر خانه، عدد نوشته شده در خانه را پاک می‌کند و عددی یک واحد بزرگتر از آخرین عددی که نوشته است را می‌نویسد و بعد از مدتی متوقف می‌شود. می‌دانیم حامد در انتهای حرکت خود تمام خانه‌های جدول را دیده است.

مسئله آسانسورها

ساختمان جدید دپارتمان مهندسی کامپیوتر تنها شامل آسانسور بوده و پله ندارد. برای دسترسی سریع و مناسب به اتاق‌ها و کلاس‌های طبقات مختلف، آسانسورها به گونه‌ای تنظیم شده‌اند که تنها در طبقات مشخصی توقف داشته باشند؛ مثلا تعدادی تنها در طبقات زوج و تعدادی دیگر تنها در طبقات فرد. دکمه‌های داخل آسانسور و کنار ورودی آسانسور نیز تنها برای همین طبقات از پیش مشخص شده فعال هستند.

مسئله دوستان خوب

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

مسئله حداکثر مجموع

ماتریس مربعی با ابعاد $N$ در $N$ و درایه‌هایی از اعداد صحیح موجود است. منظور از زیرماتریس بیشینه، زیرماتریسی از ماتریس مفروض است که مجموع عناصر آن بزرگتر یا مساوی مجموع عناصر هر زیرماتریس دیگر آن است.

به عنوان مثال، برای ماتریس زیر:

  

مسئله چراغ راهنمایی

یک چراغ راهنمایی در مسیر گردش از بزرگراه به یک مرکز فروش بزرگ تعبیه شده است. عملکرد این چراغ به گونه‌ای است که در هر دقیقه حداکثر k خودرو امکان گردش از بزرگراه به سمت مسیر مرکز را دارند. در پایان هفته شهروندان بیشتری برای خرید به این مرکز مراجعه می‌کنند که باعث بالا رفتن حجم ترافیک می‌شود. مدیران مرکز سفارش نصب دوربین ویژه‌ای در نزدیکی آن محل را داده‌اند که امکان شمارش تعداد خودروهای وارد شده از سمت شهر به محل گردش به مرکز فروش را دارد.

مسئله Simple Addition

تابع بازگشتی (F(n با تعریف زیر مفروض است:

  

\[ F(n)= \left\{\begin{matrix} n \% 10 & & & if \; (n\%10) > 0\\ 0 & & & if \; n = 0 \\ F(n/10) & & & Otherwise \end{matrix}\right. \]

مسئله مربی ناامید

یکی از تیم‌های لیگ برتر فوتبال (جام خلیج فارس) امسال نتایج خیلی بدی گرفته است. هیئت مدیره باشگاه برای اخراج مربی تحت فشار هستند. اما این مربی از سوی طرفداران تیم به عنوان یک قهرمان محبوب حمایت می‌شود. به همین دلیل تصمیم می‌گیرند یک فرصت دیگر به مربی بدهند. سخنگوی باشگاه به رسانه‌ها اعلام می‌کند که هیئت مدیره باشگاه تنها زمانی از مربی حمایت می‌کنند که بتواند در 5 بازی آینده 11 امتیاز برای تیمشان کسب کند.