به هر عبارت منطقی که به صورت $OR$ تعدادی از متغیرها به صورت $x_i$ یا $\overline{x_i}$ باشد، یک جمله $(Clause)$ گفته می‌شود. مانند:

$$s_1=x_1 \vee \overline{x_2} \vee x_3 \vee x_4 \vee \overline{x_5}$$

جمله‌ی $Horn$ به جمله‌ای گفته می‌شود که در آن حداکثر یک متغیر به صورت بدون نقیض (یعنی به صورت $x_i$) ظاهر می‌شود و بقیه‌ی متغیر‌ها با نقیض (به صورت $\overline{x_j}$) ظاهر می‌شوند.

مسئله‌ی $Horn-SAT$ به این صورت تعریف می‌شود: تعدادی از جمله‌های $Horn$ با یکدیگر $AND$ شده‌اند، می‌خواهیم به متغیرها‌ی $x_1,x_2,...,x_n$ آن طوری مقادیر $true$ یا $false$ نسبت بدهیم که کل عبارت مقدار $true$‌ داشته باشد.

برنامه‌ای بنویسید که با دریافت یک عبارت $Horn$ (به صورت $AND$ تعدادی جمله‌ی $Horn$) مقادیر $true$ یا $false$ را طوری به متغیر‌ها $(x_1,x_2,...,x_n)$ نسبت دهد که کل عبارت مقدار $true$ بگیرد.

در خط اول فایل به ترتیب دو عدد $n$ و $m$ ($n\leq 100,m\leq 1000$) وجود دارد که $n$ تعداد متغیرها است $(x_1,x_2,...,x_n)$ و $m$ تعداد جمله‌های $Horn$ در عبارت است.

بعد از خط اول $m$ خط در فایل ورودی وجود دارد؛ در خط $i$ ام در ابتدا عدد $l_i$ $(l_i\leq 100)$ تعداد متغیرها در جمله‌ی $i$ ام آمده و بعد از آن $l_i$ عدد به صورت $j$ یا $-j$ آمده که $j$ نشان‌دهنده‌ی $x_j$ و $-j$ نشان‌دهنده‌ی $\overline{x_j}$ است.

اگر مسئله جواب ندارد، در خط اول خروجی پیغام No Solution را بنویسید. در غیر این صورت فایل شامل $n$ خط خواهد بود که در خط $i$ ام مقدار $T$ ( معادل با $x_i=true$) یا مقدار $F$ (معادل با $x_i=false$) خواهد بود.

(معادل با عبارت ورودی $( \overline{}x_1 \vee \overline{x_2} \vee x_3) \land (x_1 \vee \overline{x_2}) \land (x_3 \vee \overline{x_2}) \land (x_3) \land (\overline{x_4})$ و خروجی $x_1=true,x_2=false,x_3=true,x_4=false$)

• سوال بعد
• سوال قبل