المپدیا

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

ابزار کاربر

ابزار سایت


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

Decrypt

سازمان جاسوسی آدم‌های فضایی برای مخابره‌ی خبرهایش به مریخ، از نوع خاصی مکالمات رمزی استفاده می‌کند تا دیگران قادر به فهمیدن این خبرها نباشند. هر خبر فضایی، یک رشته‌ی به طول $n$ از اعداد ۱ تا $d$ است و پس از رمز شدن نیز یک رشته با همین طول از اعداد ۱ تا $d$ باقی می‌ماند. برای رمز‌گشایی یک خبر رمزی باید یک از اعداد ۱ تا $d$ و یک عدد که « عدد جابه‌جایی» خوانده می‌شود، در اختیار دشته باشیم. کافی است کل خبر را به اندازه‌ی «عدد جابه‌جایی» به راست شیفت دوری دهیم و سپس جایگشت مورد نظر را روی اعداد اعمال کنیم تا متن خبر به دست آید.

اعمال یک جایگشت بر روی یک دنباله از اعداد باعث می‌شود عددهای ۱ در دنباله به عدد اول جایگشت،… و عددهای $d$ به عدد آخر جایگشت تبدیل شوند. شیفت دوری به راست به اندازه‌ی $x$ باعث می‌شود $x$ عنصر آخر دنباله‌ با همان ترتیب در اول دنباله قرار گیرند.

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

شما باید برنامه‌ای بنویسید که عدد جابه‌جایی و جایگشت قابل قبول را پیدا کند یا اعلام کند که چنین اعدادی وجود دارند.

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

  • $n$ و $d$ از ورودی بخواند.
  • سپس خبر رمزی و خبر مورد حدس را بخواند.
  • عدد جابه‌جایی و جایگشت و یا No solution را در خروجی بنویسید.

ورودی

  • سطر نخست ورودی شامل دو عدد طبیعی است: $n$ که طول دنباله‌ها و $d$ که اعداد آن‌ها را مشخص می‌کند.($1\leq n \leq 500000$ و $1\leq d \leq 100000$)
  • سطر بعدی محتوی $n$ طبیعی است که خبر رمزشده را نشان می‌دهد.
  • در سطر بعدی نیز $n$ عدد طبیعی آمده‌اند که خبر حدس ما را مشخص می‌کند.
  • در خبر رمز شده از هر یک از اعداد ۱ تا $d$ لااقل یکی وجود دارد.

خروجی

  • در صورتی با الگوریتم رمزگشایی گفته شده تبدیل سطر دوم ورودی به سطر آن ممکن است، در اولین سطر خروجی عدد جابه‌جایی و در سطر دوم، جایگشت تبدیل را بنویسید.
  • در غیر این صورت در تنها سطر خروجی بنویسید No solution.

محدودیت‌ها

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

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

ورودی نمونه خروجی نمونه
6 3
1 2 3 3 2 1
1 3 3 1 2 2
2
3 1 2
6 3
1 2 3 3 2 1
1 3 3 2 2 1
No solution

ابزار صفحه