المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۱۷:سوال ۶

سوال ۶

۱۳۸۵ نفر روی محور اعداد ایستاده‌اند، به طوری که نفر $i$اُم ($۱ \le i \le ۱۳۸۵$) روی نقطه به طول $i$ قرار گرفته است. هر کدام از این افراد یک سنگ دارد و در یک لحظه همه با هم سنگ‌شان را به طرف مثبت پرتاب می‌کند. برد سنگ $i$اُم را با $f(i)$ نشان می‌دهیم. بدین ترتیب سنگ نفر $i$اُم بعد از پرتاب در محل $i+f(i)$ قرار می‌گیرد. می‌دانیم به ازای هر $x$٬ $f(x)$ برابر است با تعداد «صفرها» در نمایش مبنای دوی $x$ (سمت چپ‌ترین رقم در نمایش مبنای دو همواره یک است). به عنوان مثال، $f(۱۳)$ برابر است با ۱، زیرا نمایش مبنای دوی ۱۳ به صورت «۱۱۰۱» می‌باشد. که سه عدد «۱» و یک عدد «۰» دارد.

بعداز اینکه همه سنگ خود را پرتاب کردند، دورترین سنگ کجا می‌افتد؟ ( بزرگ‌ترین مکانی که در آن حدّاقل یک سنگ قرار می‌گیرد کجاست؟)

  1. ۱۳۸۵
  2. ۱۳۸۶
  3. ۱۳۹۰
  4. ۱۳۹۱
  5. ۱۳۹۵

پاسخ

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

عدد 1385 در مبنای دو معادل 10101101001 است. از آن‌جایی که این عدد 11 رقمی است و 5 رقم صفر دارد کافیست 5 عدد کوچک‌تر از آن را بررسی کنیم که از مقدار 1385 + 5 بیش‌تر خواهند شد یا خیر. زیرا تنها در صورتی که یکی از این 5 عدد تعداد صفرهای بیش‌تری نسبت به 1385 داشته باشد و اختلافش از 1385 کم‌تر از تعداد صفرهای بیش‌تر آن باشد، مقدار $K + f(K)$ بیش‌تر خواهد بود. برای چک کردن این 5 عدد نیز با استفاده از تفریق باینری به راحتی می‌توان دریافت که 1390 بزرگ‌ترین عددی است که می‌تواند وجود داشته باشد و جواب گزینه ج خواهد بود


ابزار صفحه