مسئله‌ی Turn the Lights Off [برو به فهرست نوشته‌ها] متن فارسی و روش حل مسئله‌ی Turn the Lights Off از سوالات وبسایت UVa Online Judge مسئله صفحه‌ای مشبک با ابعاد 10 در 10 وجود دارد که هر خانه شامل یک لامپ و یک کلید برای روشن یا خاموش کردن لامپ است. اما این کلیدها رفتار عادی ندارند و فشار دادن هر کدام، نه تنها لامپ همان خانه که لامپ خانه‌های بالا، پایین، راست و چپ آن خانه را - در صورت وجود - تغییر وضعیت می‌دهد.ادامه ...
مسئله‌ی انتخابات [برو به فهرست نوشته‌ها] بررسی مسئله‌ی انتخابات، از سوالات مسابقه‌ی برنامه‌نویسی ACM-ICPC 2016 سایت تهران مسئله جناب خان که با کسب و کار لبوی خود میلیاردر شده است، می‌خواهد رئیس جمهور شود! در کشور او که از چندین ایالت تشکیل شده است، از روشی با عنوان هیئت انتخاب (یا هیئت الکترال) برای انتخاب رئیس جمهور استفاده می‌شود. در چنین ساختاری شمارش رأی در هر ایالت به صورت مستقل انجام می‌شود و هر ایالت متناسب با جمعیت خود تعدادی نماینده در هیئت انتخاب کنندگان رئیس جمهور دارد. تمام نمایندگان یک ایالت در نهایت به نامزدی رأی می‌دهند که در آن ایالت اکثریت آرا را کسب کرده باشد. اگر نامزدها رأی برابر داشته باشند، هر ایالت قوانین خاص خود برای انتخاب نهایی را دارد. در نهایت رئیس جمهور کسی است که بیش از نصف مجموع رأی‌های هیئت انتخاب را از آن خود کند.ادامه ...
مسئله‌ی اعداد اردوش [برو به فهرست نوشته‌ها] بررسی مسئله‌ی اعداد اردوش (Erdos Numbers) یا فاصله‌ی همکاری اردوش از سوالات آمادگی مسابقات برنامه‌نویسی موجود در کتاب Programming Challenges و وبسایت UVa Online Judge مسئله پل اردوش (اردیش - Paul Erdős) ریاضیدان مشهور و برجسته‌ی قرن بیستم است که تا پایان عمر خود تلاش گسترده‌ای برای انتشار مقالات علمی داشت و همکاری با وی در انتشار مقاله یک افتخار بزرگ برای هر ریاضیدان محسوب می‌گردد.ادامه ...
مسئله‌ی بشکه‌های آب [برو به فهرست نوشته‌ها] بررسی مسئله‌ی بشکه‌های آب (Water Barrels)، از سوالات مسابقات برنامه‌نویسی بیان مسئله $n$ بشکه‌ی آب با تعدادی لوله به هم وصل شده‌اند. هر بشکه استوانه‌ای عمودی با سطح مقطع یک متر مربع و ارتفاع نامحدود است که با عدد یکتا بین 1 تا $n$ شماره‌گذاری شده است. $i$-امین لوله بشکه‌ی $ x_i $ و $y_i$ را به هم متصل می‌کند. یک سر این لوله در ارتفاع $h_i$ متر به بشکه‌ی $ x_i $ متصل است و سر دیگر آن در همان ارتفاع به بشکه‌ی $y_i$ متصل است. در زمان صفر بشکه‌ها خالی هستند و یک جریان آب به صورت پیوسته با سرعت یک متر مکعب بر ساعت در بشکه‌ی شماره‌ی یک می‌ریزد. اگر آب بشکه‌ای به ارتفاع لوله‌ای برسد، آب در لوله جریان پیدا می‌کند و می‌تواند وارد بشکه‌ی دیگر شود. فرض کنید قطر لوله‌ها ناچیز است و سرعت آب در لوله‌ها بسیار زیاد است.ادامه ...
مسئله‌ی تاریخچه‌ی جدول [برو به فهرست نوشته‌ها] بررسی مسئله‌ی تاریخچه‌ی جدول (Grid History)، از سوالات مسابقات برنامه‌نویسی بیان مسئله جدولی با n سطر و m ستون در نظر بگیرید. در تمام خانه‌های این جدول عدد 0 نوشته شده است. در ابتدای کار حامد در خانه‌ای از جدول ایستاده است. او عدد این خانه را پاک می‌کند و عدد 1 را به جای آن می‌نویسد. حامد شروع به حرکت می‌کند و در هر ثانیه یک خانه به بالا، راست، پایین یا چپ می‌رود. او با وارد شدن به هر خانه، عدد نوشته شده در خانه را پاک می‌کند و عددی یک واحد بزرگتر از آخرین عددی که نوشته است را می‌نویسد و بعد از مدتی متوقف می‌شود. می‌دانیم حامد در انتهای حرکت خود تمام خانه‌های جدول را دیده است.ادامه ...
مسئله‌ی آسانسورها [برو به فهرست نوشته‌ها] بررسی مسئله‌ی آسانسورها (Elevators)، از سوالات مسابقات برنامه‌نویسی ACM مسئله ساختمان جدید دپارتمان مهندسی کامپیوتر تنها شامل آسانسور بوده و پله ندارد. برای دسترسی سریع و مناسب به اتاق‌ها و کلاس‌های طبقات مختلف، آسانسورها به گونه‌ای تنظیم شده‌اند که تنها در طبقات مشخصی توقف داشته باشند؛ مثلا تعدادی تنها در طبقات زوج و تعدادی دیگر تنها در طبقات فرد. دکمه‌های داخل آسانسور و کنار ورودی آسانسور نیز تنها برای همین طبقات از پیش مشخص شده فعال هستند. این ایده دسترسی سریع و مناسب به طبقات ساختمان را برای برخی افراد فراهم می‌کند. به عنوان نمونه اعضای هیئت علمی دسترسی مستقیم به طبقات اتاق‌های خود دارند. اما در حالت کلی باعث سردرگمی می‌شود. اگر شخصی بخواهد از طبقه‌ای به طبقه‌ی دیگری برود، ممکن است هیچ آسانسوری در هر دوی آنها توقف نداشته باشد و شخص مجبور به تعویض آسانسور گردد. در چنین شرایطی این سوال پیش می‌آید که کدام آسانسور (یا آسانسورها) باید انتخاب شوند و کدام انتخاب‌ها شخص را در زمان کمتری به مقصد می‌رساند. اگر مسیر حرکت شخص از طبقه‌ی 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 $ زمان لازم برای رسیدن به مقصد از طریق آن مسیر است. برنامه‌ای بنویسید که افراد را در استفاده‌ی بهتر (در زمان کمتر) از آسانسورها یاری کند.ادامه ...
مسئله‌ی دوستان خوب [برو به فهرست نوشته‌ها] بررسی مسئله‌ی دوستان خوب، از سوالات مسابقات برنامه‌نویسی ACM مسئله دو دوست در زمین نامحدودی متشکل از حصارهای دایره‌ای شکل هم‌اندازه با ساختار زیر قرار دارند: ادامه ...
مسئله‌ی حداکثر مجموع [برو به فهرست نوشته‌ها] بررسی مسئله‌ی حداکثر مجموع، از سوالات آمادگی مسابقات برنامه‌نویسی مسئله ماتریس مربعی با ابعاد $N$ در $N$ و درایه‌هایی از اعداد صحیح موجود است. منظور از زیرماتریس بیشینه، زیرماتریسی از ماتریس مفروض است که مجموع عناصر آن بزرگتر یا مساوی مجموع عناصر هر زیرماتریس دیگر آن است. به عنوان مثال، برای ماتریس زیر: ادامه ...
مسئله‌ی چراغ راهنمایی [برو به فهرست نوشته‌ها] بررسی سوال مسابقات برنامه‌نویسی Turn for MEGA و راه حل آن مسئله یک چراغ راهنمایی در مسیر گردش از بزرگراه به یک مرکز فروش بزرگ تعبیه شده است. عملکرد این چراغ به گونه‌ای است که در هر دقیقه حداکثر k خودرو امکان گردش از بزرگراه به سمت مسیر مرکز را دارند. در پایان هفته شهروندان بیشتری برای خرید به این مرکز مراجعه می‌کنند که باعث بالا رفتن حجم ترافیک می‌شود. مدیران مرکز سفارش نصب دوربین ویژه‌ای در نزدیکی آن محل را داده‌اند که امکان شمارش تعداد خودروهای وارد شده از سمت شهر به محل گردش به مرکز فروش را دارد. ادامه ...
مسئله‌ی Simple Addition [برو به فهرست نوشته‌ها] بررسی مسئله‌ی 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. \] ادامه ...