المپدیا

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

ابزار کاربر

ابزار سایت


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

قیچی شطرنجی

قیچی شطرنجی ماشینی است که یک صفحه‌ی شطرنجی را فقط روی خطوط جدول برش می‌دهد و مقدار کل برش را در حافظه‌ی خود نگه می‌دارد (طول برش). برای مثال در شکل زیر، یک صفحه‌ی $4\times 4$ به وسیله‌ی این ماشین به چهار قطعه به اندازه‌های ۳، ۴، ۴ و ۵ تقسیم شده است. طول این برش برابر ۱۱ می‌باشد.

یک صفحه‌ی شطرنجی $7\times 8$ داده شده است. می‌خواهیم با قیچی شطرنجی آن را به تعدادی قطعه تقسیم کنیم به طوری که اندازه‌ی هر قطعه حداکثر ۵ باشد و طول برش کمینه شود.

با انجام برش‌های مناسب، کم‌ترین طول برش را به‌دست آورید. نحوه‌ی برش خود را با رسم شکل نشان دهید و ثابت کنید که مجموع طول برش به‌دست آمده کمینه است.


ابزار صفحه