دنباله‌ای اکیدا صعودی مانند $a_1, a_2, ..., a_n$ از اعداد داریم. ما هیچ اطلاعاتی درباره‌ی اعداد نداریم و فقط می‌دانیم اکیدا صعودی هستند. عدد $x$ در این دنباله موجود است اما نمی‌دانیم کجای دنباله است و می‌خواهیم مکان عدد $x$ در دنباله را بیابیم. در هر مرحله می‌توانیم یکی از $a_i$ها را انتخاب کنیم؛ سپس به ما نتیجه‌ی مقایسه‌ی $x$ با $a_i$ گفته می‌شود؛ یعنی یکی از عبارات زیر گزارش داده می‌شود: $$x < a_i,\ \ \ x = a_i, \ \ \ x > a_i$$ هزینه‌ی مقایسه‌ی عدد $a_i$ با $x$، برابر $w_i$ است. $w_i$ داده شده است.

می‌خواهیم الگوریتمی ارائه دهیم که مکان عدد $x$ در دنباله را بیابد. کمینه‌ی هزینه‌ای که بتوان به طور تضمینی این کار را انجام داد $$f(w_1, w_2, ..., w_n)$$ می‌نامیم. برای مثال می‌توان نشان داد اگرتمام $w_i$ها برابر ۱ باشند، این مقدار برابر $\lfloor \lg(n) \rfloor$ خواهد شد (منظور از $\lg(n)$، لگاریتم $n$ در مبنای ۲ است).

مقدار $$f(\underbrace{2, 3, ..., 10, 1, 2, 3, ..., 10, ..., 1, 2, 3, ..., 10}_{\text{319 عدد}})$$ چند است؟

1. ۱۹
2. ۲۰
3. ۲۶
4. ۱۶
5. ۲۷

مقدار $$f(\underbrace{1, 1, ..., 1}_{\text{511 عدد}}, \underbrace{2, 2, ..., 2}_{\text{511 عدد}})$$ چند است؟

1. ۱۸
2. ۱۲
3. ۲۷
4. ۱۱
5. ۱۹

فرض کنید $n \ge 4$ باشد. مقدار $$f(n, n^2, n^3, ..., n^n)$$ چند است؟

1. $n+n^2+...+n^{n-1}$
2. $\sum_{1 \le 2k+1 \le n}n^{2k+1}$
3. $n^{n-3}+n^{n-1}$
4. $\lfloor{\lg(1+n+n^2+...+n^n)}\rfloor$
5. $\Big\lfloor n^{\frac{n}{2}} + n^{\frac{3n}{4}} + n^{\frac{7n}{8}} + ... \Big\rfloor$

فرض کنید $n \ge 3$ و تمام $w_i$ها متمایز هستند. چند تا از گزاره‌های زیر همواره درست هستند؟

• هیچ الگوریتم بهینه‌ای در مرحله‌ی اول $w_i$ بیشینه را انتخاب نمی‌کند.
• الگوریتم بهینه‌ای وجود دارد که در مرحله‌ی اول، $w_i$ای را انتخاب می‌کند که $|\sum_{j < i}w_j - \sum_{j > i} w_j|$ کم‌ترین مقدار ممکن را داشته باشد.
• جواب بهینه‌ای وجود دارد که در هیچ مرحله‌ای، $a_1$ را انتخاب نکند.
• جواب بهینه‌ای وجود دارد که در مرحله‌ی اول، $w_i$ کمینه را انتخاب کند.

1. ۳
2. ۴
3. ۰
4. ۱
5. ۲

• سوال قبل