====== سؤال ۱۶ ======

جای‌گشت $n$ عضوی $<a_1,a_2,...,a_n>$ از اعداد ۱ تا $n$ را در نظر بگیرید. برنامه‌ی زیر این دنباله را مرتب می‌کند:

  * دستورهای زیر را برای هر یک از مقادیر $i$ از ۱ تا $n$ تکرار کن:
    * تا وقتی‌که $a_i$ برابر $i$ نیست، مقدار خانه‌ی $i$ را با مقدار خانه‌ی $a_i$ تعویض کن.


مثلاً اگر ورودی <۴، ۱، ۳، ۲، ۵> باشد،

{{ :سوالات_المپیاد:مرحله‌ی_اول:دوره‌ی_۱۵:5.png?nolink |}}



حداکثر تعداد تعویض‌ها برای تمام جای‌گشت‌های ۲۰۰۵ عضوی را در نظر بگیرید. باقی‌مانده‌ی این عدد بر ۵ چند است؟
  - ۰
  - ۱
  - ۲
  - ۳
  - ۴
<پاسخ>
گزینه (?) درست است.



معلوم است که در هر تعویضی حداقل یک عدد در جای خود قرار می‌گیرد و با توجه به این که در تعویض آخر دو عدد در جای خود قرار می‌گیرند٬ بنابراین تعداد تعویض‌ها حداکثر ۲۰۰۴ خواهدشد.


برای جای‌گشت زیر تعداد تعویض‌ها برابر ۲۰۰۴ خواهد شد.


$$2005,1,2,3,4,...,2003,2004$$

</پاسخ>


  * [[سوال ۱۷|سوال بعد]]
  * [[سوال ۱۵|سوال قبل]]