بستن پنجره
فرادرس - مجموعه آموزش‌های ویدئویی  مهندسی کامپیوتر - طراحی الگوریتم - ساختمان داده
بستن پنجره     از آخرین نوشته‌ها

»    مسابقه‌ی برنامه‌نویسی آنلاین 20 Quera

»    دوره‌ی طراحی و تحلیل الگوریتم دانشگاه استنفورد

»    مسأله‌ی انتخابات

بستن پنجره
وبگاه
این صفحه
اشتراک‌گذاری در LinkedIn     Cloob     اشتراک‌گذاری در Twitter
اشتراک‌گذاری در Facebook     ارسال با Telegram     Google Plus
بستن پنجره
وبگاه     این صفحه
اشتراک‌گذاری در LinkedIn     Cloob     اشتراک‌گذاری در Twitter     اشتراک‌گذاری در Facebook     ارسال با Telegram     Google Plus
مسأله‌ی تاریخچه‌ی جدول - الگوریتمستان
الگوریتمستان
213.005.00
  »  

       

بررسی مسأله‌ی تاریخچه‌ی جدول (Grid History)، از سوالات مسابقات برنامه‌نویسی بیان

آنچه در این نوشته می‌خوانید:
   •  مسأله‌ی تاریخچه‌ی جدول
       »  مسأله
       »  ورودی برنامه
       »  خروجی برنامه
       »  حل مسأله

مسأله

  [بازگشت به فهرست]

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

    به شما عکسی از اعداد نوشته شده در جدول داده شده است. آیا حامد اعداد روی جدول را به درستی نوشته است؟

      

ورودی برنامه

  [بازگشت به فهرست]

در سطر اول ورودی عدد T ($ 1 \leq T \leq 100 $) ، تعداد تست‌ها آمده است. پیش از هر تست یک سطر خالی آمده است.

    برای هر تست در یک سطر ورودی اعداد n ($ 2 \leq n \leq 50 $) ، تعداد سطرها، و m ($ 2 \leq m \leq 50 $) ، تعداد ستون‌ها، را بخوانید. در n سطر بعدی اعداد نوشته شده در جدول آمده که هر سطر شامل m ستون است. اعداد نوشته شده در جدول نابیشتر از $ 10^9$ هستند.

      

3

  

2    2

4    11

7    12

  

2    2

4    7

10    8

  

2    3

2    13    11

17    18    8

      

خروجی برنامه

  [بازگشت به فهرست]

به ازای هر تست، ابتدا یک سطر شامل ":Case #x" بنویسید که در آن x نشان‌دهنده‌ی شماره‌ی تست است، با شروع از 1. در صورتی که حامد در طول مسیر اعداد را به درستی یادداشت کرده است "YES" و در غیر اینصورت "NO" را در یک سطر بنویسید.

      

Case #1:

YES

Case #2:

NO

Case #3:

NO

      

    منبع: مرحله‌ی انتخابی مسابقات برنامه‌نویسی بیان 1393، مسأله‌ی تاریخچه‌ی جدول (Grid History)

      

حل مسأله

  [بازگشت به فهرست]

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

(1,1) (1,2) (2,2) (1,2) (2,2) (2,1)

    و

(1,1) (2,1) (2,2) (1,2) (2,2) (2,1)

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

    اعداد جدول ورودی را به صورت مرتب شده در نظر بگیرید که دنباله‌ی حاصل با $ A_i $ و خانه‌ی متناظر هر $ A_i $ با $ L_i $ مشخص شده‌اند $(i=1,2,3, \cdots, n \times m)$. بر اساس مفاهیم ورودی مسأله، هیچ اطلاعی از حرکت‌های قبل از ورود به خانه‌ی $ L_1 $ (حرکت‌های قبل از $A_1$) وجود نداشته و بحث در مورد آنها نیز اهمیتی ندارد (چرا؟)؛ اما مستقل از این حرکت‌ها و این که شروع حرکت از چه خانه‌ای بوده است، باید بتوان مسیری از هر $L_i$ (با مقدار $A_i$) به $L_{i+1}$ (با مقدار $A_{i+1}$) یافت که مقدار عدد خانه‌های مسیر بزرگتر از $A_i$ باشند. اگر جدول ورودی را به صورت یک گراف جهت‌دار (چرا جهت‌دار؟) در نظر بگیریم که از هر خانه به عنوان گره گراف توسط یال‌هایی به خانه‌های مجاور خود متصل هستند، یافتن مسیر از $L_i$ به $L_{i+1}$ تبدیل به یافتن کوتاهترین مسیر در گراف متناظر آن می‌شود. خروجی این مسیریابی می‌تواند یکی از سه حالت زیر باشد:

    1- مسیری بین $L_i$ و $L_{i+1}$ وجود ندارد.

    2- کوتاهترین مسیر بین $L_i$ و $L_{i+1}$ با طول بزرگتر از $A_{i+1} - A_i $ است.

    3- کوتاهترین مسیر بین $L_i$ و $L_{i+1}$ با طول نابیشتر از $A_{i+1} - A_i$ است.

    برقرار بودن دو حالت اول به ازای حتی یک جفت $L_i$ و $L_{i+1}$ به معنی نادرست بودن اعداد ثبت شده در جدول بوده و باید خروجی NO چاپ شود. اگر به ازای هر جفت $L_i$ و $L_{i+1}$ حالت سوم برقرار باشد، به معنی درست بودن اعداد جدول بوده و باید خروجی YES چاپ شود.

    در پیاده‌سازی الگوریتم ارائه شده باید به دو نکته‌ی مهم توجه داشت:

    1- خانه‌ای با بزرگترین شماره (خانه‌ی بیشینه) همواره باید خانه‌ای با یک واحد کمتر از مقدار بیشینه را در مجاورت خود داشته باشد (چرا؟). بنابراین اگر خانه‌ای با مقدار یک واحد کمتر از خانه‌ی بیشینه در جدول وجود نداشته یا در مجاورت آن خانه نباشد، جدول حتما به نادرستی پر شده است. اگر این شرط بررسی نگردد، خروجی نمونه‌ی دوم ورودی مسأله YES خواهد شد که نادرست است.

    2- اگر شماره‌ی خانه‌ای زوج باشد، هر حرکت به چهار خانه‌ی مجاور مقدار آن خانه را فرد می‌کند. به همین ترتیب با هر حرکت از خانه با شماره‌ی فرد، یک عدد زوج در خانه‌ی بعدی نوشته می‌شود. بر اساس این استدلال خانه‌های مجاور نمی‌توانند هر دو زوج یا هر دو فرد باشند. پس شرط لازم درستی جدول (و نه شرط کافی) آن است که هیچ دو خانه‌ی مجاور جدول هر دو زوج یا هر دو فرد نباشند. برای اعمال این شرط در الگوریتم نیازی به بررسی برقراری آن به ازای هر خانه به صورت قطعه کد جداگانه نیست؛ بلکه کافی است در زمان محاسبه‌ی کوتاهترین مسیر بین دو خانه‌ی $L_i$ و $L_{i+1}$ (در صورت وجود) بررسی گردد که مجموع طول کوتاهترین مسیر و مقدار دو خانه (یعنی $L_i+L_{i+1}$) زوج باشد (چرا؟). اگر این شرط بررسی نگردد، خروجی نمونه‌ی سوم ورودی مسأله YES خواهد شد که نادرست است.

    متناسب با الگوریتم مرتب‌سازی و الگوریتم یافتن کوتاهترین مسیر استفاده شده برای پیاده‌سازی این راهکار، پیچیدگی زمانی اجرای الگوریتم در بدترین شرایط ممکن است از مرتبه‌ای مانند $ O(n^4) $ باشد که مرتبه‌ی قابل قبولی به نظر نمی‌رسد. اما با توجه به محدودیت مقادیر n و m‌ (نابیشتر از 50)، الگوریتم حتی با چنین مرتبه‌ای در زمان مطلوبی به جواب می‌رسد. اگرچه امکان پیاده‌سازی الگوریتم با مرتبه‌ی پایین‌تر نیز وجود دارد.

    نکته: با توجه به اینکه وزن تمامی یال‌ها یکسان است می‌توان از الگوریتم جستجوی اول سطح (BFS) نیز برای یافتن کوتاهترین مسیر استفاده کرد.


این نوشته آخرین بار در تاریخ پنجشنبه، ۱۰ فروردین ماه ۱۳۹۶ مورد بازنویسی نگارشی قرار گرفته است.
نوشته‌های مرتبط
        متن فارسی مسأله‌ی Jolly Jumpers از سوالات تمرینی کتاب‌های آمادگی مسابقات برنامه‌نویسی و وبسایت UVa Online Judge
        متن فارسی مسأله‌ی Gholam's Simple Game از سوالات مسابقه‌ی برنامه‌نویسی ACM-ICPC 2010‌ منطقه‌ای سایت تهران
        مستندات دوره‌ی Introduction to Programming Contests دانشگاه استنفورد با موضوع ریاضیات، ساختمان داده‌ها و الگوریتم‌های مورد نیاز برای شرکت در مسابقات برنامه‌نویسی
        راه حل سوالات مسابقه‌ی جهانی ACM-ICPC 2016
        متن فارسی مسأله‌ی The Trip از سوالات تمرینی کتاب‌های آمادگی مسابقات برنامه‌نویسی و وبسایت UVa Online Judge
        متن فارسی مسأله‌ی شماره‌ی 343 از UVa Online Judge، ار سوالات تمرینی کتاب‌های آمادگی مسابقات برنامه‌نویسی
        متن فارسی مسأله‌ی 3n+1 Problem (حدس کولاتز یا حدس 3n+1) از سوالات تمرینی کتاب‌های آمادگی مسابقات برنامه‌نویسی و وبسایت UVa Online Judge
        ویدئوهای آموزشی کلاس Programming Challenges شامل مباحث الگوریتم‌ها، ساختمان داده‌ها و ریاضیات محاسباتی برای آمادگی مسابقات برنامه‌نویسی
        متن فارسی مسأله‌ی Encrypted SMS از سوالات مسابقه‌ی برنامه‌نویسی ACM-ICPC 2007 منطقه‌ای سایت تهران
        بررسی مسأله‌ی انتخابات، از سوالات مسابقه‌ی برنامه‌نویسی ACM-ICPC 2016 سایت تهران
پیوند کوتاه صفحه دسته‌بندی
امتیاز نوشته
  • 1
  • 2
  • 3
  • 4
  • 5
ارسال پیام

نام: *  

پست الکترونیک:

وبگاه:

متن پیام: *

right 01 02 03 04 05 06 07 08 09 10 11 12 13 14 left