المپدیا

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

ابزار کاربر

ابزار سایت


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

Coins

یک جدول با ‎$M$‎ سطر و ‎$N$‎ ستون داریم که در بعضی از خانه‌های آن سکه‌ای قرار دارد. می‌خواهیم بعضی از سکه‌ها را به رو و بعضی دیگر را به پشت قرار دهیم به‌طوریکه در هر سطر و هر ستون اختلاف تعداد سکه‌هایی که به رو قرار دارند با تعداد سکه‌هایی که به پشت قرار دارند، حداکثر برابر با یک باشد.

برنامه‌ای بنویسید که ابعاد جدول و مکان سکه‌ها را از ورودی استاندارد بخواند و یک وضعیت نهایی سکه‌ها را بگونه‌ای معین کند که خواسته‌ی مسئله برآورده شود.

ورودی

  • در اولین خط ورودی دو عدد آمده است. اولی تعداد سطرها ‎($M$)‎ و دومی تعداد ستون‌های جدول ‎($N$)‎ را مشخص می‌کنند.
  • در خط دوم تعداد سکه‌ها ‎($k$)‎ آمده است.
  • در هر یک از ‎$k$‎ خط بعدی دو عدد آمده است که اولین عدد شماره‌ی سطر و دومین عدد شماره‌ی ستون سکه‌ی ‎$i$‎اُم را نشان می‌دهد.
  • اندازه‌ی سطر و ستون جدول حداکثر برابر ‎$10^6$‎ است.
  • تعداد سکه‌ها حداکثر برابر ‎$10^5$‎ است.

خروجی

خروجی شامل تنها یک سطر است.

  • اگر مسئله برای ورودی داده شده جواب داشته باشد، باید در خروجی رشته‌ای به طول تعداد سکه‌ها از حروف ‎$H$‎ و ‎$T$‎ را چاپ کنید. اگر سکه‌ی ‎$i$‎اُم به رو است حرف ‎$i$‎اُم برابر با ‎$H$‎ و درغیراین‌صورت برابر با ‎$T$‎ باید باشد. در صورتی که مسئله چندین جواب داشته باشد، می‌توانید هر یک را به دل‌خواه چاپ کنید.
  • اگر جوابی برای ورودی داده شده وجود نداشت در خروجی عبارت ‎Impossible‎ را چاپ کنید.

محدودیت‌ها

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

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

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


ابزار صفحه