Loading [MathJax]/jax/output/HTML-CSS/jax.js

المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۳

  1. آرایه‌ای شامل ‎n‎ عدد داریم. می‌خواهیم با اعمال حافظه و زمان پیش‌پردازش ‎O(n2)‎ به هر ‎پرسمان از نوع زیر در زمان ‎O(nlgn)‎ پاسخ دهیم‎.‎ «از بین اعداد ‎i‎ام تا ‎j‎ام آرایه ‎k‎امین عدد از نظر بزرگی کدام است.»
  2. با حافظه‌ی ‎O(n)‎ و پیش‌پردازش ‎O(nlgn)‎ هر پرسمان‎ را در زمان ‎O(n1100)‎ پاسخ دهید.

ابزار صفحه