سوال ۱۴
در یک ایستگاه قطار، ریل‌ها به شکل زیر هستند:
همه‌ی ریل‌ها از سمت چپ به راست یک طرفه هستند. اگر ۵ قطار با شماره‌های ۱ تا ۵ به ترتیب ۵ و ۴ و ۳ و ۲ و ۱ از ورودی وارد این ریل‌ها شوند، کدام ترتیب برای خروج این قطارها ممکن نیست؟ (قطارها می‌توانند هر یک از دو راه رسیدن به خروجی را انتخاب کنند و همچنین می‌توانند مدتی روی ریل منتظر بمانند، ولی نمی‌توانند از روی هم عبور کنند. همچنین هر دو ریل به اندازه‌ی کافی طولانی هستند و می‌توانند تعداد زیادی قطار را در خود جا دهند).
- 4, 1, 2, 5, 3
- 4, 2, 1, 3, 5
- 2, 3, 4, 5, 1
- 2, 3, 5, 1, 4
- 3, 4, 1, 5, 2
پاسخ
گزینه (۲) درست است.
در دو ریل بالا و پایین دنباله‌ای نزولی وجود دارد٬ پس دنباله‌ی خروجی در درون خون دو دنباله‌ی نزولی دارد. دنباله‌ی گزینه ۱ را به دنباله‌های نزولی «1,2,3» و «4,5»٬ دنباله‌ی گزینه ۳ را به دنباله‌های نزولی «۱» و «2,3,4,5»٬ دنباله‌ی گزینه ۴ را به دنباله‌ای نزولی «1,4» و «2,3,5» و بالاخره دنباله گزینه ۵ را به دنباله‌های نزولی «1,2» و «1,4,5» تجزیه می‌کنیم. ولی گزینه‌ی ۲ امکان تجزیه شدن به دو دنباله‌ی نزولی را ندارد.
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
