المپدیا

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

ابزار کاربر

ابزار سایت


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

Queens

در یک صفحه شطرنج ‎$n$‎ در ‎$n$‎ تعداد ‎$m$‎ تا از خانه‌ها قرمز شده‌اند. می‌خواهیم در این صفحه تعداد ‎$k$‎ وزیر و یک سرباز را طوری قرار دهیم که هیچکدام از وزیرها دیگری را تهدید نکنند. (دو وزیر در صورتی یکدیگر را تهدید می‌کنند که در یک سطر یا ستون یا قطر قرار گرفته باشند و میانشان سرباز نباشد.)‎ توجه کنید که سرباز و یا هیچ وزیری نباید در خانه‌ی قرمز قرار بگیرند و نیز در یک خانه نباید بیش از یک مهره قرار گیرد.

ورودی

  • در سطر اول ورودی سه عدد ‎$m$‎ ، ‎$n$‎ و ‎$k$‎ به ترتیب و با یک فاصله آمده‌اند.
  • در ‎$m$‎ سطر بعدی مختصات خانه های قرمز آمده است. (شماره‌ی سطرها و ستون‌های صفحه از شماره ‎۱‎ شروع می‌شود).
  • ‎$3\leq k,n \leq 15$‎

خروجی

  • در سطر اول خروجی محل قرار گرفتن سرباز و در ‎$k$‎ سطر بعدی محل قرار گرفتن وزیرها را بنویسید.
  • در صورتی که بیش از یک حالت قابل قبول وجود داشت، فقط یک حالت را بنویسید و در صورت وجود نداشتن جواب پیغام ‎No Answer‎ را بنویسید.

محدودیت‌ها

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

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

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

ابزار صفحه