المپدیا

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

ابزار کاربر

ابزار سایت


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

هپید و خیکول

روزی قهرمانان دوره‌ی ‎$17$‎ام و ‎$18$‎ام المپیاد کامپیوتر ، یکدیگر را در کلاس درس در دانشگاه تنها یافتند. از آنجا که همیشه بین این دو شخصیت یعنی هپید ‎)‎قهرمان دوره‌ی $17$) و خیکول‎ (قهرمان دوره‌ی $18$)‎ رقابت بوده باز هم در این زمان رقابت به اوج خود می‌رسد‎. ‎ خیکول به هپید پیشنهاد شرکت در یک را مسابقه می‌دهد اما هپید کلی کار دارد ولی مجبور می‌شود به خاطر حفظ آبرو این پیشنهاد را قبول کند. خیکول مسابقه را به هپید به شکل زیر شرح می‌دهد‎:‎

‎$n$‎ عدد صحیح روی تخته پشت سر هم می‌نویسم. تو در هر مرحله می‌توانی دو عدد مجاور را انتخاب کنی و آن‌ها را پاک کنی و به جای آنها یا جمع دو عدد را بنویسی یا عدد راست را از عدد چپ کم کنی و بنویسی. اگر از عملیات جمع استفاده کنی ‎$A$‎ امتیاز می‌گیری و اگر از عملیات تفریق استفاده کنی ‎$B$‎ امتیاز می‌گیری. تو باید طوری عملیات را انتخاب کنی تا در نهایت اگر فقط یک عدد روی تخته باقی‌مانده بود، این عدد بین ‎$p$‎ و ‎$q$‎ نباشد‎.‎

در همان لحظه استاد از راه می‌رسد و بحث قطع می‌شود، اما هپید برای گرفتن حال خیکول، سریعا اعداد را از روی تخته به دفتر خود منتقل می‌کند. هپید که در حال برگزاری امتحانات عملی دوره تابستانی بود، فرصت را غنیمت شمارد و این سوال را به عنوان سوال عملی امتحان قرار داد. به هپید کمک کنید تا بیشترین امتیاز ممکن را کسب کند.‎

ورودی

  • در خط اول ورودی به شما عدد ‎$n$‎ داده می‌شود و به دنبال آن ‎$p$‎ و سپس ‎$q$‎، پس از آن ‎$B$‎ و سپس ‎$A$‎ می‌آید‎.‎
  • در خط دوم ورودی ‎$n$‎ عدد صحیح آمده است.
  • ‎$2 \leq n \leq 60$
  • قدر مطلق اعداد روی تخته از ‎$10^6+1$‎ کوچک‌تر است‎.‎
  • ‎$-2^{28} \leq p \leq q \leq 2^{28}$
  • در ‎$10$‎ درصد از بسته تست‌ها می‌دانیم ‎$n \leq 10$‎ می‌باشد‎.‎

خروجی

در خروجی اگر هیچ دنباله‌ای از حرکات نبود که عدد نهایی در ‎$[p,q]$‎ نباشد کلمه‌ی ‎impossible‎ را چاپ کنید و در صورت وجود جواب، بیشترین امتیازی را که هپید می‌تواند کسب کند را در خروجی بنویسید.

محدودیت‌ها

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

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

ورودی نمونه خروجی نمونه
2 2 2 1 2‎
1 1‎
1
‎2 0 0 1 2‎
1 1‎
2
‎2 0 2 1 2‎
1 1‎
impossible

ابزار صفحه