المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره‌ی انتخاب تیم:دوره‌ی ۱۸:سوال ۲

Wall

در یک جدول ‎$m$‎ در ‎$n$‎ تعدادی از خانه‌ها سیاه شده‌اند و بقیه‌ی خانه‌ها سفید می‌باشند. می‌خواهیم در تعدادی از خانه‌های سفید جدول چراغ روشنایی قرار بدهیم.

چراغ‌ها باید به صورتی قرار گیرند که اولا به‌ازای تمام اضلاعِ خانه‌ها که دوطرف‌شان خانه‌ی سفید قرار دارد، حداقل یکی از دو خانه دارای چراغ باشد (از هر دو خانه‌ی سفید مجاور حداقل یکی باید چراغ داشته باشد) و ثانیا تعداد چراغ‌هایی که استفاده می‌کنیم کمینه باشند.

ورودی

  • در سطر اول ورودی دو عدد ‎$m$‎ و ‎$n$‎ به ترتیب و با یک فاصله آمده‌اند.
  • در ‎$m$‎ سطر بعدی در هر سطر ‎$n$‎ عدد ‎۰‎ یا ‎۱‎ با فاصله آمده‌اند. در صورتی که عدد ‎$j$،‎ام از سطر ‎$i$،‎ام ‎$0$‎ باشد، خانه‌ی سطر ‎$i$‎ و ستون ‎$j$‎ جدول سیاه و در غیر این صورت سفید می‌باشد (شماره‌ی سطرها و ستون‌های جدول از شماره ‎۱‎ شروع می‌شود).
  • ‎$1\leq m,n\leq 200$‎

خروجی

  • در سطر اول خروجی تعداد کم‌ترین چراغ لازم برای انجام این کار ‎($k$)‎ را بنویسید.
  • در ‎$k$‎ سطر بعدی، در هر سطر دو عدد به نشانه‌ی شماره‌ی سطر و ستون (به همین ترتیب) خانه‌هایی از جدول که در آن‌ها چراغ قرار می‌گیرد را بنویسید.

محدودیت‌ها

  • محدودیت زمان: ۱ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت

ورودی و خروجی نمونه

ورودی نمونه خروجی نمونه
3‎ 4
1 1 0 1‎
1 0 1 1 ‎
1 1 0 1
3‎
1 1
2 4
3 1

ابزار صفحه