المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره‌ی تابستان:دوره‌ی ۱۴:عملی:سوال ۴

دزد خفن

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

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

پلیس برای دستگیری دزد تعدادی کارآگاه استخدام کرده است، این کار‌آگاهان پس از $t$ روز بررسی نتایج تحقیقات خود را در اختیار پلیس قرار دادند. هر کارآگاه نتایج خود را به این صورت اعلام می‌کند: دزد در روز $i$ ام در زیر مستطیل $(a_1,b_1) , (a_2,b_2)$ دیده نشده است. دقت کنید $(a_1,b_1)$ مختصات خانه‌ی گوشه‌ی بالا سمت چپ زیر مستطیل و $(a_2,b_2)$ مختصات خانه‌ی گوشه‌ی پایین سمت راست زیرمستطیل است.

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

ورودی

در سطر اول فایل ورودی $n،t$ و $m$ آمده است، در سطر دوم $k$ تعداد کارآگاهان داده شده است، سپس در $k$ سطر هر سطر اطلاعات مربوط به یک گارآگاه آمده است در هر سطر اعداد $a1،b1،a2،b2$ و $i$ نوشته شده است.($0 \leq I \leq t$ و $1\leq m,n,t,k \leq 500$)

خروجی

در سطر اول فایل خروجی، شما می‌بایستی $l$ تعداد خانه‌هایی که دزد می‌توانسته در روز اول بوده باشد را بنویسید، سپس در $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

ابزار صفحه