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

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

 
در صورت ناخوانا بودن نوشته‌ها، از مرورگر دیگری استفاده کنید.
نوشته‌ها با برچسب حل سوالات 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 #مسابقه برنامه نویسی #صف #وبلاگ #الگوریتم‌های برنامه‌نویسی پویا #آموزش ساختمان داده‌ها #سوالات چالشی برنامه‌نویسی #آموزش طراحی الگوریتم #سوالات UVa Online Judge #برنامه‌نویسی #نمونه سوال مسابقه ACM #مسأله‌های برنامه‌نویسی #حل سوالات Timus Online Judge #حل سوالات ACM-ICPC #Python #آموزش الگوریتم #الگوریتم #مسئله‌های الگوریتمی #الگوریتم‌های بازگشتی #نمونه سوالات مسابقه برنامه‌نویسی #محاسبات ریاضی #برنامه‌نویسی ++C #پیمایش گراف #حل سوالات UVa Online Judge #گراف #معرفی وب‌سایت #مسئله‌ی کوله‌پشتی #مسابقه برنامه‌نویسی #الگوریتم‌های عقبگرد #تمرین طراحی الگوریتم #آموزش برنامه‌نویسی ++C #ترجمه‌ی فارسی سوالات ACM #الگوریتم‌های حریصانه #الگوریتم دایکسترا #درخت‌ها #الگوریتم‌های مرتب‌سازی #الگوریتم‌های تقسیم و غلبه #کتاب مسابقات برنامه‌نویسی #درخت پوشا #مسابقات برنامه‌نویسی #ساختمان داده #سوالات برنامه‌نویسی #تمرین مسابقه‌ی برنامه‌نویسی ای‌سی‌ام #ترجمه فارسی سوالات کتاب Programming Challenges #تمرین المپیاد کامپیوتر #کتاب الگوریتم #آمادگی مسابقه ACM #نمونه سوال فارسی مسابقات برنامه‌نویسی #منبع آموزشی #آمادگی مسابقه برنامه‌نویسی #ترجمه‌ی فارسی سوالات UVa Online Judge #مسئله‌های برنامه‌نویسی #کتابخانه قالب استاندارد ++C #نمونه سوال فارسی مسابقه‌ی ACM #جستجوی اول سطح #تکنیک‌های طراحی الگوریتم #دانلود کتاب #الگوریتم‌های مسیریابی #نمونه سوال فارسی مسابقات ACM #جستجوی اول عمق #ترجمه‌ی فارسی سوالات برنامه‌نویسی #حل مسئله‌‌ی الگوریتمی #سوالات مسابقات ACM-ICPC #تمرین مسابقه برنامه‌نویسی #نکات برنامه‌نویسی #ویدئوی آموزشی #ماتریس #الگوریتم‌های گراف #الگوریتم فلوید-وارشال