Processing math: 100%

المپدیا

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

ابزار کاربر

ابزار سایت


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

جایگشت

یک جایگشت از اعداد ۱ تا n را k- متناوب می‌گوییم، اگر هیچ زیردنباله‌ی متوالی در آن وجود نداشته باشد که طولش از k بیش‌تر باشد و یکنوا (صعودی یا نزولی) باشد. مثلا اگر n=5، جایگشت <1,5,2,3,4> ۲-متناوب نیست.

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

  • n و k یک جایگشت nتایی k-متناوب را از ورودی بخواند.
  • با فرض این‌که همه جایگشت‌های n تایی k-متناوب را به ترتیب الفبایی مرتب کنیم، حساب کنید که جایگشت داده شده،‌چندمین جایگشت است.

ورودی

  • در سطر اول ورودی به ترتیب دو عدد n و k آمده است.
  • در سطر بعدی n عدد آمده است که عناصر یک جایگشت k-متناوب را مشخص می‌کنند.

خروجی

در تنها سطر خروجی، باقی‌مانده رتبه جایگشت داده شده را بر عدد 10000000007 (۱۰ به توان ۹ به علاوه ۷) بنویسید.

محدودیت‌ها

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

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

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

ابزار صفحه