المپدیا

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

ابزار کاربر

ابزار سایت


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

Army

حکیم ابولقاسم فردوسی: «یکی مرد جنگی به از صد نفر»

در نقشه‌های نظامی، هر سرباز یک نقطه در صفحه با مختصات صحیح $(x,y)$ است. افراد سپاه به تعدادی جوخه افراز شده‌اند و هر سرباز دقیقا عضو یک جوخه است. هر جوخه شامل چهار سرباز با مختصه‌های $(x,y)$، $(x+1,y)$، $(x,y+1)$ و $(x+1 , y+1)$ است و سربازی که مختصات $(x,y)$ دارد، سرجوخه نامیده می‌شود. بدیهی است در هیچ نقطه‌ای دو سرباز وجود ندارند.

هر دو سربازی که مولفه‌ی $x$ و یا $y$ یکسان دارند باهم در تماس بی‌سیم هستند. در یک عملیات نظامی می‌خواهیم افراد سپاه را به تعدادی لشکر تقسیم کنیم. در اصطلاح به این عمل لشکرکشی می‌گوییم. در این کار ممکن است افراد یک جوخه به لشکر‌های مختلفی فرستاده شوند. هر لشکر دقیقا $X$ سرباز دارد و افراد یک لشکر باید بتوانند مستقیما یا از طریق دیگر سربازان لشکر خود، با هم در ارتباط بی‌سیم باشند. در واقع افراد یک لشکر باید با استفاده از بی‌سیم، مولفه‌ای همبند تشکیل دهند.

برنامه‌ای بنویسید که:

  • تعداد جوخه‌ها $(n)$، $X$ و مختصات سرجوخه‌ها را از ورودی بخواند.
  • در صورت ممکن، $4n$ سرباز را به تعدادی زیرمجموعه‌ی $X$ عضوی همبند تقسیم کند و تقسیم‌بندی را در خروجی بنویسید.
  • در غیر این صورت، اعلام کند که این کار ممکن نیست.

ورودی

در سطر اول به ترتیب دو عدد $n$ و $X$ قرار دارند.($1\leq n \leq 40000$ و مولفه‌های $x$ و $y$ هر سرباز در تایپ int قابل ذخیره هستند)

در سطر دوم تا $n+1$ام، در هر سطر مختصات یکی از $n$ سرجوخه قرار دارد.

خروجی

  1. در صورتی که موفق شدید سربازها را به $X$ تایی‌ها افراز کنید: در سطر اول، رشته‌ی Yes را چاپ کنید. پس از آن، در هر سطر، $X$ زوج مختصات چاپ کنید که هر کدام نشان‌دهنده‌ی یک سرباز است. دقت کنید که این عددها را با فاصله از هم جدا کنید.
  2. در صورتی که لشکرکشی ناموفق بود: در تنها سطر خروجی،No چاپ کنید.

محدودیت‌ها

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

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

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

ابزار صفحه