شاززز

شاززز

اینجا وبسایت آزاد المپیاد کامپیوتره! ;)
واسه ی همه ی سطوح از تازه کارها تا طلای جهانی!

بایگانی

سوال شب چهاردهم

دوشنبه, ۱۵ بهمن ۱۳۹۷، ۱۰:۱۸ ب.ظ
سوال امشبم بخاطر درخواست های زیاد(!) گذاشتیم

فرض کنید جایگشت <a1 , a2 , ... , an> جایگشتی از اعداد 1 تا n باشد. به جایگشتی علامت دار میگوییم اگر هر عدد مثبت بین 1 تا n دقیقن یکبار به صورت منفی یا مثبت آمده باشد. مثلن <1 , 3 , -2> جایگشتی علامتدار است اما <2,-1,1> نیست.

حاصل دوران (i,j) که i<=j روی یک جایگشت علامتدار <a1 , a2 , ... ,ai, ai+1,...,aj, ... , an> برابر با جایگشت علامتدار زیر است
<a1 , a2 , ... ,-aj,-aj-1,...,-ai, ... , an>

ثابت کنید برای تبدیل جایگشت علامتدار <a1 , a2 , ... , an> به <an , an-1 , ... , a1> به حداقل n-1 دوران نیاز داریم.

مهدی جعفری

(همچنین یک گراف G داریم و در آن شایان پردیس به راس F میرود و سلام کرده و آب میخورد.)
  • ۹۷/۱۱/۱۵
  • طلاهای دوره ۲۸

نظرات  (۱)

جالب بود اما هیچی ازش نفهمیدم

ارسال نظر

ارسال نظر آزاد است، اما اگر قبلا در بیان ثبت نام کرده اید می توانید ابتدا وارد شوید.
شما میتوانید از این تگهای html استفاده کنید:
<b> یا <strong>، <em> یا <i>، <u>، <strike> یا <s>، <sup>، <sub>، <blockquote>، <code>، <pre>، <hr>، <br>، <p>، <a href="" title="">، <span style="">، <div align="">
تجدید کد امنیتی