====== $k$ تایی‌های خوب ======



دنباله‌ی $a_1, a_2, \dots, a_n$ از اعداد طبیعی مفروض است. به $n^k$ طریق می‌توان یک $k$ تایی مرتب از این اعداد تولید کرد. به ازای هر یک از این $k$ تایی‌های مرتب، جمع آن را در دنباله $s$ قرار می‌دهیم (جمع یک $k$ تایی مرتب برابر با مجموع تمامی اعضای آن می‌باشد). \\
دنباله $s$ که به صورت نانزولی مرتب شده است را $s_1 \leq s_2 \leq \dots \leq s_{n^k}$ در نظر بگیرید. الگوریتمی بیابید که با ورودی گرفتن $n$ ،دنباله‌ی $a$ و عدد $m$ مقدار $s_m$ را مشخص کند ($k$ مقداری ثابت است). \\
اگر الگوریتم شما از
 $O(n^{\lceil \frac{k}{2} \rceil} lg(n) lg(max(a_i))$
 باشد **۱۵ امتیاز**، اگر از 
$O(n^{\lceil \frac{k}{2} \rceil} lg^2(n))$
 باشد، **۸۰ امتیاز** و اگر از 
$O(n^{\lceil \frac{k}{2} \rceil} lg(n))$
 باشد **۱۰۰ امتیاز** می‌گیرید.


باید ثابت کنید الگوریتم شما درست و از مرتبه مشخص شده است. توجه کنید که حافظه اشغال شده توسط الگوریتم شما از مرتبه پیچیدگی زمانی آن باشد.




  * [[سوال ۲|سوال قبل]]