المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۳۰

‎۲۰۰۰‎ بلوک ساختمانی هر یک به‌تنهایی بر روی زمین قرار دارند. می‌خواهیم برجی با قرار دادن همه‌ی این بلوک‌ها روی هم بسازیم. برای این کار تعداد نامحدودی جرثقیل داریم که می‌توانند به‌صورت هم‌زمان کار کنند. هر جرثقیل می‌تواند یک برج متشکل از یک یا چند بلوک را بر روی یک برج دیگر قرار دهد و یک برج جدید بسازد.

اگر تعداد بلوک‌های برجی که توسط جرثقیل برداشته می‌شود کم‌تر یا مساوی ‎۱۰۰‎ باشد، این کار یک ساعت و در غیر این‌صورت دو ساعت طول می‌کشد.

حداقل چند ساعت برای ساختن برج ‎ ۲۰۰۰‎بلوکی لازم است؟

  1. ‎۱۱
  2. ۱۲
  3. ۱۳
  4. ۱۴
  5. ۱۵‎

پاسخ

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

پس از ۶٬۵٬۴٬۳٬۲٬۱ و ۷ ساعت ارتفاع بلند‌ترین برج ساخته شده به ترتیب برابر ۶۴٬۳۲٬۱۶٬۸٬۴٬۲ و ۱۲۸ بلوک می‌باشد.

در هشتمین ساعت می‌توان یک برج ۱۰۰ بلوکی ر ا بر روی برج ۱۲۸ بلوکی قرار داده و برج ۲۲۸ بلوکی ساخت. بنابراین پس از گذشت ۸ ساعت بلندترین برج می‌تواند ۲۲۸ بلوک داشته باشد.

در نهمین ساعت نیز می‌توان یک برج ۱۰۰ بلوکی را بر روی برج ۲۲۸ بلوکی قرار داده و برج ۳۲۸ بلوکی ساخت. واضح است که اگر پس از گذشت ۷ ساعت برج ۱۲۸ بلوکی را بر روی برج ۱۲۸ بلوکی دیگر قرار دهیم دو ساعت طول خواهیم کشید که در این صورت در انتهای ساعت نهم طول بلندترین برج ۲۵۶ بلوک می‌باشد که برج ساخته شده به شیوه‌ی قبل که ۳۲۸ بلوک داشت بهینه می‌باشد.

برای ساختن برج بعدی به دو شیوه می‌توان عمل کرد یا در انتهای ساعت نهم یک برج ۱۰۰ بلوکی را در طول یک ساعت بر روی بلندترین برج ساخته شده یعنی برج ۳۲۸ بلوکی قرار داده و برج ۴۲۸ بلوکی به‌دست آورد٬ یا در انتهای ساعت یک برج ۲۲۸ بلوکی را در طول دو ساعت بر روی بلندترین برج ساخته شده یعنی ۲۲۸ بلوکی دیگر قرار داده و برج ۴۵۶ بلوکی به‌دست آوردکه حالت دوم بهینه است. بنابراین در انتهای ساعت دهم بلندترین برج ساخته شده دارای ۴۵۶ بلوک خواهد بود.

به همین ترتیب استدلال می‌شود که در انتهای ساعات ۱۴٬۱۳٬۱۲٬۱۱ و ۱۵ طول بلندترین برج می‌تواند به ترتیب ۱۸۲۴٬۱۳۱۲٬۹۱۲٬۶۵۶ و ۲۶۲۴ بلوک داشته باشد. بنابراین برای ساختن برجی به ارتفاع ۲۰۰۰ بلوک حداقل ۱۵ ساعت وقت لازم است.


ابزار صفحه