سوال ۵
می‌خواهیم روباتی سفارش دهیم که قادر باشد از مبدأ مختصات صفحه (مانند شکل) به تمام نقاطی که مختصات صحیح دارند برود. برای این کار روبات باید دارای زیرمجموعه‌ای از قابلیت‌های زیر باشد. قیمت روبات برابر است با مجموع قیمت‌های قابلیت‌هایی که برای آن سفارش می‌دهیم. قیمت هر قابلیت نیز روبه‌روی آن در فهرست زیر درج شده است.
- یک واحد حرکت به راست٬ ۳۰۰۰۰ تومان
- یک واحد حرکت به بالا٬ ۳۰۰۰۰ تومان
- یک واحد حرکت به پایین٬ ۲۰۰۰۰ تومان
- یک واحد حرکت به چپ٬ ۲۰۰۰۰ تومان
- تقارن نسبت به محور $x$٬ ۲۰۰۰۰ تومان $(x,y) \rightarrow (x,-y)$
- تقارن نسبت به محور $y$٬ ۲۰۰۰۰ تومان $(x,y) \rightarrow (-x,y)$
- تقارن نسبت به خط $y=x$٬ ۱۰۰۰۰ تومان $(x,y) \rightarrow (y,x)$
- تقارن نسبت به خط $y=-x$٬ ۱۰۰۰۰ تومان $(x,y) \rightarrow (-y,-x)$
حداقل قیمت روبات را تعیین کنید.
- ۳۰۰۰۰ تومان
- ۴۰۰۰۰ تومان
- ۵۰۰۰۰ تومان
- ۶۰۰۰۰ تومان
- ۷۰۰۰۰ تومان
پاسخ
گزینه‌ی (۲) درست است.
با انتخاب حرکت یک واحد به چپ و دو حرکت تقارنی آخر ( ۲ حرکت ۱۰۰۰۰ تومانی) می توان این کار راانجام داد.
ادعا می کنیم با هزینه ی کمتر این کار قابل انجام نیست. فرض کنید روش عجیبی وجود داشته باشد که با هزینه ای کمتر از ۴۰۰۰۰ بتواند این کار را انجام دهیم. اگر هیچ‌کدام از 4 حرکت اول را انتخاب نکنیم (4 جهت اصلی) روبات همیشه روی مبدا مختصات باقی می‌ماند. اگر حداقل ۲ تا از این حرکات را انتخاب کنیم حداقل باید ۴۰۰۰۰ تا هزینه کنیم. پس در این روش عجیب بایستی دقیقا یکی از ۴ حرکت اول را انتخاب کنیم. هم چنین بایستی غیر از این حرکت حداقل یک حرکت از بین ۴ حرکت آخر (حرکات تقارنی) داشته باشیم زیرا در غیر این صورت نمی توان به نقطه ی (۱و۱) رسید. پس بنابراین روش عجیب شامل دقیقن یکی از حرکات ۱۰۰۰۰ تومانی و دقیقن یکی از ۲ حرکت یک واحد به چپ یا پایین است (زیرا در غیر ای صورت هزینه حداقل ۴۰۰۰۰ خواهد بود). اما با این ۲ حرکت نمی توان به خانه ی (۱و۱) رسید.
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
