المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۳۵

افشین روی نقطه‌ی ۰ محور اعداد حقیقی ایستاده است. او در هر حرکت با توجه به شرایط زیر مقداری به سمت راست حرکت می‌کند.

• او در حرکت اوّل خود حدّاقل ۱ واحد و حدّاکثر ۸۵ واحد به سمت راست حرکت می‌کند.

• درصورتی که افشین در حرکت $i$اُم خود، $a$ واحد به سمت راست رفته باشد،

– اگر $a$ زوج باشد، او در حرکت $i+1$ اُم، $\frac a2$ واحد به سمت راست خواهد رفت.

– اگر $a$ فرد باشد، او در حرکت $i+1$ اُم،$\frac {a-۱}۲$ + ۵۱۲ واحد به سمت راست خواهد رفت.

پس از انجام ۱۰ حرکت، بیشترین مقداری که افشین می‌تواند به سمت راست رفته باشد چه‌قدر است؟

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

پاسخ

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

برای اینکه بیش‌ترین تعداد حرکات را داشته باشیم باید به بیش‌ترین عدد فرد برسیم.

اعداد را در مبنای $2$ در نظر می‌گیریم در هر مرحله اگر عدد زوج باشدصفر جلوی عدد را برمی‌داریم و اگر عدد فرد باشد، $1$ جلوی عدد را برداشته و به آن $512$ تا اضافه می‌کنیم.

پس بیش‌ترین تعداد دفعاتی که می‌توانیم عدد فرد داشته باشیم حالتی است که بیش‌ترین تعداد $1$ ممکن را در مبنای $2$ عدد ابتدایی داشته باشیم.

در نتیجه عدد ابتدایی باید $63$ باشد که تعداد حرکات ممکن با انتخاب $63$ برابر است با $6138$.


ابزار صفحه