====== کلمه‌سازی ====== یک کلمه‌ ورودی $w$ و $p$ قانون تولید کلمه به‌صورت $x \longrightarrow yz$ داریم. اگر در $w$ از حرف $x$ استفاده شده باشد با استفاده از قانون $x \longrightarrow yz$ می‌توانیم حرف $x$ را حذف کنیم و به‌جای آن $yz$ بگذاریم. اگر در $w$ در بیش از یک‌جا $x$ آمده بود می‌توانیم یکی از این جا‌ها را به دلخواه انتخاب کنیم و قانون را روی آن اجرا کنیم. فرض کنید با کلمه‌ی $”g”$ شروع می‌کنیم و در تمام قوانین تولید کلمه فقط از حروف $”a…g”$ استفاده شده است. می‌خواهیم ببینیم آیا می‌توانیم با این قوانین کلمه‌ی $n$ حرفی $W$ را تولید کنیم. ===== ورودی ===== در سطر اول ورودی $p$ آمده و در $p$ سطر بعد در هر سطر سه حرف از حروف $a…g$ آمده است. اگر این حروف به ترتیب برابر $x$ و $y$ و $z$ باشند، نشان‌دهنده‌ی قانون تولید $x \longrightarrow yz$ هستند. (بین این حروف فاصله است) در سطر $p+2$ ام ورودی ابتدا $n$ و سپس کلمه‌ی $n$ حرفی $W$‌ آمده است.( $1 \leq m \leq 7$) ===== خروجی ===== اگر کلمه‌ی $W$ قابل تولید است، خروجی دارای $n-1$ سطر و هر سطر دارای ۲ عدد خواهد بود. در سطر $i$ ام شماره‌ی قانون تولید استفاده شده در مرحله $i$ ام و شماره‌ی حرفی که این کار روی آن انجام شده را بنویسید. در صورتی که این کار امکان پذیر نبود کلمه‌ی $Impossible$ را در فایل خروجی بنویسید. ===== محدودیت‌ها ===== * محدودیت زمان: ۵ ثانیه * محدودیت حافظه: ۲۵۶ مگابایت ===== ورودی و خروجی نمونه ===== ^ ورودی نمونه ^ خروجی نمونه ^ |4 \\ g a b \\ a c d \\ b e d \\ d f g \\ 5 cdefg| 1 1 \\ 2 1 \\ 3 3 \\ 4 4| <پاسخ> * [[سوال ۹|سوال بعد]] * [[سوال ۷|سوال قبل]]