المپدیا

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

ابزار کاربر

ابزار سایت


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

Numbers

باز هم یک بازی جدید! این بار دارا و سارا برای تقویت ریاضی‌شان، بازی زیر را طراحی کرده‌اند. دارا $n$ عدد اولیه انتخاب می‌کند؛ سپس این اعداد را با روشی مشخص به $n$ عدد نهایی تبدیل می‌کند. روش او این است که در هر مرحله می‌تواند یک عدد $x$ را انتخاب کند و آن را به یکی از دو عدد $2\times x$ یا $2\times x+1$ تبدیل کند و بدین ترتیب، $x$ حذف می‌شود و عددی دیگر جایش می‌آید. دارا می‌تواند این کار را به تعداد مراحلی که دوست دارد انجام دهد تا $n$ عدد نهایی به‌دست آید.

از این جا به بعد نوبت سارا شروع می‌شود:

سارا باید با دیدن $n$ عدد اولیه و $n$ عدد نهایی، به هر یک از اعداد اولیه مثل $a$، یکی از اعداد نهایی مثل $b$ را نسبت دهد، به طوری که اولا با استفاده از روش فوق بتوان از $a$ به $b$ رسید و ثانیا هر یک از اعداد نهایی به یکی از اعداد اولیه نسبت داده شده باشد و هیچ دو عدد اولیه‌ای به یک عدد نهایی مشترک نسبت داده نشده باشند. هم‌اکنون دارا نقش خود را در بازی انجام داده است و قرار است شما به سارا کمک کنید.

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

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

ورودی

  • در سطر اول ورودی، $n$(تعداد اعداد) آمده است.($1\leq n \leq 250000$)
  • در سطر دوم، $n$ عدد اولیه آمده‌اند که با فاصله از هم جدا شده‌اند.
  • در سطر سوم، $n$ عدد نهایی آمده‌اند که با فاصله از هم جدا شده‌‌اند.

خروجی

  • در صورت وجود جواب، در تنها سطر خروجی، $n$ عدد مختلف با فاصله از هم بنویسید؛ عدد $i$ام مشخص می‌کند که عدد نهایی نسبت داده شده به عدد اولیه‌ی $i$ام، چندمین عدد نهایی است.
  • در صورتی که این کار ناممکن بود، در تنها سطر خروجی، $-1$ را بنویسید.

محدودیت‌ها

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

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

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

ابزار صفحه