فهرست مندرجات
Kind Neibours
در کشور یوتوپیا $4 \times n \times m$ خانه وجود دارد که در $2 \times n$ ردیف و $2 \times m$ ستون قرار دارند. در این کشور یک باغ وجود دارد که پر از گل است (می‌توانید فرض کنید تعداد گل‌های باغ بیشتر از $10^9$ است). هم‌چنین در باغچه هر خانه تعدادی گل وجود دارد.
در این کشور دو رسم با نام‌های عشق سطری و عشق ستونی وجود دارد که به صورت زیر انجام می‌شود.
عشق سطری به دو صورت زیر انجام می شود:
- ساکنان $2 \times m$ خانه که در یک سطر قرار دارند به روی پشت بام خود می‌روند و به‌ازای هر $1 \leq k \leq m$ خانه‌ی ستون $2 \times k-1$ یک گل به خانه شماره $2 \times k$ هدیه می‌دهد.
- ساکنان $2 \times m$ خانه که در یک سطر قرار دارند به روی پشت بام خود می‌روند و به‌ازای هر $1 \leq k \leq m$ خانه‌ی ستون $2 \times k$ یک گل به خانه شماره $2 \times k-1$ هدیه می‌دهد.
عشق سطری به دو صورت زیر انجام می شود:
- ساکنان $2 \times n$ خانه که در یک ستون قرار دارند به روی پشت بام خود می روند و به‌ازای هر $1 \leq k \leq n$ خانه ی سطر $2 \times k-1$ یک گل به خانه شماره $2 \times k$ هدیه می دهد.
- ساکنان $2 \times n$ خانه که در یک ستون قرار دارند به روی پشت بام خود می روند و به‌ازای هر $1 \leq k \leq n$ خانه‌ی سطر $2 \times k$ یک گل به خانه شماره $2 \times k-1$ هدیه می‌دهد.
هر کدام از خانه‌ها می‌توانند تعدادی گل از باغ قرض بگیرند ولی بعداً باید به همان تعداد گل به باغ پس بدهند. هدف مردم این است که بعد از چند بار انجام مراسم در هر خانه $0$ یا $1$ گل قرار بگیرد و هیچ خانه به باغ بدهکار نباشد. شما باید برنامه‌ای بنویسید تا با گرفتن اطلاعات، به‌دست بیاورد آیا این کار امکان‌پذیر است یا خیر.
ورودی
- در سطر اول ورودی، دو عدد زوج $1 \leq 2 \times n \leq 200$ و $1 \leq 2\times m \leq 200$ آمده‌اند.
- در $n$ سطر بعدی، $m$ عدد آمده است که تعداد گل‌های درون خانه‌ها را مشخص می‌کند.
خروجی
اگر این کار امکان‌پذیر باشد در تنها سطر خروجی YES و در غیر این‌صورت NO چاپ کنید.
محدودیت‌ها
- محدودیت زمان: ۲ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
ورودی و خروجی نمونه
| ورودی نمونه | خروجی نمونه |
|---|---|
| 2 2 1 1 2 0 | YES |
| 2 2 2 2 2 0 | NO |
پاسخ
فرض کنید $a[i][j]$ برابر باشد با تعداد گل‌های درون خانه سطر $i$ام و ستون $j$ام و تابع $f$ به صورت زیر تعریف شده باشد:
\selectlanguage{english} \[ f(i) = \left\{ \begin{array}{l l} -1 & \quad \text{if $i$ is even}\\
1 & \quad \text{if $i$ is odd}\\
\end{array} \right.
\]\\ \selectlanguage{farsi}
در این صورت مسئله برابر است با پیدا کردن اعداد طبیعی $row_1$ تا $row_{2 \times n}$ و $col_1$ تا $col_{2 \times m}$ به طوری که: $$\forall (1 \leq i \leq {2 \times n} , 1 \leq j \leq {2 \times m}) \longmapsto 0 \leq a[i][j]+row_i\times f(j)+col_j\times f(i) \leq 1 $$
می‌توان نشان داد که اگر $row_1, row_2,\cdots, row_{2 \times n}$ و $col_1, \cdots, col_{2 \times m}$ یک جواب برای سوال باشد، $row_1+f(1)\times col_1$ ، $row_2+f(2)\times col_1$ ، $\cdots$ ،$row_{2 \times n}+f({2 \times n})\times col_1$ و $0$ ، $col_2+f(1)\times col_1$ ، $col_3+f(2)\times col_1$ ، $\cdots$ ، $col_{2 \times m}+f({2 \times m}-1)\times col_1$ هم یک جواب برای سوال است. پس می‌توان فرض کرد که اگر یک جواب برای سوال وجود داشته باشد، جوابی برای سوال وجود دارد که در آن $col_1$ برابر است با $0$.
چون مقدار $col_1$ برابر است با $0$ پس مقدار $row_1$ یا برابر است با $1-a[1][1]$ یا $-a[1][1]$، که برای هر کدام از این حالات باید سوال را جداگانه حل کرد.
زمانی که مقدار $col_1$ و $row_1$ مشخص باشد، هر کدام از مقایر $row_{2\leq i \leq 2\times n}$ و $col_{2 \leq i \leq 2 \times m}$ دو حالت دارند. $a[i][j]$ محدودیتی برای $row_i$ و $col_j$ قرار می دهد. مسئله به دست آمده نسبت دادن یکی از دو عدد مناسب برای متغیر هاست طوری که شرایطی که اعداد جدول تولید می‌کنند را برآورده کند که 2-satisfiability}{http://en.wikipedia.org/wiki/2-satisfiability}} نام دارد.
با استفاده از الگوریتم حل 2-satisfiability می‌توان سوال را در زمان $o(n \times m)$ حل کرد.
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
