• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

دیدن، باور کردن است اما آیا حقیقت است؟!

تردستی به تازگی وارد شهر شده و یک تردستی کلاسیک را با خود به شهر آورده. بازی تردست به این گونه است که روی یک میز سه کاسه کنار هم در یک ردیف قرار دارند. زیر کاسه اول یک نخود و زیر دو کاسه‌ی دیگر چیزی نیست. تردست پشت میز می‌رود و در هر مرحله دو کاسه را خیلی سریع باهم جابه‌جا می‌کند به طوری که تعداد جابه‌جایی‌ها برابر $n$ است.

همه‌ی تماشاچیان می‌دانند که قبل از شروع شعبده‌بازی، نخود زیر کاسه اول بوده است. تردست که آوازه تبحر برنامه‌نویسی شما به گوشش رسیده، از شما خواسته‌ که برنامه‌ای بنویسید که بعد از پایان شعبده‌بازی، مکان کاسه‌ای که نخود زیر آن است را مشخص کند.

ورودی🔗

در سطر اول ورودی، عدد صحیح $n$ که تعداد جابه‌جایی‌ها است می‌آید. $1 \le n \le 1000$ سپس در $n$ سطر بعدی، مکان دو کاسه‌ای که جابه‌جا می‌شوند به شما داده می‌شود.

$1 \le a \neq b \le 3$

خروجی🔗

در تنها سطر خروجی شماره‌ی مکان کاسه‌ای که نخود زیر آن است را خروجی دهید.

مثال🔗

ورودی نمونه ۱🔗

4
1 2
2 3
3 1
1 2

خروجی نمونه ۱🔗

2

در مرحله اول نخود زیر کاسه‌ی اول قرار دارد:

• با جابه‌جایی کاسه مکان اول و دوم، نخود زیر کاسه‌ی مکان دوم می‌رود.
• با جابه‌جایی کاسه مکان دوم و سوم، نخود زیر کاسه‌ی مکان سوم می‌رود.
• با جابه‌جایی کاسه مکان سوم و اول، نخود زیر کاسه‌ی مکان اول می‌رود.
• با جابه‌جایی کاسه مکان اول و دوم، نخود زیر کاسه‌ی مکان دوم می‌رود.

بنابراین بعد از پایان تردستی، نخود زیر کاسه‌ی مکان دوم است.

• محدودیت زمان: ۲ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

پدر دوقلوهای افسانه‌ای می‌خواهد برای دو دخترش گردنبند بخرد. از آن‌جا که بین دو گردنبند تثلیث برقرار است (یعنی یا دو گردنبند کاملاً یکی هستند و یا یکی بهتر از دیگری است)، پدر باید دو گردنبند کاملاً یکسان خریداری کند تا دوقلوها به یکدیگر حسودی نکنند.

به ازای حالت‌های مختلف بگویید دو گردنبند یکی هستند یا نه؟

دقت کنید چنانچه که یک گردنبند را بچرخانیم و یا آن را برعکس کنیم گردنبند ثابت باقی می‌ماند! توصیه می‌شود به مثال‌های نمونه توجه کنید.

ورودی🔗

در خط اول عدد $t$ می آید که نشان دهنده تعداد جفت‌ گردنبندهای مدنظر پدر دوقلوهای افسانه‌ای است. سپس در هر کدام از $t$ خط بعدی، یک جفت گردنبند مدنظر پدر با یک فاصله از هم می‌آید.

$1 \le t \le 21 \, 844$

طول هر گردنبند حداکثر ۷ و از حروف کوچک انگلیسی تشکیل شده است.

خروجی🔗

به ترتیب برای هر جفتی که نشان دهنده دو گردنبند یکسان هستند، عبارت YES و در غیر این‌صورت عبارت NO را خروجی دهید. به بزرگ بودن حروف خروجی خود توجه کنید.

مثال🔗

ورودی نمونه ۱🔗

6
ab abab
abc cba
gcd lcm
abc bca
lca lcs
abacb abcab

خروجی نمونه ۱🔗

NO
YES
NO
YES
NO
YES

• در جفت اول چون طول دو گردنبند یکی نیست، آن‌ها با هم برابر نیستند.
• در جفت دوم با برعکس کردن گردن بند دوم به گردنبندها برابر می‌شوند.
• در جفت سوم g در گردنبند اول هست ولی در دومی وجود ندارد.
• در جفت چهارم با یک واحد شیفت دادن به چپ گردنبند اول به گردنبند دوم می‌رسیم.
• در جفت پنجم a در گردنبند اول هست ولی در دومی نیست.
• در جفت ششم با یک بار برعکس کردن رشته‌ی اول، و یک واحد شیفت دادن به راست، به رشته‌ی دوم می‌رسیم.

• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

تربچه علاقه زیادی به دنباله‌های خوب دارد. یک دنباله به طول $n$ را خوب می‌گوییم اگر هر $k$ عدد متوالی از آن را که نگاه می‌کنیم، اعداد $1$ تا $k$ دقیقاً یکبار در آن ظاهر شده باشند. به علاوه، هر دنباله خوب یک ارزشی دارد. ارزش یک دنباله برابر مجموع قدرمطلق اختلاف هر دو عدد مجاور آن است.

برای مثال اگر دنباله خوب به طول $n = 7$ و $k = 4$ را در نظر بگیریم که به صورت $1, 2, 3, 4, 1, 2, 3$ است، ارزش آن برابر $|1 - 2| + |2 - 3| + |3 - 4| + |4 - 1| + |1 - 2| + |2 - 3| = 8$ می‌شود.

حال تربچه از شما می‌خواهد که با داشتن مقدار $k$ و $n$، مقدار بیشترین ارزشی که یک دنباله خوب می‌تواند داشته باشد را به دست آورید.

ورودی🔗

در تنها سطر ورودی، به ترتیب دو عدد صحیح $k$ و $n$ داده می‌شوند.

$1 \le k \le 8$ $1 \le n \le 100\, 000$ $k \leq n$

خروجی🔗

بیشترین ارزشی که می‌توان با ساخت یک دنباله به دست آورید را نمایش دهید.

مثال🔗

ورودی نمونه ۱🔗

4 4

خروجی نمونه ۱🔗

7

یک دنباله که عدد ۷ را می‌سازد دنباله زیر است: $3, 1, 4, 2$

ورودی نمونه ۲🔗

2 4

خروجی نمونه ۲🔗

3

• محدودیت زمان: ۲ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

ترب و بچه‌اش تربچه می‌خواهند توپ بازی کنند ولی نه بازی‌های سطحی که انسان‌ها انجام می‌دهند! پیش روی آن‌ها در ابتدای هر بازی تعدادی دسته قرار دارد و در هر دسته تعدادی (بزرگتر از ۱) توپ قرار دارد. هر کس در نوبت خود می‌تواند دقیقاً یکی از عملیات‌های زیر را روی یک دسته که حداقل ۲ توپ داشته باشد انجام دهد و هر کس که نتواند عملی انجام دهد، بازنده بازی می‌شود. توجه کنید تربچه چون کوچک‌تر است همیشه آغازکننده بازی هست.

1. یک دسته با $a$ توپ را به دو دسته با $1$ و $a-1$ توپ تقسیم کند.
2. یک دسته با $a$ توپ را به دو دسته با $\lfloor \frac{a}{2} \rfloor$ و $\lceil \frac{a}{2} \rceil$ توپ تقسیم کند.
3. یک دسته با $a$ توپ را به دو دسته با $\lfloor \sqrt a \rfloor$ و $a- \lfloor \sqrt a \rfloor$ توپ تقسیم کند.

برای اطلاع از تعریف عبارت‌های $\lfloor a \rfloor$ و $\lceil a \rceil$ می‌توانید لینک کف و سقف را مطالعه کنید.

ورودی🔗

در سطر اول ورودی، عدد صحیح $t$ که نشان دهنده‌ی تعداد بازی‌های انجام شده بین ترب و تربچه می‌آید. $1 \leq t \leq 100$

سپس اطلاعات هر بازی می‌آید. در سطر اول اطلاعات هر بازی، $k$ یا همان تعداد دسته‌ها می‌آید و سپس در سطر بعد، $k$ عدد صحیح می‌آید که ‌$i$ـمین ‌آن‌ها $c_i$ نام دارد و نشان دهنده تعداد توپ‌ها در دسته $i$ام است. $1 \le k \le 10 \, 000$ $2 \le c_i \le 100 \, 000$

خروجی🔗

به ازای هر بازی اگر ترب با بازی بهینه برنده می‌شد Torob و در صورت برد تربچه با بازی بهینه Torob Che را خروجی دهید.

مثال🔗

ورودی نمونه ۱🔗

4
1
6
2
3 3
1
9
3
2 2 2

خروجی نمونه ۱🔗

Torob Che
Torob
Torob
Torob Che

• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

ترب و تربچه هر کدام یک جدول $n \times n$ دارند که در هر خانه‌ی آن یکی از اعداد $1$ تا $n^2$ نوشته شده به طوری که هر عدد دقیقاً یکبار در این جدول‌ها ظاهر شده باشند.

تربچه می‌خواهد جدولش را به جدول ترب تبدیل کند. او در هر عملیات می‌تواند:

• جای دو سطر از جدولش را باهم عوض کند.
• جای دو ستون از جدولش را باهم عوض کند.

حال تربچه می‌خواهد بداند آیا می‌تواند جدولش را مشابه جدول ترب کند یا نه.

ورودی🔗

در سطر اول ورودی، عدد صحیح و مثبت $t$ آمده که تعداد سناریوها را نشان می‌دهد. $1 \leq t \leq 10$

در سطر اول هر سناریو، عدد صحیح و مثبت $n$ آمده که اندازه‌ی جدول‌ها را نشان می‌دهد. $2 \leq n \leq 50$

در $n$ سطر بعدی هر سناریو، در هر سطر $n$ عدد آمده که عدد ظاهر شده در سطر $i$ام ستون $j$ام، عدد $a_{i, j}$ از جدول تربچه است.

در $n$ سطر بعدی، به طور مشابه جدول اعداد ترب ظاهر می‌شود. تضمین می‌شود که در هر دو جدول، اعداد $1$ تا $n^2$ دقیقاً یکبار ظاهر شوند.

خروجی🔗

خروجی $t$ سطر دارد و هر سطر جواب یک سناریو است. اگر در یک سناریو جدول تربچه قابل تبدیل به جدول ترب بود، YES و در غیر این صورت NO چاپ کنید.

توجه کنید سیستم داوری نسبت به بزرگ و کوچک بودن حروف حساس است.

مثال🔗

ورودی نمونه ۱🔗

3
2
1 2
3 4
4 3
2 1
3
1 2 3
4 5 6
7 8 9
1 2 3
8 9 4
7 6 5
2
1 2
3 4
1 3
2 4

خروجی نمونه ۱🔗

YES
NO
NO

• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

در یک انباری $n$ تکه چوب داریم. طول چوب $i$ام برابر $l_i$ است. حال می‌خواهیم $k$ تکه از این چوب‌ها را برداریم به طوری که بتوان با آن‌ها یک قاب به شکل $k$ ضلعی ساخت.

توجه کنید صرفاً انتخاب کردن تکه چوب‌ها یک حالت جدید به وجود می‌آورد و نیازی به چیدن آن‌ها برای اضلاع یک قاب نداریم. همچنین دو تکه چوب با طول برابر را متمایز در نظر بگیرید.

از شما می‌خواهیم تعداد حالت‌های ممکن برای ساختن این قاب را چاپ کنید.

تضمین میشود که مقدار $k$ کوچکتر مساوی $n$ است

ورودی🔗

در سطر اول ورودی، به ترتیب دو عدد صحیح و مثبت $n$ و $k$ آمده است. $3 \leq n \leq 60$ $3 \leq k \leq 8$

در سطر دوم ورودی، $n$ عدد صحیح که با یک فاصله از هم جدا شده‌اند و عدد $i$ام آن همان $l_i$ یعنی طول چوب $i$ام است. $1 \leq l_i \leq 60$

زیرمسئله‌ها🔗

خروجی🔗

در تنها سطر خروجی، تعداد روش‌های انتخاب کردن چوب برای ساخت قاب را چاپ کنید.

مثال🔗

ورودی نمونه ۱🔗

5 3
1 1 1 1 1

خروجی نمونه ۱🔗

10

ورودی نمونه ۲🔗

6 4
1 2 4 8 16 32

خروجی نمونه ۲🔗

0

ورودی نمونه ۳🔗

5 5
1 2 3 4 5 

خروجی نمونه ۳🔗

1

• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

ترب و تربچه مشغول بازی کردن شطرنج هستند. بازی شطرنج آن‌ها روی یک جدول $n \times n$ انجام می‌شود. ترب با رنگ سفید و تربچه با رنگ سیاه بازی می‌کند. ترب سه مهره دارد، دو مهره‌ی رخ و یک مهره‌ی شاه دارد. تربچه یک مهره‌ی شاه دارد.

اکنون وضعیت اولیه بازی با ۴ مهره به شما داده می‌شود. فرض کنید ترب به هوشمندانه ترین شکل ممکن بازی می‌کنند ولی تربچه که فقط یک مهره‌ی شاه دارد هر بار از بالاترین سطر شروع می‌کند و به ترتیب از چپ به راست به اولین خانه‌ای که بتواند حرکت کند، حرکتش را انجام می‌دهد. (ترتیب خانه‌ها عبارت است از بالا چپ، بالا، بالا راست، چپ، راست، پایین چپ، پایین و پایین راست) حال از شما می‌خواهیم کمترین تعداد حرکت لازم برای پایان بازی را چاپ کنید.

قوانین بازی شطرنج🔗

مهره‌ی شاه در یک حرکت می‌تواند به یک خانه‌ی مجاور راسی برود که هیچ کدام از مهره‌های همرنگ خودش در آن نیست (اگر به خانه‌ای برود که مهره‌ی غیرهمرنگ باشد و آن مهره شاه نباشد، آن مهره را از صفحه بازی حذف می‌کند و به‌جای آن قرار می‌گیرد). مهره‌ی شاه نمی‌تواند به خانه‌ای برود که ممکن است در حرکت بعدی حریف، باعث حذف شدن شاه شود (همان مفهوم «کیش شدن»).

مهره‌ی رخ می‌تواند به همه‌ی خانه‌های هم سطر و یا هم ستونش که هیچ مهره‌ای در بازه‌ی بین آن‌ها نیست، حرکت کند (نمی‌تواند از روی دیگر مهره‌ها بپرد).

اگر در یک وضعیت مهره‌ی شاه بازیکنی مورد تهدید یک بازیکن دیگر باشد، باید در حرکت بعدی، خودش را از آن وضعیت خارج کند و نمی‌تواند کار دیگری انجام دهد.

بازی به نوبت انجام می‌شود، ابتدای بازی نوبت مهره‌های سفید است و سپس سیاه و بعد از آن به نوبت و یک حرکت انجام می‌دهند. اگر بازیکنی نتواند در نوبت خودش حرکت انجام دهد بازی تمام می‌شود. اگر وضعیت طوری باشد که شاه در معرض تهدید باشد، تهدید کننده برنده‌ی بازی است ولی اگر شاه هیچ تهدیدی نشده باشد ولی هیچ مهره‌ای را نمی‌توان حرکت داد، بازی مساوی می‌شود. اگر هیچ بازیکنی هیچ راه‌ پیروزی نداشته باشد بازی به تساوی منجر می‌شود.

ورودی🔗

در سطر اول ورودی عدد صحیح و مثبت $n$ آمده که ابعاد صفحه‌ی شطرنج را نشان می‌دهد. $3 \leq n \leq 4$

در سطر دوم ورودی عدد صحیح و مثبت $t$ آمده که تعداد سناریوهای مختلف را نشان می‌دهد. $1 \leq t \leq 10\,000$

در هر سناریو یک جدول $n \times n$ از کاراکترها بدون فاصله داده می‌شود. در واقع هر جدول $n$ رشته به طول $n$ است که کاراکترهای آن K و R و . و k است که به ترتیب مهره‌ی شاه سفید، رخ سفید، خانه خالی و شاه سیاه را نشان می‌دهد.

تضمین می‌شود در جدول داده شده مهره‌ی شاه سیاه در معرض تهدید نباشد، دو مهره‌ی رخ سفید و یک شاه سفید و یک شاه سیاه در جدول باشد و بقیه‌ی خانه‌ها خالی باشند.

تضمین می‌شود در وضعیت اولیه، شاه کسی در معرض تهدید نیست و فرض کنید بعد از این وضعیت نوبت رنگ سفید است.

محدودیت‌ها🔗

خروجی🔗

خروجی $t$ سطر دارد، در هر سطر با فرض اینکه هر دو بازیکن بهترین بازی خود را ارائه دهند، کمترین تعداد حرکت برای پیروزی را با CheckMate و سپس تعداد مراحل را چاپ کنید و یا عدم امکان پیروزی و همان تساوی یا Draw را چاپ کنید (به نمونه خروجی توجه کنید).

مثال🔗

ورودی نمونه ۱🔗

4
2
.R.K
..R.
....
k...
...K
..R.
.k..
R...

خروجی نمونه ۱🔗

CheckMate 1
CheckMate 5

.R.K
R...
....
k...

...K
....
.k..
R.R.

...K
.k..
....
R.R.

....
.k.K
....
R.R.

.k..
...K
....
R.R.

.k..
...K
....
RR..

• محدودیت زمان: ۴ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

مردم شهر دست‌به‌دست هم می‌دهند و یک صف بلند درست می‌کنند. هر شهروند یک عدد بین ۰ تا $M$ برای خودش انتخاب کرده است. عدد شهروند $i$ام برابر $a_i$ است.

حال از روی اعداد شهروندان اعداد $t_1, t_2, \dots, t_{n-k+1}$ را به صورت زیر می‌سازیم.

$a_i \oplus a_{i+1} \oplus \dots \oplus a_{i+k-1} = t_i$

منظور از $\oplus$ عملگر $xor$ است.

اکنون دیگر به اعداد شهروندان دسترسی نداریم و فقط دنباله‌ی $t$ را داریم. از شما می‌خواهیم تعداد حالت‌های ممکن برای اعداد شهروندان را محاسبه کنید.

از آن‌جایی که ممکن است پاسخ مسئله خیلی بزرگ باشد، باقی‌مانده‌ی پاسخ مسئله را بر $10^9 + 7$ چاپ کنید.

ورودی🔗

در سطر اول به ترتیب سه عدد $n$ و $k$ و $M$ آمده است. $1 \le k \le n \le 5000$

سپس در سطر بعد $n-k+1$ عدد می‌آید که عدد $i$ـم نشانگر $t_i$ است.

$0 \le M, t_i \le 5000$

زیرمسئله‌ها🔗

خروجی🔗

در تنها سطر خروجی یک عدد نامنفی که پاسخ مساله به پیمانه $10^9+7$ است را خروجی دهید.

مثال🔗

ورودی نمونه ۱🔗

4 2 0
0 1 1

خروجی نمونه ۱🔗

0

با توجه به اینکه $M = 0$ است، پس دنباله‌ی $a$ تماماً ۰ است و نمی‌تواند دنباله‌ی $t$ به صورت گفته شده باشد. بنابراین پاسخ مسئله برابر ۰ می‌شود.

ورودی نمونه ۲🔗

3 3 2
1

خروجی نمونه ۲🔗

7

ورودی نمونه ۳🔗

25 23 89
22 37 41

خروجی نمونه ۳🔗

809594952