مسابقه شماره 226
2000 بلوک ساختمانی هر یک به تنهایی بر روی زمین قرار دارند. میخواهیم برجی با قرار دادن همهی این بلوکها روی هم بسازیم. برای این کار نامحدودی جرثقیل داریم که میتوانند به صورت همزمان کار کنند. هر جرثقیل میتواند یک برج متشکل از یک یا چند بلوک را بر روی یک برج دیگر قرار دهد و یک برج جدید بسازد . اگر تعداد بلوکهای برجی که توسط جرثقیل برداشته میشود کمتر یا مساوی 100 باشد, این کار یک ساعت و در غیر این صورت دو ساعت طول میکشد. حداقل چند ساعت برای ساختن برج 2000 بلوکی لازم است؟
پس از 1,2,3,4,5,6و7 ساعت ارتفاع بلندترین برج ساخته شده به ترتیب برابر2,4,8,16,32,64و128 بلوک میباشد.
در هشتمین ساعت میتوان یک برج 100 بلوکی را بر روی برج 128 بلوکی قرار داده و برج 228 بلوکی ساخت. بنابراین پس از گذشت 8 ساعت بلندترین برج میتواند 228 بلوک داشته باشد.
در نهمین ساعت نیز میتوان یک برج 100 بلوکی را بر روی برج 228 بلوکی قرار داده و برج 328 بلوکی ساخت. واضح است که اگر پس از گذشت 7 ساعت برج 128 بلوکی را بر روی برج 128 بلوکی دیگر قرار دهیم دو ساعت طول خواهد کشید که در این صورت در انتهایی ساعت نهم طول بلند ترین برج 256 بلوک میباشد که برج ساخته شده به شیوهی قبل که 328 بلوک داشت بهینه میباشد. برای ساختن برج بعدی به دو شیوه میتوان عمل کرد یا در انتهای ساعت نهم یک برج 100 بلوکی را در طول یک ساعت بر روی بلندترین برج ساخته شده یعنی برج 328 بلوکی قرار داده و برج 428 بلوکی به دست آورد , یا در انتهای ساعت هشتم یک برج 228 بلوکی را در طول دو سات بر روی بلندترین برج ساخته شده یعنی 228 بلوکی دیگر قرار داده و برج 456 بلوکی ده دست آورد که حالت دوم بهینه است.
بنابراین در انتهای ساعت دهم بلند ترین برج ساخته شده دارای 456 بلوک خواهد بود. به همین ترتیب استدلال میشود که در انتهای ساعت 11,12,13,14و15 طول بلندترین برج میتواند به ترتیب 656,912,1312,1824و2624 بلوک داشته باشد. بنابراین برای ساختن برجی به ارتفاع 2000 بلوک حداقل 15 ساعت وقت لازم است.