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

برنامه‌نویسی، طراحی الگوریتم و حل مسئله‌های الگوریتمی

 
در صورت ناخوانا بودن نوشته‌ها، از مرورگر دیگری استفاده کنید.
نوشته‌ها با برچسب سوالات مسابقات ACM-ICPC نوشته‌ها با برچسب سوالات مسابقات ACM-ICPC - الگوریتمستان الگوریتمستان الگوریتمستان
نوشته‌ها با برچسب «

سوالات مسابقات ACM-ICPC

»

مسئله

رابطه‌ی جمع زدن دو عدد را در نظر بگیرید:

مسئله‌ی Column Addition

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

ادامه ...

مسئله

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

روستا را به صورت شبکه‌ای با ابعاد $ n \times m $ در نظر بگیرد که برخی خانه‌های آن در آغاز آتش گرفته‌اند و اگر خانه‌ای در زمان $x$ آتش گرفته باشد، هشت خانه‌ی مجاور آن در زمان $ x + k$ آتش خواهند گرفت و هرگز خاموش نمی‌شوند. حال اگر خرزو خان در نقطه‌ی $s$ شبکه باشد، می‌تواند در هر ثانیه به یکی از چهار خانه‌ی مجاور بالا، پایین، راست یا چپ خود برود و تلاش کند به نقطه‌ی $t$ که هلیکوپتر در آن قرار دارد برسد.

ادامه ...

مسئله

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

ادامه ...

مسئله

ساختمان جدید دپارتمان مهندسی کامپیوتر تنها شامل آسانسور بوده و پله ندارد. برای دسترسی سریع و مناسب به اتاق‌ها و کلاس‌های طبقات مختلف، آسانسورها به گونه‌ای تنظیم شده‌اند که تنها در طبقات مشخصی توقف داشته باشند؛ مثلا تعدادی تنها در طبقات زوج و تعدادی دیگر تنها در طبقات فرد. دکمه‌های داخل آسانسور و کنار ورودی آسانسور نیز تنها برای همین طبقات از پیش مشخص شده فعال هستند. این ایده دسترسی سریع و مناسب به طبقات ساختمان را برای برخی افراد فراهم می‌کند. به عنوان نمونه اعضای هیئت علمی دسترسی مستقیم به طبقات اتاق‌های خود دارند. اما در حالت کلی باعث سردرگمی می‌شود. اگر شخصی بخواهد از طبقه‌ای به طبقه‌ی دیگری برود، ممکن است هیچ آسانسوری در هر دوی آنها توقف نداشته باشد و شخص مجبور به تعویض آسانسور گردد. در چنین شرایطی این سوال پیش می‌آید که کدام آسانسور (یا آسانسورها) باید انتخاب شوند و کدام انتخاب‌ها شخص را در زمان کمتری به مقصد می‌رساند. اگر مسیر حرکت شخص از طبقه‌ی i به طبقه‌ی j به صورت $ i = f_1 \rightarrow f_2 \rightarrow f_3 \rightarrow \cdots \rightarrow f_k = j $ نمایش داده شود، عبارت $ \sum_{r=1}^{k-1} \vert f_i - f_{i+1} \vert $ زمان لازم برای رسیدن به مقصد از طریق آن مسیر است. برنامه‌ای بنویسید که افراد را در استفاده‌ی بهتر (در زمان کمتر) از آسانسورها یاری کند.

ادامه ...

مسئله

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

  

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

  

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

با توجه به موقعیت دو دوست در این ساختار، هدف یافتن حداقل گام‌های مورد نیاز برای رسیدن دو دوست به یک خانه است. توجه داشته باشید که محل اولیه‌ی دو دوست لزوما متمایز نبوده و در کل مراحل یک دوست در محل خود ثابت مانده و دوست دیگر حرکت می‌کند.

ادامه ...

مسئله

یکی از تیم‌های لیگ برتر فوتبال (جام خلیج فارس) امسال نتایج خیلی بدی گرفته است. هیئت مدیره‌ی باشگاه برای اخراج مربی تحت فشار هستند. اما این مربی از سوی طرفداران تیم به عنوان یک قهرمان محبوب حمایت می‌شود. به همین دلیل تصمیم می‌گیرند یک فرصت دیگر به مربی بدهند. سخنگوی باشگاه به رسانه‌ها اعلام می‌کند که هیئت مدیره‌ی باشگاه تنها زمانی از مربی حمایت می‌کنند که بتواند در 5 بازی آینده 11 امتیاز برای تیمشان کسب کند. مربی می‌خواهد بداند چقدر احتمال دارد به این موفقیت دست پیدا کند و از شما کمک می‌خواهد.فرض کنید احتمال کسب برد، باخت و تساوی در مسابقه‌های بعدی از روی مسابقات انجام شده تا به حال به دست می‌آید. به عنوان مثال اگر این تیم از 10 بازی انجام داده‌ی قبلی 3 برد داشته باشد، احتمال برد در آینده 30% خواهد بود.

ادامه ...

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

   

 

پیوند کوتاه:
»  راه حل سوالات مسابقه‌ی جهانی ACM-ICPC 2016
راه حل سوالات مسابقه‌ی جهانی ACM-ICPC 2016
برچسب‌ها
#نمونه سوالات مسابقه برنامه‌نویسی #کتاب مسابقات برنامه‌نویسی #الگوریتم‌های بازگشتی #حل سوالات ACM-ICPC #نمونه سوال فارسی مسابقه‌ی ACM #الگوریتم‌های عقبگرد #مسئله‌های الگوریتمی #ترجمه فارسی سوالات کتاب Programming Challenges #آمادگی المپیاد کامپیوتر #مسابقه برنامه نویسی #ساختمان داده #مسئله‌ی کوله‌پشتی #الگوریتم‌های برنامه‌نویسی پویا #ویدئوی آموزشی #نمونه سوال مسابقه ACM #آمادگی مسابقه ACM #سوالات برنامه‌نویسی #آموزش الگوریتم #برنامه‌نویسی #سوالات مسابقات برنامه‌نویسی بیان #آموزش برنامه‌نویسی ++C #الگوریتم فلوید-وارشال #درخت پوشا #الگوریتم‌های مرتب‌سازی #تمرین مسابقه برنامه‌نویسی #کتابخانه قالب استاندارد ++C #الگوریتم #الگوریتم‌های حریصانه #صف #منبع آموزشی #الگوریتم‌های تقسیم و غلبه #درخت‌ها #نکات برنامه‌نویسی #الگوریتم دایکسترا #معرفی وب‌سایت #مسئله‌های برنامه‌نویسی #مسابقات برنامه‌نویسی ACM #حل سوالات UVa Online Judge #پیمایش گراف #مسابقات برنامه‌نویسی #محاسبات ریاضی #مسابقه برنامه‌نویسی #تمرین طراحی الگوریتم #کتاب الکترونیکی #جستجوی اول عمق #سوالات UVa Online Judge #برنامه‌نویسی ++C #حل مسئله‌‌ی الگوریتمی #مسأله‌های برنامه‌نویسی #حل سوالات Timus Online Judge #ترجمه‌ی فارسی سوالات ACM #تمرین المپیاد کامپیوتر #حل سوالات مسابقات برنامه‌نویسی #نمونه سوال فارسی مسابقات ACM #الگوریتم‌های کوتاهترین مسیر #نمونه سوال فارسی مسابقات برنامه‌نویسی #کتاب الگوریتم #گراف #ترجمه‌ی فارسی سوالات UVa Online Judge #تمرین مسابقه‌ی برنامه‌نویسی ای‌سی‌ام #آموزش طراحی الگوریتم #آموزش ساختمان داده‌ها #ترجمه‌ی فارسی سوالات برنامه‌نویسی #مسأله‌های الگوریتمی #دانلود کتاب #وبلاگ #آمادگی مسابقه برنامه‌نویسی #Python #الگوریتم‌های مسیریابی #الگوریتم‌های گراف #سوالات چالشی برنامه‌نویسی #جستجوی اول سطح #ماتریس #سوالات مسابقات ACM-ICPC #تکنیک‌های طراحی الگوریتم