سوال ها لزوما به ترتيب سختی مرتب نشده اند.

تبدیل گراف


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

دو گراف nn راسی به شما داده شده است که راس‌های آن‌ها از 11 تا nn شماره‌گذاری شده اند. در هر مرحله می‌توان یال‌های متصل به یک راس در گراف اول را یک بار به صورت ساعتگرد یا پادساعتگرد چرخاند.

عمل چرخاندن یک راس مانند vv به این شکل انجام می‌شود که در ازای هر یال از vv به uu در گراف، یک یال جدید از vv به nextv(u)next_v(u) قرار داده می‌شود و تمامی یال‌های قدیمی راس vv پاک می‌شود.

برای حرکت چرخاندن ساعتگرد، تابع nextnext به شکل زیر تعریف می‌شود:

nextv(u)={u1,u1vu2,u1=v next_{v}(u)= \begin{cases} u \oplus 1, & u \oplus 1 \ne v \\ u \oplus 2, & u \oplus 1 = v \end{cases}

برای چرخاندن پادساعتگرد نیز تابع nextnext به طور مشابهی ساخته می‌شود: nextv(u)={u1,u1vu2,u1=v next_{v}(u)= \begin{cases} u \oplus -1, & u \oplus -1 \ne v \\ u \oplus -2, & u \oplus -1 = v \end{cases}

منظور از عملگر \oplus جمع دوری است که به شکل زیر تعریف می شود:

ij={i+jmodn,i+jmodn0n,i+jmodn=0 i \oplus j = \begin{cases} i + j \mod n, & i + j \mod n \ne 0\\ n, & i + j \mod n = 0 \end{cases}

هدف تبدیل گراف اول به گراف دوم در تعدادی حرکت است. آیا این کار امکان پذیر است؟

ورودی🔗

در خط اول ورودی عدد طبیعی nn، تعداد راس‌های گراف‌ها آمده است. در nn خط بعدی از ورودی در هر خط یک رشته‌ی nn حرفی از 0 و 1 آمده است که ماتریس مجاورت گراف اول را نشان می‌دهد و 1 بودن حرف jjام خط iiام وجود یک یال از ii به jj در گراف اول را نشان می‌دهد. در nn خط بعدی به حالت مشابه ماتریس مجاورت گراف دوم آمده است. تضمین می‌شود ماتریس‌های ورودی متقارن هستند و درایه‌های روی قطرشان برابر با صفر است.

1n501 \le n \le 50

خروجی🔗

در صورتی که نمی‌توان گراف اول را به گراف دوم تبدیل کرد در یک خط عبارت impossible را چاپ کنید. در غیر این‌صورت ابتدا تعداد حرکات لازم برای تبدیل گراف اول به گراف دوم را چاپ کنید و در خطوط بعدی حرکات را به شکل - v یا + v چاپ کنید. - v یک چرخاندن ساعتگرد بر روی راس vv و + v یک چرخاندن پادساعتگرد بر روی راس vv را نشان می‌دهد. دقت کنید لزومی ندارد که تعداد حرکات مینیمم باشد و جواب شما اگر کمتر از 300 000300\ 000 حرکت داشته باشد قابل قبول است.

زیرمسئله‌ها🔗

زیرمسئله نمره محدودیت
۱ ۱۱ n7n \le 7
۲ ۱۱ تضمین می‌شود درجه هر راس در گراف‌ها دقیقاً یک است.
۳ ۲۲ تضمین می‌شود گراف‌ها درخت هستند.
۴ ۵۶ بدون محدودیت اضافی

مثال🔗

ورودی نمونه ۱🔗

4
0101
1000
0001
1010
0011
0001
1000
1100
Plain text

خروجی نمونه ۱🔗

10
+ 2
+ 2
- 3
+ 2
+ 4
- 1
+ 4
+ 1
- 4
- 4
Plain text
ارسال پاسخ برای این سؤال
در حال حاضر شما دسترسی ندارید.