سکه و وزن


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

روی یک میز 2n2n سکه داریم. nn سکه در بالای میز با شماره‌های ۱ تا nn و nn سکه در پایین میز با شماره‌های ۱ تا nn قرار دارند. می‌دانیم تعدادی (شاید صفر) از سکه‌ها تقلبی، و بقیه‌ی سکه‌ها اصل هستند. سکه‌های اصل با هم، و سکه‌های تقلبی باهم، هم‌وزن هستند. همچنین می‌دانیم وزن سکه‌های تقلبی کمتر از وزن سکه‌های اصلی است.

شکل اصلی

برای هر ii و jj، وزن سکه‌ی iiام از طرف بالا میز را با سکه‌ی jjام از طرف پایین میز مقایسه کردیم و در صورتی که:

  • وزن سکه‌ی ii بالا، کمتر سکه‌ی jj پایین بود علامت <
  • وزن سکه‌ی ii بالا، بیشتر سکه‌ی jj پایین بود علامت >
  • وزن سکه‌ی ii بالا، برابر سکه‌ی jj پایین بود علامت =

را در سطر iiام ستون jjام یک جدول n×nn \times n نوشته‌ایم.

حال می‌خواهیم از روی این جدول مشخص کنیم کدام سکه‌ها اصل و کدام سکه‌ها تقلبی هستند. ممکن است در جدول داده شده، تناقضی وجود داشته باشد و یا نتوانیم با کمک این داده‌ها وضعیت را به صورت یکتا مشخص کنیم. از شما می‌‌خواهیم برنامه‌ای بنویسید که این سه حالت را شناسایی کرده و نتیجه را اعلام کند.

برای بهتر متوجه شدن سوال، نمونه‌ها را مطالعه کنید.

ورودی🔗

در سطر اول ورودی، عدد صحیح و مثبت nn به شما داده می‌شود. 1n2,0001 \leq n \leq 2 \,,000

در nn سطر بعدی، در هر سطر nn کاراکتر داده می‌شود که یکی از <، = یا > است. یعنی سکه‌ی iiام از jjام کوچکتر (<)، بزرگ‌تر‍ (>) یا مساوی (=) است.

خروجی🔗

اگر اطلاعات داده شده تناقض دارند عبارت invalid، در غیراین‌صورت اگر نمی‌توانستیم به‌صورت یکتا وضعیت تقلبی یا اصل بودن را شناسایی کنیم عبارت not unique و در غیراین‌صورت در دو سطر، در هر سطر یک رشته از 0 (تقلبی) و 1 (اصل) به طول nn چاپ کنید که به ترتیب وضعیت تقلبی یا اصل بودن سکه‌‌های بالای و پایین میز را نشان می‌دهد.

مثال‌ها🔗

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

4
<=<<
<=<<
=>==
<=<<
Plain text

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

0010
1011
Plain text
توضیح نمونه ۱

اگر وزن ۴ سکه‌ی بالا را با u1,u2,u3,u4u_1, u_2, u_3, u_4\, و ۴ سکه‌ی پایین را با d1,d2,d3,d4d_1, d_2, d_3, d_4 \, نشان دهیم. داده‌های جدول بالا به صورت زیر هستند:

u1<d1u1=d2u1<d3u1<d4u2<d1u2=d2u2<d3u2<d4u3=d1u3>d2u3=d3u3=d4u4<d1u4=d2u4<d3u4<d4 \begin{array}{cccc} u_1 \lt d_1 & u_1 = d_2 & u_1 \lt d_3 & u_1 \lt d_4 \\ u_2 \lt d_1 & u_2 = d_2 & u_2 \lt d_3 & u_2 \lt d_4 \\ u_3 = d_1 & u_3 \gt d_2 & u_3 = d_3 & u_3 = d_4 \\ u_4 \lt d_1 & u_4 = d_2 & u_4 \lt d_3 & u_4 \lt d_4 \\ \end{array}

سکه‌های تقلبی با رنگ نارنجی و سکه‌های اصل با رنگ زرد در تصویر زیر مشخص شده‌اند. این تنها حالت ممکن برای تقلبی یا اصل بودن سکه‌ها است و نتیجه مقایسه‌ها هم همین را نشان می‌دهد.

شکل نمونه ۱

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

3
=<<
<=<
<<=
Plain text

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

invalid
Plain text
توضیح نمونه ۲

هر دو سکه‌ی ۱ (بالا و پایین)، ۲ و ۳ باهم هم‌وزن هستند. پس می‌توانیم وزن آن‌ها را با w1w_1، w2w_2 و w3w_3 نشان دهیم.

می‌دانیم سکه‌ی ۱ (بالا) از سکه‌ی ۲ (پایین) سبک‌تر است (w1<w2w_1 \lt w_2). سکه‌ی ۲ (بالا) از سکه‌ی ۱ (پایین) سبک‌تر است (w2<w1w_2 \lt w_1). و این تناقض است و پاسخ invalid می‌شود.

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

1
=
Plain text

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

not unique
Plain text
توضیح نمونه ۳

در این حالت دو سکه داریم، سکه‌ی ۱ بالا و سکه‌ی ۱ پایین و می‌دانیم آن‌ها هم‌وزن هستند. ممکن است هر دو تقلبی و یا هر دو اصل باشند. پس نمی‌توان وضعیت آن‌ها را یکتا مشخص کرد و پاسخ not unique می‌شود.