سوال ۴۷
۵ نفر با وزن‌های ۳۰٬۴۰٬۸۰٬۸۰ و ۲۰ کیلوگرم در یک طرف رودخانه ایستاده‌اند و قایقی دارند که ظرفیت آن ۸۰ کیلوگرم است.
آیا آن‌ها می‌توانند با استفاده از این قایق به سوی دیگر رودخانه بروند؟ (در هر بار رد شدن قایق از رودخانه باید حداقل یک نفر برای هدایت آن در قایق باشد.)
پاسخ
الگوریتم حرکت به صورت زیر می‌باشد( در ابتدا فرض می‌کنیم همه در سمت چپ رودخانه باشند):
۲۰ و ۳۰ باهم به سمت راست رفته و ۳۰ پیاده شده و ۲۰ برمی‌گردد.
۲۰ و ۴۰ باهم به سمت راست رفته و ۴۰ پیاده شده و ۲۰ برمی‌گردد.
۲۰ در سمت چپ پیاده شده و ۸۰ به سمت راست رفته پیاده شده و ۳۰ سوار می‌شود.
۳۰ به سمت چپ آمده٬ پیاده می‌شود و ۸۰ سوار شده به سمت راست می‌رود.
۸۰ در سمت راست پیاده شده و ۴۰ سوار شده به سمت چپ می‌آید.
۴۰ نفر ۲۰ را سوار کرده٬ به سمت راست آورده٬ آن را پیاده می‌کند و به سمت چپ برمی‌گردد و نفر ۳۰ را سوار کرده و با هم به سمت راست رفته و در آن‌جا پیاده می‌شوند.
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
