فرض کنید به شما دو دنباله داده شده است و شما مسئول آن هستید که ببینید آیا ترتیب کاراکترها در دنباله دوم، همان ترتیب در دنباله اول است یا خیر؟ کافیست از راست یا از چپ ترتیب حفظ شود.

مثلاً اگر دنباله اول abcdefghi و دنباله دوم bfhi باشد، ترتیب از چپ به راست در اولی حفظ شده است. مثالی دیگر که ترتیب را از راست به چپ حفظ کند، دنباله اول abcdefghi و دنباله دوم gfdb است که ترتیب آمدن اعضای دنباله دوم در اولی از راست به چپ است و ترتیب را حفظ کرده است.

مثالی بزنیم که ترتیب را نه از راست به چپ و نه از چپ به راست، حفظ نکرده باشد. دنباله اولی ‫‪abcdefghi‬‬ و دنباله دومی ‫‪bgic‬‬.

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

توجه: ممکن است در دنباله دوم کاراکتری بیاید که در اولی نیست. روشن است که در این صورت پاسخ منفی است و ترتیب حفظ نشده است.

توجه: ممکن است از هر کاراکتر به هر تعداد موجود باشد. کافی‌ست در یکی از حالات ترتیب حفظ شده باشد تا پاسخ مثبت باشد. برای مثال اگر دنباله اول ‫‪abacdfeag‬‬ و دنباله دوم bca باشد ترتیب حفظ شده است (با در نظر گرفتن آخرین a).

ورودی🔗

در خط اول به شما عدد $1\leq n \leq 10$ داده می‌شود که $n$ بیان‌گر تعداد زوج‌های دنباله‌هاست. سپس به ازای هر زوج دنباله، در یک خط دنباله اول و در خط بعدی دنباله دوم می‌آید.

خروجی🔗

به ازای هر زوج دنباله اگر ترتیب حفظ شده است، YES وگرنه NO را چاپ کنید.

ورودی نمونه🔗

5
abcdefghi
dfge
abcdefghi
hcba
qwer
asdf
qwkedlrfid
kelid
abacdfeag
bca

خروجی نمونه🔗

NO
YES
NO
YES
YES

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

کریم یک کودک ۵ ساله است که در گفتن برخی حروف انگلیسی مشکل دارد.

برای مثال او گاهی از اوقات به جای حرف K، حرف T را تلفظ میکند. اما او هیچ‌گاه به جای حرف T، حرف K را تلفظ نمی‌کند.

همینطور او گاهاَ حرف G را به اشتباه D تلفظ می‌کند. و R را بعضی اوقات L تلفظ می‌کند و بعضی اوقات F. البته پیش می‌آید که این حروف را درست تلفظ کند.

مادر کریم همیشه نسبت به گفته‌ی او شوق وافری نشان می‌دهد؛ از این رو کلمه‌ای که کریم گفته را به شما میگوید و شما باید تعداد کلمه‌های ممکن که کریم با مدنظر داشتن آن‌ها چنین کلمه‌ای را می‌گوید را به او بگویید. (مستقل از بامعنا بودن یا نبودن این کلمات)

به مثال و توضیح آن توجه کنید.

ورودی🔗

تنها خط ورودی شامل یک رشته به طول حداکثر ۲۰ حرف از حروف بزرگ انگلیسی است.

خروجی🔗

تنها خط خروجی باید شامل یک عدد باشد که برابر با جواب مسئله است.

ورودی نمونه🔗

FILIPEK

خروجی نمونه🔗

4

کریم ممکن است کلمات FILIPEK، RILIPEK، RIRIPEK یا FIRIPEK را مد نظر داشته باشد.

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

در حین تغییر دکوراسیون، همیشه حالت‌های جدیدی پیش می‌آید! "رادزینکا دوبرامیل ویچشسلافوویچ"

برای مثال، وقتی کوئرا بالاخره موفق شد که دکوراسیون شرکتش را تغییر دهد، باید دوباره کارتون‌هایی را که چند روز پیش اعضا بسته بودند، دوباره باز می‌کردند و می‌چیدند. قبل از تغییر آنها این جعبه‌ها را در یک ردیف چیده بودند و در حین تغییر، ترتیب این جعبه‌ها به هم ریخت. از این رو اعضا تصمیم گرفتند که قبل از باز کردن جعبه‌ها، آن‌ها را دوباره مرتب کنند و به حالت سابق برگردانند تا سرعتشان در چینش بیشتر شود. آنها می‌دانند که جعبه‌ای که الآن در مکان $i$ام قرار دارد، قبل از تغییر در مکان $a_i$ام بود.

حال ‌آن‌ها تعدادی کارگر گرفته‌اند (خود ناتوانند) تا جعبه‌ها را برایشان مرتب کنند. آنها در هر ثانیه می‌توانند به یک کارگر بگویند که جعبه‌ی در مکان $i$ را با جعبه‌ی در مکان $j$ عوض کند و اینکار برای هر کارگر تنها یک ثانیه طول می‌کشد. تنها نکته‌ای که وجود دارد این است که زمانی که به یک کارگر گفته‌شد که جعبه‌ی در مکان $i$ را با جعبه‌ی در مکان $j$ عوض کند، به کارگر دیگری نمی‌توان گفت که جعبه‌ی در مکان $i$ یا $j$ را با جعبه‌ی دیگری عوض کند؛ یعنی در آن ثانیه هیچ عملیات دیگری روی این دو جعبه نمی‌تواند صورت پذیرد یا به عبارت دیگر روی هر جعبه در هر ثانیه تنها یک عملیات می‌تواند انجام شود. دقت کنید که کارگر‌ها در هر ثانیه به صورت موازی کار می‌کنند.

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

ورودی🔗

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

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

$1 \le n \le 100 \ 000$ $1 \le a_i \le n$

خروجی🔗

در سطر اول خروجی کمترین تعداد ثانیه‌‌ای را که لازم دارند تا جعبه‌ها را مرتب کنند، چاپ کنید.

سپس در سطر‌های بعدی توضیح هر ثانیه را به این صورت خروجی دهید:

ابتدا تعداد عملیات‌ها را در این ثانیه خروجی دهید.

سپس در سطر‌های بعدی، در هر سطر، یک عملیات را به صورت "$a$ $b$" خروجی دهید که نمایانگر این است که یک کارگر در این ثانیه جعبه‌ی در مکان $a$ را با جعبه‌ی در مکان $b$ عوض کند.

در صورت وجود چند جواب به دلخواه یکی را چاپ کنید.

مثال🔗

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

4
2 1 4 3

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

1
2
1 2
3 4

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

3
3 2 1

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

1
1
1 3

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

3
2 3 1

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

2
1
1 2
1
1 3

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

یک روز یک خری متعلق به مناطق بیابانی به استادیوم فوتبال رفت و به دلیل خرارت(خر بودن) به جای سکوها به داخل زمین رفت. سپس او با دیدن چمن به سر شوق آمد و دیدن هزاران انسان که دور او بودند دو برابر او را ذوق زده کرد؛ احساس کنسرت به او دست داد و تصمیم گرفت که برایشان بخواند(عرعر کند)! او از موسیقی و ریتم چیزی حالی‌اش نبود اما برای اینکه عرعرش ریتمیک باشد تصمیم گرفت که بین عرعرهایش فاصله‌ی مشخصی بیندازد. برای همین او یک عدد $a$ و یک عدد $b$ انتخاب کرد و تصمیم گرفت که اینگونه بخواند:

او در ثانیه‌ی ۰ به مردم اعلام می‌کند که قرار است یک آهنگ درخواستی برایشان بخواند. سپس $a$‌ ثانیه صبر می‌کند و در ثانیه‌ی $a$ عرعر اول را سر می‌دهد. سپس $b$‌ ثانیه صبر می‌کند و در ثانیه‌ی $a+b$ عرعر دوم را سر می‌دهد. بعد دوباره $a$ ثانیه صبر می‌کند و در ثانیه‌ی $2 \times a + b$ عرعر می‌کند. سپس $b$ ثانیه صبر می‌کند و ...

او از اول با خودش قرار گذاشته بود که بیشتر از $l$ بار عرعر نکند. (حنجره‌اش طاقت بیشتر از این مقدار را نمی‌کشد) حالا او $l$‌ بار عرعر کرده است و برایش سوال است که از زمانی که به مردم اعلام کرد که قرار است برایشان بخواند تا الان که آخرین عرعر را سر داده است چند ثانیه گذشته است. او خر است و از شما می‌خواهد که به سوالش جواب بدهید.

ورودی🔗

در تنها سطر ورودی به ترتیب سه عدد $a$ و $b$ و $l$‌ می‌آید که به ترتیب نمایانگر زمان‌های صبر بین عرعرها و تعداد عرعرها می‌باشند. $1 \le a,b,l \le 1000$

خروجی🔗

در تنها خط خروجی زمان آخرین عرعر را چاپ کنید.

مثال🔗

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

1 1 1

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

1

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

3 4 5

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

17

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

10 3 2

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

13

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

در هر خانه از یک جدول $n$ در $m$ یک دومینوی ایستاده قرار داده شده است. هر دومینو یا عمودی است یا افقی (دومینوهای عمودی فقط در جهت بالا یا پایین می‌افتد و دومینوهای افقی فقط در جهت چپ یا راست). وقتی یک دومینو در یک جهت می‌افتد دومینوی موجود در خانه‌ی بعدی (در همان جهت) نیز اگر از نظر عمودی و افقی بودن مانند این دومینو باشد می‌افتد (دومینوها فقط در شرایط گفته شده بر روی دومینوهای دیگر تاثیر می‌گذارند).

می‌خواهیم تعدادی دومینو را بیاندازیم به طوری که همه‌ی دومینوها بیافتند. حداقل چند دومینو را باید بیاندازیم؟

ورودی🔗

در خط اول ورودی دو عدد $n$ و $m$ آمده است که تعداد سطرها و ستون‌های جدول را نشان می‌دهند.

در $n$ خط بعدی در هر خط، $m$ کاراکتر آمده که هر کدام نشان دهنده‌ی وضعیت یک دومینو است (| برای دومینوهای افقی و - برای دومینوهای عمودی)

$1 \le n, m \le 3000$

خروجی🔗

جواب مسئله را در یک خط چاپ کنید.

مثال🔗

ورودی نمونه🔗

3 3
|||
||-
||-

خروجی نمونه🔗

4

در ورودی نمونه سه دومینوی واقع در ستون اول را به سمت راست و دومینوی واقع در ستون سوم و سطر دوم را به سمت پایین می‌اندازیم.