Processing math: 100%

المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:متفرقه:سوال های تمرینی دوره ی تابستان:سوال ۳۰

Great Thief

از آن‌جا که المپیاد کامپیوتری‌ها به جدول خیلی علاقه دارند، شهر آن‌ها به شکل یک جدول m×n است، همچنین می‌دانیم که در محیط جدولی دیوار کشیده شده است، به‌طوری که هیچ کس نمی‌تواند از شهر خارج شود.

یک دزد در روز 0ام(روز افتتاح شهر)‌ از یکی از بانک‌های شهر دزدی می‌کند.می‌دانیم که بانک در یکی از m×n خانه‌های جدول قرار دارد. می‌دانیم دزد هر شب حرکت می‌کند،‌ او از خانه‌ی فعلیش به یکی از ۴ خانه‌ی مجاور (در صورت وجود) می‌رود. توجه کنید دزد در روز 0ام در خانه‌ی بانک قرار دارد.

پلیس برای دستگیری دزد تعدادی کارآگاه استخدام کرده است، این کارآگاهان پس از t روز نتایج بررسی خود را در اختیار پلیس قرار دادند. هر کارآگاه نتایج خود را به این صورت اعلام می‌کند:‌ دزد در روز iام در زیرمستطیل (a1,b1),(a2,b2) دیده نشده است. دقت کنید (a1,b1) مختصات گوشه‌ی بالا سمت چپ و (a2,b2) مختصات گوشه‌ی پایین سمت راست زیر مستطیل است.

مختصات خانه‌ی گوشه‌ی بالا سمت چپ شهر (1,1) و مختصات خانه‌ی گوشه‌ی پایین سمت راست شهر (m,n) است. شما می‌بایستی با فرض اینکه اطلاعات کارآگاهان درست است محل بانک را بیابید.

ورودی

  • در سطر اول ورودی، m و n و t آمده است.
  • در سطر دوم k تعداد کارآگاهان داده شده است.
  • سپس در k سطر در هر سطر اطلاعات مربوط به یک کارآگاه آمده است در هر سطر i، a1، b1، a2 و b2 نوشته شده است. ( 0it)
  • 1n,m,t500

خروجی

  • در سطر اول خروجی شما باید l تعداد خانه‌هایی که دزد می‌توانسته در روز 0ام باشد را بنویسید.
  • سپس در l سطر مختصات هر یک از این خانه‌ها را بنویسید، مختصات‌ها به هر ترتیب دل‌خواهی می‌توانند نوشته شوند.

محدودیت‌ها

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

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

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

پاسخ

منتظر پر کردن این قسمت توسط علاقمندان هستیم.


ابزار صفحه