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

نوشته‌های یک علاقه‌مند به حوزه‌های برنامه‌نویسی، الگوریتم، حل مسئله و ریاضیات دوست داشتنی

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

نمونه سوال مسابقه ACM

»
✤   مسئله‌ی آتش‌سوزی در برره

مسئله

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

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

ادامه ...
✤   مسئله‌ی Jolly Jumpers

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

1  4  2  3

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

  

ورودی برنامه

هر خط ورودی برنامه با عدد $n$ (کمتر از 3000) آغاز و پس از آن $n$ عدد دنباله می‌آیند.

ادامه ...
✤   مسئله‌ی The Trip

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

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

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

ادامه ...
✤   مسئله‌ی 3n+1 Problem

الگوریتمی را در نظر بگیرید که با دریافت یک عدد $n$، دنباله‌ای از اعداد را تولید می‌کند. به این ترتیب که اگر $n$ زوج بود، تقسیم آن بر عدد 2 و اگر فرد بود، $ 3n + 1 $ را به عنوان جمله‌ی بعدی دنباله و مقدار جدید برای $n$ تولید کرده و عملیات را تا زمانی که مقدار $n$ برابر 1 شود، ادامه دهد. برای مثال، دنباله‌ی زیر با شروع از $ n = 22 $ تولید می‌شود:

\[ 22 \; 11 \; 34 \; 17 \; 52 \; 26 \; 13 \; 40 \; 20 \; 10 \; 5 \; 16 \; 8 \; 4 \; 2 \; 1 \]

حدس زده شده است که چنین دنباله‌ای به ازای هر عدد صحیح $n$ در نهایت به عدد 1 ختم خواهد شد. این حدس حداقل برای اعداد کمتر از 1000000 صحیح است.

ادامه ...
✤   مسئله‌ی Encrypted SMS

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

روش multi-tap در حال حاضر (سال ۲۰۰۷) رایج‌ترین روش ورودی گوشی‌های تلفن است که فشار دادن یک یا چند باره‌ی یک کلید خاص، حرف مورد نظر ما را تولید می‌کند. به عنوان مثال، حروف B ،A و C به ترتیب با یک، دو و سه بار فشار دادن کلید 2 به دست می‌آیند.

ادامه ...
✤   مسئله‌ی Gholam's Simple Game

کف اتاق خواب غلام با کاشی‌های سفید و زرد پوشیده شده است. گاهی که حوصله ندارد، روی یکی از کاشی‌ها می‌ایستد و در آن ردیف از کاشی‌ها قدم می‌زند. او ابتدا عدد $n$ را انتخاب می‌کند و تنها $n$ قدم حرکت می‌کند. اگر در حین حرکت به دیوار برسد، چرخیده و در جهت خلاف به حرکت خود ادامه می‌دهد. توجه داشته باشید که خود عمل چرخش گام حساب نمی‌شود. در حین قدم زدن (یک کاشی در هر قدم) او تعداد دفعاتی که پا روی کاشی زرد گذاشته را می‌شمارد.

برای مثال، شکل زیر یک ردیف از کاشی‌های اتاق را نشان می‌دهد. رنگ کاشی‌ها با حروف 'W' و 'Y' مشخص شده‌اند که به ترتیب به معنی رنگ سفید و زرد هستند. اگر او از کاشی شماره‌ی 3 شروع کرده و تصمیم داشته باشد 7 قدم به سمت راست حرکت کند، در نهایت روی کاشی شماره‌ی 2 متوقف شده و 3 بار روی کاشی‌های زرد پا می‌گذارد.

ادامه ...
✤   مسئله‌ی What Base Is This

می‌دانیم که جایگاه رقم در یک عدد، وزن آن را در مقدار عدد مشخص می‌کند. برای مثال، عدد 362 در مبنای 10 از رقم 2‌ با وزن $10^0$، رقم 6 با وزن $10^1$ و رقم 3 با وزن $10^2$ به صورت $ 3 \times 10 ^ 2 + 6 \times 10 ^ 1 + 2 \times 10 ^ 0 $ یا $ 300 + 60 + 2 $ تشکیل شده است. چنین ساختاری برای نمایش اعداد در سایر مبناها نیز وجود دارد.

اگرچه عموم مردم تصور می‌کنند اعداد مورد استفاده‌ی آنها تنها در مبنای 10 تعریف شده‌اند، اما ما می‌دانیم که نمایش در سایر مبناها نیز امکانپذیر است. مثلا عدد 362 نمایش متفاوتی در مبناهای 9 یا 14 دارد.

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

مسئله

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

با در اختیار داشتن احتمال پیروزی جناب خان در هر ایالت، احتمال پیروزی وی در انتخابات را محاسبه کنید.

ادامه ...
✤   مسئله‌ی آسانسورها

مسئله

ساختمان جدید دپارتمان مهندسی کامپیوتر تنها شامل آسانسور بوده و پله ندارد. برای دسترسی سریع و مناسب به اتاق‌ها و کلاس‌های طبقات مختلف، آسانسورها به گونه‌ای تنظیم شده‌اند که تنها در طبقات مشخصی توقف داشته باشند؛ مثلا تعدادی تنها در طبقات زوج و تعدادی دیگر تنها در طبقات فرد. دکمه‌های داخل آسانسور و کنار ورودی آسانسور نیز تنها برای همین طبقات از پیش مشخص شده فعال هستند. این ایده دسترسی سریع و مناسب به طبقات ساختمان را برای برخی افراد فراهم می‌کند. به عنوان نمونه اعضای هیئت علمی دسترسی مستقیم به طبقات اتاق‌های خود دارند. اما در حالت کلی باعث سردرگمی می‌شود. اگر شخصی بخواهد از طبقه‌ای به طبقه‌ی دیگری برود، ممکن است هیچ آسانسوری در هر دوی آنها توقف نداشته باشد و شخص مجبور به تعویض آسانسور گردد. در چنین شرایطی این سوال پیش می‌آید که کدام آسانسور (یا آسانسورها) باید انتخاب شوند و کدام انتخاب‌ها شخص را در زمان کمتری به مقصد می‌رساند. اگر مسیر حرکت شخص از طبقه‌ی 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% خواهد بود.

ادامه ...
کمی آمار
  • عمر سایت:  ۴۵۷۱ روز
  • تعداد امتیاز ثبت شده:  ۳۲۷۵ امتیاز
  • میانگین امتیازها:  ۴.۲۵ از ۵.۰۰
  • بازدید امروز:  ۲۸۳ بازدید
  • بازدید ۲۴ ساعت گذشته:  ۱۰۸۴ بازدید
  • بازدید ۷ روز گذشته:  ۸۴۷۹ بازدید
  • بازدید ۳۰ روز گذشته:  ۳۷۵۳۲ بازدید
  • بازدید ۱ سال گذشته: ۴۲۲۱۳۹ بازدید
  • کل بازدیدها: ۴۸۱۴۴۸۵ بازدید
برچسب‌ها
#آمادگی مسابقه برنامه‌نویسی  #آموزش الگوریتم  #مسئله‌های الگوریتمی  #برنامه‌نویسی ++C  #الگوریتم  #نمونه سوالات مسابقه برنامه‌نویسی  #حل مسئله‌‌ی الگوریتمی  #برنامه‌نویسی  #منبع آموزشی  #حل سوالات مسابقات برنامه‌نویسی  #الگوریتم‌های تقسیم و غلبه  #نمونه سوال مسابقه ACM  #الگوریتم‌های برنامه‌نویسی پویا  #الگوریتم‌های بازگشتی  #کتاب الکترونیکی  #آموزش ساختمان داده‌ها  #تکنیک‌های طراحی الگوریتم  #محاسبات ریاضی  #گراف  #دانلود کتاب  #حل سوالات ACM-ICPC  #الگوریتم‌های مرتب‌سازی  #سوالات مسابقات ACM-ICPC  #Python  #پیمایش گراف  #ساختمان داده  #کتاب مسابقات برنامه‌نویسی  #الگوریتم‌های گراف  #حل سوالات UVa Online Judge  #الگوریتم‌های مسیریابی  #الگوریتم‌های حریصانه  #درخت‌ها  #سوالات UVa Online Judge  #جستجوی اول سطح  #ماتریس  #الگوریتم‌های کوتاهترین مسیر  #درخت پوشا  #الگوریتم دایکسترا  #ویدئوی آموزشی  #معرفی وب‌سایت  #الگوریتم فلوید-وارشال  #مسئله‌ی کوله‌پشتی  #جستجوی اول عمق  #کتابخانه قالب استاندارد ++C  #صف  #سوالات مسابقات برنامه‌نویسی بیان  #الگوریتم‌های عقبگرد  #حل سوالات Timus Online Judge