Pebbles

فرض کنید ‎$\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‎ آنها پاسخ سؤال را خروجی داد.