المپدیا

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

ابزار کاربر

ابزار سایت


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

Mirrors

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

با تحقیقاتی که خیکوله انجام داده است، هسته‌ی مرکزی پردازش‌گرهای نوری، یک تراشه از آینه هاست که در یک جدول ‎$n \times m$‎ چیده شده‌اند. در هر خانه‌ی جدول می‌تواند یک آینه قرار داشته باشد. آینه‌ها تنها به شکل قطری قرار دارند و همواره از گوشه‌ی بالا سمت چپ یک خانه، به گوشه‌ی پایین سمت راست آن کشیده شده‌اند. پرتوهای نور از یکی از ‎$m$‎ حفره‌ی بالا یا ‎$n$‎ حفره‌ی سمت چپ جدول وارد آن شده و پس از بازتاب روی آینه‌ها از یکی از ‎$n$‎ حفره‌ی سمت راست یا ‎$m$‎ حفره‌ی پایین جدول خارج می‌شود (به عکس نگاه کنید).

خیکوله چندین پردازش‌گر نوری را از مقامات کشور خیکولند دریافت کرده است و باید نقشه‌ی آینه‌های جدول مرکزی هر یک از پردازش‌گرها را استخراج کند. برای اینکار او تنها می‌تواند ‎$n‎ + ‎m$‎ پرتو از خانه‌های بالایی و سمت چپی جدول به آن بتاباند و با تحلیل خروجی هریک از پرتوها، محتویات جدول را حدس بزند‎. ‎ او از شما خواسته است که با نوشتن یک برنامه‌ به او کمک کنید.

ورودی

  • در خط اول ورودی، عدد ‎$(1 \leq t \leq 10)$‎ تعداد پردازش‌گرها آمده است.‎
  • در خطوط بعدی توضیحات ‎$t$‎تا پردازش‌گر آمده است‎.
    • توضیحات هر پردازش‌گر با یک خط که در آن اعداد ‎$(1 \leq n \leq 1000)$‎ و ‎$(1 \leq m \leq 1000)$‎، ابعاد هسته‌ی مرکزی نوشته شده است، شروع می‌شود.
    • سپس در ‎$n$‎ خط بعدی، خروجی پرتوهایی آمده است که از سمت چپ تابانده ‌شده‌اند (به ترتیب از بالا به پایین).
    • در ‎$m$‎ خط بعدی، خروجی پرتوهایی می‌آید که از بالا تابانده شده‌اند (به ترتیب از چپ به راست).
      • خروجی یک پرتو به شکل یک جفت کاراکتر و شماره نشان داده شده است. در صورتی که کاراکتر ‎r‎ داده شده باشد، به این معنی است که پرتوی مورد نظر از سمت راست خارج شده است و عدد داده شده شماره سطری است که پرتو از آن خارج شده است (به ترتیب از بالا به پایین). در صورتی که کاراکتر ‎c‎ داده شده باشد، به این معنی است که پرتوی مورد نظر از سمت پایین خارج شده است و عدد داده شده شماره ستونی است که پرتو از آن خارج شده است (به ترتیب از چپ به راست).

خروجی

در خروجی به ازای هر پردازش‌گر، درصورتی که جدولی متناظر با داده‌های خیکوله وجود ندارد، عبارت ‎impossible‎ را چاپ کنید. در غیر این صورت شکل جدول را در خروجی چاپ کنید. فرمت جدول را مشابه خروجی نمونه چاپ کنید. بین خروجی‌های پردازش‌گرهای مختلف خط اضافه چاپ نکنید.‎ در صورتی که پاسخ سوال یکتا نباشد، یکی از پاسخ ها را چاپ نمایید‎.‎

محدودیت‌ها

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

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

ورودی نمونه خروجی نمونه
5‎
2 2‎
r 1‎
r 2‎
c 1
‎c 2‎

2 2‎
c 1‎
c 2‎
r 1‎
r 2‎

2 2‎
c 2‎
c 1‎
r 2‎
r 1‎

2 2‎
c 1‎
c 2‎
r 2‎
r 1‎

2 2‎
r 2‎
r 1‎
c 2‎
‎c 1‎
..
..
\‎.
.\‎
.\‎
\‎.
\\
.‎\‎
impossible

ابزار صفحه