$n$ دسته سنگریزه داریم که در دسته $i$ ام $a_i$ سنگریزه قرار دارد. میدانیم به ازای هر $1 \leq i < n$ داریم $a_i \leq a_{i+1}$.
دو نفر بازی زیر را روی سنگریزهها انجام میدهند:
* هر نفر در نوبت خود یک دسته را انتحاب میکند و تعدادی از سنگ ریزههای آن را بیرون میاندازد، در صورتی که بعد از حرکت او به ازای یک $i > 1$ ، $a_i < a_{i-1}$ باشد او بازنده بازی خواهد بود. در غیر این صورت بازی ادامه پیدا میکند.
* در صورتی که بعد از حر کت یک بازیکن هیچ دستهای دارای سنگریزه نباشد، آن بازی کن برنده بازی خواهد بود.
در صورتی که هر دو بازیکن بهترین بازی خود را انجام دهند ، چه کسی برنده بازی خواهد بود؟
به ازای هر تست، در صورتی که نفر اول برنده بازی خواهد بود عبارت TAK و در غیر این صورت عبارت NIE را چاپ کنید.
| ورودی نمونه | خروجی نمونه |
|---|---|
| 2 2 2 2 3 1 2 4 | NIE TAK |
پاسخ
فرض کنید $\lceil \frac{n}{2} \rceil$ عدد به صورت زیر تعریف شده باشند:
* در صورتی که $n$ زوج باشد ، به ازای هر $1 \leq i \leq \frac{n}{2}$ ، $b_i = a_{2 i}-a_{2 \times i-1}$.
* در صورتی که $n$ فرد باشد ، $b_1 = a_1$ و $b_{2 \leq i \leq \frac{n+1}{2}} = a_{2 i -1}-a_{2 i -2}$.
در این صورت بازی به شکل زیر خواهد بود:
در هر مرحله هرکس میتواند یا تعداد خاصی بهیکی از $b_i$ ها اضافه کند، یا هر تعداد دلخواه از یکی از $b_i$ ها کم کند. هر چند زمانی که تمامی $b_i$ ها برابر با صفر باشد لزوماً پایان بازی نیست اما اگر یکی از بازیکنها بتواند طوری بازی کند که نوبت او حداقل یکی از $b_i$ ها بیشتر از صفر باشد برندهی بازی خواهد بود. (چون در حالت نهایی بازی حتماً تمام $b_i$ ها برابر با صفر خواهد بود).
میتوان نشان داد که اگر $x = b_1 \bigoplus b_2 \bigoplus \cdots \bigoplus b_{\lceil \frac{n}{2} \rceil}$ و $x > 0$ حتما یک عدد $j$ وجود دارد به شرطی که $b_j > b_j \bigoplus x$. یا به عبارت دیگر اگر xor $b_i$ ها ناصفر باشد ، میتوان یکی از $b_i$ ها را تعداد کاهش داد به طوری که xor اعداد برابر با صفر شود.
میتوان نشان داد در صورتی نفر اول برندهی بازی خواهد بود که xor $b_i$ ها در ابتدا مخالف صفر باشد، در این صورت او در هر مرحلهیکی از $b_i$ ها را طوری کاهش میدهد که xor اعداد برابر با صفر باشد و نفر دیگر با حرکت خود باعث میشود که xor اعداد ناصفر شود. پس اگر این استراتژی را ادامه دهد هیچ وقت نوبت او xor اعداد برابر با صفر نخواهد بود و نتیجتاً هیچ وقت تمام $b_i$ ها برابر با صفر نخواهد بود و او برنده بازی است.
در صورتی که xor $b_i$ ها در ابتدا برابر با صفر باشد نفر دوم با استراتژی گفته شده میتواند برنده بازی باشد.
پیچیدگی
میتوان به راحتی مقدایر $b_i$ ها را با $o(n)$ عملیات بهدست آورد و بر حسب xor آنها پاسخ سؤال را خروجی داد.