المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۱۱:عملی:سوال ۲

تاس خورشیدی

یک جدول مستطیلی $m\times n$‌ از اعداد طبیعی داریم. می‌خواهیم یک تاس را از نقطه‌ی $(a,b)$ جدول، روی اضلاع خانه‌های جدول بغلتانیم و به نقطه $(c,d)$ برسیم. تاس در هر خانه‌ای که قرار بگیرد اگر عدد کف تاس (عددی که روی وجه پایین آن نوشته شده) $x$ و عدد خانه‌ی مورد نظر $y$ باشد جریمه‌ای برابر $(x-y)^2$ به ما تعلق می‌گیرد. می‌خواهیم طوری حرکت کنیم که کم‌ترین جریمه را بپردازیم. (هنگامی که در خانه $(a,b)$ هستیم و همچنین وقتی به خانه‌ی $(c,d)$ می‌رسیم نیز باید جریمه بپردازیم.)

$(1,1)$ خانه‌ی بالا چپ و $(m,n)$ خانه‌ي پایین و راست جدول است. خانه‌ی $(x,y)$ یعنی خانه‌ای که در سطر $x$ ام و ستون $y$ ام قرار دارد.

تاس را طوری می‌توان قرار داد که وجه کف آن ۱، وجه راست آن ۲، وجه جلوی آن ۳، وجه پشت آن ۴، وجه چپ آن ۵ و وجه روی آن ۶ باشد.

ورودی

در خط اول فایل ورودی اعداد $m$ و $n$ ($1 \leq m,n \leq 20$) و در خط دوم $a$ و $b$ و $c$ و $d$ و در خط سوم عدد کف تاس و عدد روی وجه جلوی تاس در زمان شروع حرکت داده شده است. در $m$ خط بعد در هر خط $n$ ‌ عدد داده شده است که سطر $i+3$ ام ورودی، سطر $i$ ام جدول است.

خروجی

در خط اول فایل خروجی حداقل جریمه و $l$ (تعداد خانه‌هایی که از آن‌ها عبور کرده‌اید) را بنویسید. در $l$ سطر بعد (در هر سطر دو عدد) شماره‌ی خانه‌های مسیر را بنویسید.

محدودیت‌ها

  • محدودیت زمان: ۵ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت

ورودی و خروجی نمونه

ورودی نمونه خروجی نمونه
4 4
1 1 3 3
1 3
3 2 6 5
3 2 3 5
6 1 ? 1
6 10 1 6
? 5
1 1
1 2
1 3
2 3
3 3

پاسخ


ابزار صفحه