المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۳۸

قطعه شکلاتی به طول $m$ و به عرض $n$ به صورتی شیار داده شده که به واحد‌های $1\times1$ تقسیم شده است. در صورتی که یک قطعه شکلات را از روی یکی از خطوط عمودی یا افقی به دو قطعه تقسیم کنیم می‌گوییم که آن را «شکسته‌ایم». اگر برای تبدیل قطعه‌ی اولیه به قطعات $1\times1$، حداکثر تعداد شکستن لازم را با $B$ و حداقل آن را با $b$ نمایش دهیم کدام یک از گزینه‌های زیر درست است؟

  1. $b=mn-1,B=mn$
  2. $b=B=mn-1$
  3. $b=m+n-1,B=mn-1$
  4. $b=m+n-1,B=mn$
  5. $b=m+n-2,B=(m-1)(n-1)$

پاسخ

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

در ابتدا ۱ تخته‌ی شکلات بزرگ داریم و در هر مرحله تعداد تخته‌ها دقیقا یک واحد زیاد می‌شود. پس چون در انتها mn تا تکه شکلات داریم تعداد مراحل در هر صورت برابر با mn-1 است.


ابزار صفحه