Processing math: 60%

المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۱۶:تئوری:سوال ۱۵

صف جنجالی

در شهر ‎«ی.ا.ش.ا»، ‎n‎ صف اتوبوس قرار دارد. برای ایستادن در یک صف اتوبوس دو قاعده زیر باید رعایت شود‎:

  • شماره‌ی هرکس باید از شماره‌ی هریک از افراد جلویی‎)‎هر صف دقیقاً یک جلو دارد که آن‌هم نزدیک‌ترین مکان به تابلوی ایستگاه است‎(!‎ وی بیش‌تر باشد‎.‎
  • به‌جز نفرات اوّل هر صف، مجموع شماره‌ی هرکس و شماره‌ی نفر دقیقاً جلویی او باید مجذور کامل باشد‎.‎

با این وصف، اگر شماره‌ی افراد همیشه از یک شروع شود و حداکثر تعداد افرادی که با این قواعد می‌توانند در ‎n‎ صف بایستند را ‎f(n)‎ بنامیم، ثابت کنید: ‎

  1. f(n) \geq \lfloor \frac{(n+1)^2}{2} \rfloor‎ - ‎1
  2. f(n) \leq \lfloor \frac{(n+1)^2}{2} \rfloor‎ - ‎1

ابزار صفحه