Loading [MathJax]/jax/output/HTML-CSS/jax.js

المپدیا

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

ابزار کاربر

ابزار سایت


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

تخصیص برچسب

گراف وزن‌دار G داده شده است به طوری که یال‌های آن یا از نوع A و یا B هستند رئوس این گراف را طوری در صفحه‌ی دو بعدی قرار دهید (تخصیص مختصات صحیح برای رئوس) که:

  • الف) اگر از راس V1 به V2 یال ازنوع A باشد هم مختصات x و هم مختصات y راس V2 از V1 بیش‌تر باشد.
  • ب) اگر از راس V1 به V2 یال از نوع B باشد یا مختصات x و یا مختصات y راس V2 از V1‌بیش‌تر باشد.

ورودي

در سطر اول فایل ورودی تعداد رئوس گراف (n50) و بعد از آن یک جدول nn داده شده است به طوری که اگر در گراف بین دو راس i و j یال نباشد ai,j برابر ۰ است اگر یال از نوع A باشد برابر ۱ و در غیر این صورت برابر ۲ می‌باشد.

خروجي

در صورت وجود جواب در سطر i ام فایل خروجی مختصات راس i ام نوشته شود و در غیر این صورت پیغام Impossible را بنویسید.

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

ورودي نمونه خروجي نمونه
4
0 1 0 0
0 0 0 0
1 2 0 1
0 0 0 0
0 0
1 1
-1 -1
2 2

ابزار صفحه