المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:متفرقه:آزمون های اینترنتی ۸۹ تا ۹۱:سوال ۷۰

Pebbles

‎$n$‎ دسته سنگ‌ریزه داریم که در دسته ‎$i$‎ ام ‎$a_i$‎ سنگ‌ریزه قرار دارد. می‌دانیم به ازای هر ‎$1 \leq i < n$‎ داریم ‎$a_i \leq a_{i+1}$.

‎ دو نفر بازی زیر را روی سنگ‌ریزه‌ها انجام می‌دهند: ‎

  • ‎ هر نفر در نو‌بت خود یک دسته را انتحاب می‌کند و تعدادی از سنگ ریزه‌های آن را بیرون می‌اندازد، در صورتی که بعد از حرکت او به ازای یک ‎$i > 1$‎ ، ‎$a_i < a_{i-1}$‎ باشد او بازنده بازی خواهد بود. در غیر این صورت بازی ادامه پیدا می‌کند.
  • ‎‎ در صورتی که بعد از حر کت یک بازیکن هیچ دسته‌ای دارای سنگ‌ریزه نباشد، آن بازی کن برنده بازی خواهد بود.

‎ ‎ در صورتی که هر دو بازیکن بهترین بازی خود را انجام دهند ، چه کسی برنده بازی خواهد بود؟‎ ‎

ورودی

  • در سطر اول ورودی عدد ‎$1 \leq t \leq 10$‎ نشان‌دهنده تعداد تست‌ها آمده است‎.
  • در سطر اول هر تست عدد ‎$1 \leq n \leq 1000$‎ و در سطر بعدی ‎$n$‎ عدد ‎$a_1$‎ تا ‎$a_n$‎ آمده است‎.

خروجی

به ازای هر تست، در صورتی که نفر اول برنده بازی خواهد بود عبارت ‎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‎ آنها پاسخ سؤال را خروجی داد.


ابزار صفحه