این مسابقه جهت آمادگی در مسابقه ACPC برگزار خواهد شد.

میوه‌خوری باستانی


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

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

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

  • هر فرد در نوبت خود، دقت می‌کند در ظرف حریف چند میوه وجود دارد و به تعداد میوه‌های ظرف حریف، از ظرف خود میوه می‌خورد. اگر کسی که نوبتش است به اندازه‌ی کافی میوه در ظرف خود نداشته باشد، تمام میوه‌های ظرف خود را می‌خورد.

مسابقه زمانی تمام می‌شود که میوه‌های یکی از دو ظرف بازیکنان تمام شده باشد. کسی که میوه‌های ظرفش تمام شود می‌بازد.

برای مثال، فرض کنید پیرهرات ظرفی با ۷ میوه و دامغانیاندی ظرفی با ۴ میوه داشته باشد.

  1. در نوبت اول، پیرهرات ۴ میوه از ظرف خود می‌خورد. حال پیرهرات ۳ میوه و دامغانیاندی ۴ میوه دارد.

  2. در نوبت دوم، دامغانیاندی ۳ میوه از ظرف خود می‌خورد. حال پیرهرات ۳ میوه و دامغانیاندی ۱ میوه دارد.

  3. در نوبت سوم، پیرهرات ۱ میوه از ظرف خود می‌خورد. حال پیرهرات ۲ میوه و دامغانیاندی ۱ میوه دارد.

  4. در نوبت چهارم، دامغانیاندی می‌بایست ۲ میوه از ظرف خود بخورد. چون کمتر از این مقدار میوه دارد، یک میوه می‌خورد و مسابقه به پایان می‌رسد.

از آنجایی که پیرهرات هم از رقابت و هم از برد خوشش می‌آید، دوست دارد در نهایت یکی از ظرف‌ها خالی و در ظرف دیگر دقیقا یک میوه باقی مانده باشد. به همین جهت، پیرهرات به یک جفت (a,b)(a, b) جفت «هرات‌پسند» می‌گوید اگر در صورتی که ظرف دامغانیاندی aa میوه و ظرف پیرهرات bb میوه داشته باشد، بازی به شکل بیان شده به پایان برسد.

حال در مراسم اختتامیه‌ی عملیات فوق سری قزاقستان، nn ظرف میوه چیده شده که در ظرف iiام، aia_i میوه قرار دارد. پیرهرات قصد دارد دو عدد ii و jj انتخاب کند که زوج (ai,aj)(a_i, a_j) هرات‌پسند باشد و حالِ دامغانیاندی را بگیرد. به همین جهت به شما گفته یا چنین زوجی برای او پیدا کنید، یا بگوید نمی‌تواند حال دامغانیاندی را بگیرد.

ورودی🔗

در خط اول ورودی، nn که تعداد ظرف‌های میوه است داده می‌شود. در خط دوم، nn عدد داده می‌شوند که عدد ii ام، تعداد میوه‌های ظرف ii ام است. 2n1052 \le n \le 10^5 1ai1061 \le a_i \le 10^6

خروجی🔗

در تنها خط خروجی، در صورتی که هیچ زوج هرات‌پسندی وجود نداشت کلمه‌ی impossibleو در غیر این صورت دو عدد iji \, j چاپ کنید که زوجی هرات‌پسند هستند.

مثال🔗

ورودی نمونه ۱🔗

4
1 12 67 8
Plain text

خروجی نمونه ۱🔗

impossible
Plain text

ورودی نمونه ۲🔗

5
1 1 12 67 8
Plain text

خروجی نمونه ۲🔗

2 1
Plain text

ورودی نمونه ۳🔗

6
1 5 6 7 90 8
Plain text

خروجی نمونه ۳🔗

2 6
Plain text

دقت کنید که ترتیب اعداد خروجی داده شده اهمیت دارد.

ارسال پاسخ برای این سؤال
در حال حاضر شما دسترسی ندارید.