المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۳

باز هم رئیس مجلس، تصمیم به محاکمه‌ی وزیر المپیاد گرفته است. باور کنید این هماهنگی کار یک روز و دو روز نیست.

ضمن این که ‎$n-2$‎ وزنه‌ی ‎۱ گرمی و ‎۲‎ وزنه‌ی ‎$\frac{1}{2}$‎ گرمی داریم. وزنه‌ها از نظر ظاهری کاملا شبیه به هم هستند. دست‌گاهی داریم که با گذاشتن تعدادی وزنه بر روی آن، به ما می‌گوید مجموع وزن این وزنه‌ها، مقداری صحیح هست یا خیر.

می‌خواهیم حداقل یکی از وزنه‌های ‎$\frac{1}{2}$ گرمی را پیدا کنیم. کمینه‌ی تعداد دفعات استفاده از دست‌گاه را که به طور تضمینی بتوان این کار را انجام داد، ‎$f(n)$‎ در نظر می‌گیریم. ‎$\theta(f(n))$‎ را بیابید.


ابزار صفحه