المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۳۲:سوال ۴

سوال ۴

در یک مرغ‌داری، برای باز شدن هر تخم‌مرغ و در آمدن جوجه از آن باید تعدادی نوک به آن زده شود (این مقدار به میزان استحکام پوست تخم‌مرغ بستگی دارد). ۷ تخم‌مرغ داریم که به ترتیب به ۰، ۱، ۲، … و ۶ نوک برای باز شدن نیاز دارند. می‌خواهیم این تخم‌مرغ‌ها را در یک ردیف بچینیم. در هر مرحله، یکی از تخم‌مرغ‌هایی که به ۰ نوک نیاز دارد، باز می‌شود و جوجه از آن بیرون می‌آید؛ سپس جوجه‌ی بیرون آمده به تمام تخم‌مرغ‌های سمت راستش در ردیف ۲ نوک می‌زند (اگر تخم‌مرغی به کمتر از ۲ نوک نیاز داشته باشد، به همان مقدار مورد نیاز به آن نوک زده می‌شود). در چند ترتیب اولیه از تخم‌مرغ‌ها در ردیف مذکور، تمام تخم‌مرغ‌ها جوجه خواهند شد؟

  1. ۴۸
  2. ۱۲۰
  3. ۷۲۰
  4. ۱۴۴
  5. ۹۶

راهنمایی

اگر مقدور باشد که همه تخم‌مرغ‌ها جوجه شوند، ترتیب باز شدنشان مهم نیست و به هر ترتیبی که باز شوند، در نهایت همه تخم‌مرغ‌ها جوجه خواهند شد.

راهنمایی

تعداد نوک‌های مورد نیاز برای باز شدن چپ‌ترین تخم‌مرغ چند است؟

راهنمایی

با توجه به این که تعداد نوک‌های مورد نیاز برای باز شدن چپ‌ترین تخم‌مرغ نباید از صفر بیشتر باشد، سعی کنید به ترتیب تخم‌مرغ‌ها را از چپ به راست تعیین کنید.

در هر مرحله پس از تعیین شدن تخم‌مرغ $i$ام، اثر باز شدن آن تخم‌مرغ را بر تخم‌مرغ‌های دیگر اعمال کنید.


ابزار صفحه