المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۲۰:سوال ۱۹

سوال ۱۹

فرض کنید آرایه‌ای به طول ۱۰۰۰ از بیت‌های ۰ و ۱ داریم. می‌گوییم این آرایه «۰- غالب» است اگر دست کم ٪۹۰ اعداد آن ۰ باشد (و در نتیجه حداکثر ٪۱۰ آن ۱ باشد). هم‌چنین آرایه «۱- غالب» است اگر دست کم ٪۹۰ اعداد آن ۱ باشد (و در نتیجه حداکثر ٪۱۰ آن ۰ باشد). می‌دانیم که آرایه یا ۰- غالب است یا ۱- غالب٬ ولی نمی‌دانیم کدام‌یک. چندتا از درایه‌های این آرایه را باید بررسی کنیم تا به طور قطع بتوانیم بگوییم که آرایه ۰- غالب است یا ۱- غالب؟

  1. ۱۹۱
  2. ۲۰۱
  3. ۲۱۰
  4. ۵۰۱
  5. ۹۰۱

پاسخ

گزینه (۲) درست است.

اگر آرایه صفر غالب باشد حداکثر ۱۰٪ آن یعنی ۱۰۰ تا یک و اگر ۱-غالب باشد حداکثر ۱۰۰ تا صفر دارد. حال چون می‌دانیم آرایه یا ۰-غالب است و یا ۱-غالب اگر در بررسی‌مان از هرکدام از صفرها یا یک‌ها بیش‌تر از ۱۰۰ تا داشته باشیم می‌توانیم با قطعیت بگوییم که آن غالب است. پس در بدترین شرایط $100+100+1$ یعنی ۲۰۱ بررسی لازم داریم.


ابزار صفحه