المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره‌ی انتخاب تیم:دوره‌ی ۱۷:سوال ۱

Balance

سال‌ها پیش در دهکده‌ی کچل‌آباد محصول مردم دهکده پشم و مو بود، مردم برای تقسیم کردن بسته‌های پشم و موی خود پیش کچل اعظم که کدخدای دهکده هم بود می‌رفتند و کچل اعظم تعدادی از بسته‌ها را (حداقل یک و نه لزوما همه‌ی آن‌ها) در جایگاه‌های ترازوی مخصوص خود می‌گذاشت طوری که ترازو در حالت تعادل قرار بگیرد و سپس شماره‌ی بسته‌های استفاده شده و جایگاه‌های آن‌ها را به مردم اعلام می‌کرد. ترازوی کچل اعظم از تعدادی جایگاه تشکیل شده بود. هر کدام از جایگاه‌ها با فاصله‌شان از مبدا مشخص می‌شدند و کچل اعظم می‌توانست هر تعداد از بسته‌ها را در هر کدام از جایگاه‌ها که دلش می‌خواست قرار دهد (ممکن است چند بسته در یک جایگاه قرار بگیرند). لازم به ذکر است که هنگامی ترازو در تعادل قرار می‌گیرد که مجموع ضرب وزن بسته‌ها در فاصله‌شان از مبدا برابر صفر شوند(با فرض این که مبدا ترازو نقطه‌ی صفر، مختصات جایگاه‌های راست ترازو مثبت و مختصات جایگاه‌های چپ‌ ترازو منفی باشند). شما به کچل اعظم کمک کنید که این کار را به درستی انجام بدهد.

برنامه‌ای بنویسید که:

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

ورودی

  • در سطر اول ورودی، عدد $n$(تعداد بسته‌ها) قرار دارد.
  • در هر یک از $n$ سطر بعد، یک عدد صحیح نامنفی آمده است که خط $i+1$ام وزن بسته‌ی $i$ام را نشان می‌دهد.
  • در سطر $n+2$ام عدد $m$(تعداد جایگاه‌ها) را بخواند.
  • در هر یک از $m$ سطر بعد، یک عدد صحیح آمده است که خط $n+i+2$ام مختصات جایگاه $i$ام را نشان می‌دهد.(قدر مطلق اعداد ورودی کوچک‌تر مساوی ۲۵ است.)

خروجی

اگر کار خواسته شده غیر ممکن بود در تنها سطر خروجی «impossible» چاپ کنید و در غیر این صورت، به تعداد بسته‌هایی که جواب شما استفاده می‌کند، در هر سطر خروجی به ترتیب دو عدد $i$ و $j$ چاپ کنید که $i$ شماره بسته و $j$ شماره‌ی جایگاه استفاده شده برای آن بسته می‌باشد(ترتیب چاپ کردن سطرها مهم نیست).

محدودیت‌ها

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

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

ورودی نمونه خروجی نمونه
2
3
5
2
-3
5
1 2
2 1

ابزار صفحه