روی یک میز سکه داریم. سکه در بالای میز با شمارههای ۱ تا و سکه در پایین میز با شمارههای ۱ تا قرار دارند. میدانیم تعدادی (شاید صفر) از سکهها تقلبی، و بقیهی سکهها اصل هستند. سکههای اصل با هم، و سکههای تقلبی باهم، هموزن هستند. همچنین میدانیم وزن سکههای تقلبی کمتر از وزن سکههای اصلی است.
برای هر و ، وزن سکهی ام از طرف بالا میز را با سکهی ام از طرف پایین میز مقایسه کردیم و در صورتی که:
<
>
=
را در سطر ام ستون ام یک جدول نوشتهایم.
حال میخواهیم از روی این جدول مشخص کنیم کدام سکهها اصل و کدام سکهها تقلبی هستند. ممکن است در جدول داده شده، تناقضی وجود داشته باشد و یا نتوانیم با کمک این دادهها وضعیت را به صورت یکتا مشخص کنیم. از شما میخواهیم برنامهای بنویسید که این سه حالت را شناسایی کرده و نتیجه را اعلام کند.
برای بهتر متوجه شدن سوال، نمونهها را مطالعه کنید.
در سطر اول ورودی، عدد صحیح و مثبت به شما داده میشود.
در سطر بعدی، در هر سطر کاراکتر داده میشود که یکی از <
، =
یا >
است. یعنی سکهی ام از ام کوچکتر (<
)، بزرگتر (>
) یا مساوی (=
) است.
اگر اطلاعات داده شده تناقض دارند عبارت invalid
، در غیراینصورت اگر نمیتوانستیم بهصورت یکتا وضعیت تقلبی یا اصل بودن را شناسایی کنیم عبارت not unique
و در غیراینصورت در دو سطر، در هر سطر یک رشته از 0
(تقلبی) و 1
(اصل) به طول چاپ کنید که به ترتیب وضعیت تقلبی یا اصل بودن سکههای بالای و پایین میز را نشان میدهد.
اگر وزن ۴ سکهی بالا را با و ۴ سکهی پایین را با نشان دهیم. دادههای جدول بالا به صورت زیر هستند:
سکههای تقلبی با رنگ نارنجی و سکههای اصل با رنگ زرد در تصویر زیر مشخص شدهاند. این تنها حالت ممکن برای تقلبی یا اصل بودن سکهها است و نتیجه مقایسهها هم همین را نشان میدهد.
هر دو سکهی ۱ (بالا و پایین)، ۲ و ۳ باهم هموزن هستند. پس میتوانیم وزن آنها را با ، و نشان دهیم.
میدانیم سکهی ۱ (بالا) از سکهی ۲ (پایین) سبکتر است (). سکهی ۲ (بالا) از سکهی ۱ (پایین) سبکتر است (). و این تناقض است و پاسخ invalid
میشود.
در این حالت دو سکه داریم، سکهی ۱ بالا و سکهی ۱ پایین و میدانیم آنها هموزن هستند. ممکن است هر دو تقلبی و یا هر دو اصل باشند. پس نمیتوان وضعیت آنها را یکتا مشخص کرد و پاسخ not unique
میشود.