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