شما عدد صحیح مثبتی با نام m و نیز عدد صحیح نامنفی با نام s در اختیار دارید ، وظیفه شما یافتن کوچکترین و بزرگترین عددی است که دارای طول m و مجموع ارقام s باشد ، اعداد مورد نیاز باید صحیح ، غیر منفی ، در مبنای ۱۰ و با صفر آغاز نشود.
## ورودی
ورودی در یک خط دو عدد m و s که به صورت زیر هستند را دریافت می‌کند:
$$ 1 \leq m \leq 100 $$$$ 0 \leq s \leq 900 $$
## خروجی
در خروجی دو عدد صحیح غیرمنفی در یک خط چاپ میشود که به ترتیب کوچکترین عدد موجود و بزرگترین عدد موجود میباشد. اگر هیچ عددی با توجه به شرایط مطلبوب وجود نداشت خروجی باید به شکل `1- 1-` باشد.
مثال:
| خروجی | ورودی |
|:---------:|:-----------:|
| 96 69 | 15 2|
| 1- 1- | 0 3|
طول و مجموع ارقام
شما عدد صحیح مثبتی با نام m و نیز عدد صحیح نامنفی با نام s در اختیار دارید ، وظیفه شما یافتن کوچکترین و بزرگترین عددی است که دارای طول m و مجموع ارقام s باشد ، اعداد مورد نیاز باید صحیح ، غیر منفی ، در مبنای ۱۰ و با صفر آغاز نشود.
در خروجی دو عدد صحیح غیرمنفی در یک خط چاپ میشود که به ترتیب کوچکترین عدد موجود و بزرگترین عدد موجود میباشد. اگر هیچ عددی با توجه به شرایط مطلبوب وجود نداشت خروجی باید به شکل 1- 1- باشد.
مثال:
خروجی
ورودی
96 69
15 2
1- 1-
0 3
نمره‌های درس «آمار» این ترم پایین بوده و استاد تصمیم گرفته نمره‌ی دانش آموزان را افزایش دهد. اگر نمره‌ی دانش آموز $i$ را $a-i$ در نظر بگیریم، استاد می‌خواهد نمره‌ی $b_i$ را برای او ثبت کند، به طوری که شرایط زیر برقرار باشد:
+ $a_i \leq b_i$
+ $a_i < a_j \Rightarrow b_i < b_j$
+ تمامی $b_i$ها طبیعی هستند.
برای اینکه نمره‌ها به صورت منطقی افزایش یابند، استاد می‌خواهد میانگین نمرات بعد از افزایش برابر با عدد $M$ شود و در بین حالت‌هایی که این ویژگی را دارند، پراکندگی نمرات کمینه شود. پراکندگی یک دنبالهی دلخواه مانند $c_i, c_2, \cdots , c_n$ با میانگین $T$ برابر است با :
$$\frac{\Sigma_{i=1}^{n} (c_i - T)^2}{n}$$
## ورودی
سطر اول ورودی شامل دو عدد طبیعی $n$، تعداد دانش آموزان، و عدد $M'$، به طوری که $M'= M\times n$ است.
در سطر دوم دنبالهی $a_1, a_2, \cdots, a_n$ آمده است به طوری که $a_i$ نشان‌دهنده‌ی نمره‌ی دانش‌آموز $i$ است. دنبالهی $a_i$ها اکیدا صعودی است.
## خروجی
دنبالهی $b_1, b_2, \cdots, b_n$ را در خروجط چاپ کنید. در صورت وجود چندین جواب یکی را به دلخواه چاپ کنید.
## محدودیت ها
+ $1 \leq n \leq 10^6$
+ $1 \leq a_i \leq 10^9 $
+ $\Sigma_{i=1}^{n} a_i \leq M' \leq 10^18$
## مثال
ورودی نمونه ۱
```
3 9
1 2 3
```
خروجی نمونه ۱
```
2 3 4
```
ورودی نمونه ۲
```
4 10
1 2 3 4
```
خروجی نمونه ۲
```
1 2 3 4
```
۲۶امین دوره المپیاد کامپیوتر - آزمون اول- ۱۳۹۴/۵/۳۱
نمره ها
نمره‌های درس «آمار» این ترم پایین بوده و استاد تصمیم گرفته نمره‌ی دانش آموزان را افزایش دهد. اگر نمره‌ی دانش آموز i را a−i در نظر بگیریم، استاد می‌خواهد نمره‌ی bi را برای او ثبت کند، به طوری که شرایط زیر برقرار باشد:
ai≤bi
ai<aj⇒bi<bj
تمامی biها طبیعی هستند.
برای اینکه نمره‌ها به صورت منطقی افزایش یابند، استاد می‌خواهد میانگین نمرات بعد از افزایش برابر با عدد M شود و در بین حالت‌هایی که این ویژگی را دارند، پراکندگی نمرات کمینه شود. پراکندگی یک دنبالهی دلخواه مانند ci,c2,⋯,cn با میانگین T برابر است با :
۲۶امین دوره المپیاد کامپیوتر - آزمون اول- ۱۳۹۴/۵/۳۱
این برنامه ۳ عدد ورودی می‌گیرد که عددهای اول و دوم به ترتیب تعداد سطر و ستون ماتریس اول هستند و عددهای دوم و سوم به ترتیب تعداد سطر و ستون ماتریس دوم هستند؛ سپس مقدار هر درایه ماتریس را گرفته و ضرب دو ماتریس را چاپ می‌کند.
## مثال
ورودی نمونه
```
2 3 2
1 2 3
4 5 6
1 2
3 4
5 6
```
خروجی نمونه
```
22 28
49 64
```
ضرب ماتریس‌ها
این برنامه ۳ عدد ورودی می‌گیرد که عددهای اول و دوم به ترتیب تعداد سطر و ستون ماتریس اول هستند و عددهای دوم و سوم به ترتیب تعداد سطر و ستون ماتریس دوم هستند؛ سپس مقدار هر درایه ماتریس را گرفته و ضرب دو ماتریس را چاپ می‌کند.
در پی بومی‌سازی مار و پله به بازی زیر دست یافتیم:
مهره‌ای داریم روی نقطه‌ي صفر محور یک بعدی مختصات. این مهره تنها به سمت راست حرکت می‌کند. همچنین در این بازی به جای مار و پله آیتم جدید به نام ماپله داریم. ماپله‌ها به این صورت هستند که دو سر دارند. یکی در خانه‌ی $x$ و دیگری در $y$ و هرگاه مهره‌ی ما به یکی از دو سر ماپله برسد از سمت دیگر ماپله ظاهر میشود. به ازای هر بار که مهره‌ی ما در دام یک ماپله بیفتد باید یک ریال جریمه بپردازیم. بازی هنگامی تمام میشود که مهره‌ی ما به سمت راست سمت راست‌ترین ماپله برسد در واقع در سمت راست آن دیگر سر هیچ ماپله‌ای نباشد. همچنین $n$ ماپله‌ی اولیه بر روی محور مختصات موجود است . شما باید مکان $m$ ماپله‌ی جدید را طوری تعیین کنید که جریمه‌ی پرداختی توسط ما بیشینه شود. مختصات ماپله‌های جدیدی می‌تواند هر مقداری باشد و لزومی ندارد که اعداد صحیح باشد ولی ماپله‌های ابتدایی همگی روی نقاط صحیح قرار دارند. همچنین دو سر ماپله نمی‌تواند روی هم بیفتد.
راهنمایی : ماپله‌ها هر طور که قرار گرفته باشند مهره‌ي ما به صورت یکتا حتما به سمت راست آخرین ماپله خواهد رسید.
## ورودی
+ در سطر اول ورودی عدد $n$ آمده است.
+ در سطر دوم ورودی عدد $m$ آمده است.
+ و در $n$ سطر بعدی، در هر سطر آن دو عدد آمده که نشانگر دو سر یک ماپله است.
## خروجی
در تنها سطر خروجی بیشینه مقدار جریمه‌ای که باید بپردازیم را بنویسید.
## محدودیت‌ها
+ همیشه $1 \leq n \leq 10^5$
+ همیشه $1 \leq m \leq 10^6$
+ همچنین تمامی مختصات‌ها بین ۱ تا $2 \times 10^6$ هستند.
## مثال
ورودی نمونه ۱
```
3
1
10 11
1 4
2 3
```
خروجی نمونه ۱
```
6
```
ورودی نمونه ۲
```
3
3
5 7
6 10
1999999 2000000
```
خروجی نمونه ۲
```
12
```
مارپله‌ی ایرانی
در پی بومی‌سازی مار و پله به بازی زیر دست یافتیم:
مهره‌ای داریم روی نقطه‌ي صفر محور یک بعدی مختصات. این مهره تنها به سمت راست حرکت می‌کند. همچنین در این بازی به جای مار و پله آیتم جدید به نام ماپله داریم. ماپله‌ها به این صورت هستند که دو سر دارند. یکی در خانه‌ی x و دیگری در y و هرگاه مهره‌ی ما به یکی از دو سر ماپله برسد از سمت دیگر ماپله ظاهر میشود. به ازای هر بار که مهره‌ی ما در دام یک ماپله بیفتد باید یک ریال جریمه بپردازیم. بازی هنگامی تمام میشود که مهره‌ی ما به سمت راست سمت راست‌ترین ماپله برسد در واقع در سمت راست آن دیگر سر هیچ ماپله‌ای نباشد. همچنین n ماپله‌ی اولیه بر روی محور مختصات موجود است . شما باید مکان m ماپله‌ی جدید را طوری تعیین کنید که جریمه‌ی پرداختی توسط ما بیشینه شود. مختصات ماپله‌های جدیدی می‌تواند هر مقداری باشد و لزومی ندارد که اعداد صحیح باشد ولی ماپله‌های ابتدایی همگی روی نقاط صحیح قرار دارند. همچنین دو سر ماپله نمی‌تواند روی هم بیفتد.
راهنمایی : ماپله‌ها هر طور که قرار گرفته باشند مهره‌ي ما به صورت یکتا حتما به سمت راست آخرین ماپله خواهد رسید.
مثلثی از اعداد وجود دارد(مانند شکل 2). برنامه‌ای بنویسید که بزرگترین مجموع مسیر از ریشه تا برگ را محاسبه نماید. ریشه بالاترین عدد و برگ در پایین‌ترین قسمت قرار دارند و تنها مسیرهایی مدنظر است که از ریشه شروع شود، از تمام سطوح گذشته و در برگ خاتمه یابد.
## ورودی
در سطر اول تعداد نمونه `t` مشخص شده است. در هر $t< 100$ قسمت بعد در سطر ابتدایی عدد $n<100$ تعداد سطوح مثلث آورده شده است. در `n` خط دنبالهی آن در خط `i`ام که بین 1 تا `n` است `i` عدد بین 0 تا 99 دریافت میشود.
## خروجی
برنامه‌ی شما باید به ازای هر نمونه یک عدد شامل بزرگترین مجموع مسیر از ریشه تا برگ را محاسبه نماید.
## مثال
نمونه ورودی
```
1
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
```
نمونه خروجی
```
30
```
مثلث‌ها
مثلثی از اعداد وجود دارد(مانند شکل 2). برنامه‌ای بنویسید که بزرگترین مجموع مسیر از ریشه تا برگ را محاسبه نماید. ریشه بالاترین عدد و برگ در پایین‌ترین قسمت قرار دارند و تنها مسیرهایی مدنظر است که از ریشه شروع شود، از تمام سطوح گذشته و در برگ خاتمه یابد.
در سطر اول تعداد نمونه t مشخص شده است. در هر t<100 قسمت بعد در سطر ابتدایی عدد n<100 تعداد سطوح مثلث آورده شده است. در n خط دنبالهی آن در خط iام که بین 1 تا n است i عدد بین 0 تا 99 دریافت میشود.
همانطور که می‌دانید ماشین زمان اختراع شده و حتی آقابزرگ هم برای آزمایش از آن استفاده کرده است. هدف او رفتن به سال 1500 بوده ولی ظاهرا ماشین مشکلاتی داشته و او به زمانی دیگر رفته است. محققان اثبات کرده اند که از ابتدا تا نابودی سیاره‌ی زمین را می‌توان با استفاده از خاصیت «کیتی» `n` نقطه بحرانی از زمین به `k` عصر مختلف تقسیم کرد که باشماره‌های 1 تا `k` شماره‌گذاری شده‌اند. به طور دقیق‌ر به هر عصر یه رشته‌ی `n` بیتی اختصاص داده شده به طوری که اگر نقطه‌ی `i`ام در آن عصر خاصیت «کیتی» داشته باشد، بیت `i`ام آن یک است و در غیر این صورت برابر با صفر است(دانستن خاصیت یتی تأثیری بر حل سوال نخواهد داشت). رشته‌ی مربوط به هیچ دو عصری یکسان نیست.
آقا بزرگ می‌خواهد در سریع‌تری زمان ممکن بفهمد در کدام عصر قرار دارد. برای این کار او می‌تواند یکی از نقاط بحرانی زمنی را انتخاب کند و در آن قرار بگیرد. سپس می‌تواند برای انتقال بین نقاط بحرانی از جاده‌های باستانی زمین استفاده کند. این جاده ها دو طرفه هستند و بین `n` نقطه‌ی بحرانی ساخته شده‌اند و آقابزرگ می دند که برای عبور از هریک از جاده‌ها چقدر زمان نیاز دارد. آقابزرگ، در ره نقطه‌ی بحرانی می‌تواند خاصیت «کیتی» آن نقطه را بررسی کند. او بسیار باهوش است و در نتیجه در اولین لحظه‌ای که بتواند با توجه به خواص کیتی نقاط بحرانی عصر فعلی را تشخیص دهد، متوقف میشود و بلافاصله به سال 1500 می رود. آقا بزرگ بسیار عجله دارد و می‌خواهد هرچه سریع‌تر به سال 1500 برود. به همین دلیل، می‌خواهدبدانه مستقل از عسری که در آن است، حداکثر چقدر زمان لازم دارد تا بتواند به سال 1500 برود؟
## ورودی
سطر اول ورودی شامل سه عدد طبیعی `k` تعداد عصرهای مختلف زمین، `n` تعداد نقاط بحرانی، `m` تعداد جاده‌های باستانی است.
در سطر `i`ام از `k` سطر بعدی، رشته‌ی `n` بیتی متناظر با عصر `i`ام آمده است.
در هر یک از `m` سطر بعدی، عدد `w, v ,u` آمده است که وجود یک جاده‌ی باستانی بین دو نقطه‌ی بحرانی `u` و `v` است به طوری که طی کردن آن توسط آقابزرگ، `w` ثانیه طول می کشد.
## خروجی
در تنها سطر خروجی، پاسخ مسئله را چاپ کنید.
## محدودیت‌ها
+ $1 \leq n,m \leq 1000$
+ $ 1 \leq k \leq 11$
+ $ 1 \leq w \leq 10^5 , u \ne v , 1 \leq u,v \leq n$
## مثال
ورودی نمونه ۱
```
5 4 6
0001
0000
0010
0100
1000
1 2 1
2 3 1
3 4 1
1 4 10
1 3 10
2 4 10
```
خروجی نمونه ۱
```
3
```
ورودی نمونه ۲
```
3 3 3
000
001
011
1 2 1
1 3 1
2 3 3
```
خروجی نمونه ۲
```
2
```
۲۶امین دوره المپیاد کامپیوتر - آزمون اول - ۱۳۹۴/۵/۳۱
ماشین زمان
همانطور که می‌دانید ماشین زمان اختراع شده و حتی آقابزرگ هم برای آزمایش از آن استفاده کرده است. هدف او رفتن به سال 1500 بوده ولی ظاهرا ماشین مشکلاتی داشته و او به زمانی دیگر رفته است. محققان اثبات کرده اند که از ابتدا تا نابودی سیاره‌ی زمین را می‌توان با استفاده از خاصیت «کیتی» n نقطه بحرانی از زمین به k عصر مختلف تقسیم کرد که باشماره‌های 1 تا k شماره‌گذاری شده‌اند. به طور دقیق‌ر به هر عصر یه رشته‌ی n بیتی اختصاص داده شده به طوری که اگر نقطه‌ی iام در آن عصر خاصیت «کیتی» داشته باشد، بیت iام آن یک است و در غیر این صورت برابر با صفر است(دانستن خاصیت یتی تأثیری بر حل سوال نخواهد داشت). رشته‌ی مربوط به هیچ دو عصری یکسان نیست.
آقا بزرگ می‌خواهد در سریع‌تری زمان ممکن بفهمد در کدام عصر قرار دارد. برای این کار او می‌تواند یکی از نقاط بحرانی زمنی را انتخاب کند و در آن قرار بگیرد. سپس می‌تواند برای انتقال بین نقاط بحرانی از جاده‌های باستانی زمین استفاده کند. این جاده ها دو طرفه هستند و بین n نقطه‌ی بحرانی ساخته شده‌اند و آقابزرگ می دند که برای عبور از هریک از جاده‌ها چقدر زمان نیاز دارد. آقابزرگ، در ره نقطه‌ی بحرانی می‌تواند خاصیت «کیتی» آن نقطه را بررسی کند. او بسیار باهوش است و در نتیجه در اولین لحظه‌ای که بتواند با توجه به خواص کیتی نقاط بحرانی عصر فعلی را تشخیص دهد، متوقف میشود و بلافاصله به سال 1500 می رود. آقا بزرگ بسیار عجله دارد و می‌خواهد هرچه سریع‌تر به سال 1500 برود. به همین دلیل، می‌خواهدبدانه مستقل از عسری که در آن است، حداکثر چقدر زمان لازم دارد تا بتواند به سال 1500 برود؟
سطر اول ورودی شامل سه عدد طبیعی k تعداد عصرهای مختلف زمین، n تعداد نقاط بحرانی، m تعداد جاده‌های باستانی است.
در سطر iام از k سطر بعدی، رشته‌ی n بیتی متناظر با عصر iام آمده است.
در هر یک از m سطر بعدی، عدد w, v ,u آمده است که وجود یک جاده‌ی باستانی بین دو نقطه‌ی بحرانی u و v است به طوری که طی کردن آن توسط آقابزرگ، w ثانیه طول می کشد.
۲۶امین دوره المپیاد کامپیوتر - آزمون اول - ۱۳۹۴/۵/۳۱
یک لیست از `n` عدد نامرتب داریم، می‌خواهیم عنصری که در این لیست بیش از نصف طول لیست تکرار شده است را از روشی مشابه `quick sort` در صورت وجود بیابیم. شما باید برنامه‌ای بنویسید که این لیست اعداد را بگیرد و در خروجی اگر چنین عنصری وجود داشت آن را چاپ کند و در غیر این صورت `None` چاپ شود.
## ورودی
در سطر اول تعداد اعداد و در سطر بعد لیست اعداد ورودی
## محدودیت‌ها
$$1 \leq n \leq 10^7$$
## مثال
نمونه ورودی ۱
```
13
17 89 3 3 0 4 3 3 90 3 3 32 3
```
نمونه خروجی ۱
```
3
```
نمونه ورودی ۲
```
10
2 5 67 5 5 91 13 5 10 91
```
نمونه خروجی ۲
```
None
```
عدد تکراری
یک لیست از n عدد نامرتب داریم، می‌خواهیم عنصری که در این لیست بیش از نصف طول لیست تکرار شده است را از روشی مشابه quick sort در صورت وجود بیابیم. شما باید برنامه‌ای بنویسید که این لیست اعداد را بگیرد و در خروجی اگر چنین عنصری وجود داشت آن را چاپ کند و در غیر این صورت None چاپ شود.
برنامه‌ای بنویسید که یک عدد صحیح `n` از کاربر بگیرد و پس از آن `n` رشته را از ورودی بگیرد. خروجی برنامه بزرگترین رشته‌ای مانند `s` خواهد بود که هرکدام از رشته‌ها `s` و یا وارون آن را به عنوان زیر رشته داشته باشند، اگر زیر رشته ی مشترکی وجود نداشت چیزی چاپ نشود.
زیر رشته‌ای که در خروجی چاپ میشود، باید به فرمی باشد که در رشته اول قرار دارد، مثلاً در مثال زیر ، باید `CDEF` چاپ شود، نه `FEDC`
## مثال
نمونه ورودی
```
3
ABCDEF
FEDCAB
GHCDEFJK
```
نمونه خروجی
```
CDEF
```
زیررشته مشترک
برنامه‌ای بنویسید که یک عدد صحیح n از کاربر بگیرد و پس از آن n رشته را از ورودی بگیرد. خروجی برنامه بزرگترین رشته‌ای مانند s خواهد بود که هرکدام از رشته‌ها s و یا وارون آن را به عنوان زیر رشته داشته باشند، اگر زیر رشته ی مشترکی وجود نداشت چیزی چاپ نشود.
زیر رشته‌ای که در خروجی چاپ میشود، باید به فرمی باشد که در رشته اول قرار دارد، مثلاً در مثال زیر ، باید CDEF چاپ شود، نه FEDC
فرض کنید به شما دو دنباله داده شده است و شما مسئول آن هستید که ببینید آیا ترتیب کاراکترها در دنباله دوم، همان ترتیب در دنباله اول است یا خیر؟ کافیست از راست یا از چپ ترتیب حفظ شود.
مثلاً اگر دنباله اول `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
حفظ ترتیب
فرض کنید به شما دو دنباله داده شده است و شما مسئول آن هستید که ببینید آیا ترتیب کاراکترها در دنباله دوم، همان ترتیب در دنباله اول است یا خیر؟ کافیست از راست یا از چپ ترتیب حفظ شود.
مثلاً اگر دنباله اول abcdefghi و دنباله دوم bfhi باشد، ترتیب از چپ به راست در اولی حفظ شده است. مثالی دیگر که ترتیب را از راست به چپ حفظ کند، دنباله اول abcdefghi و دنباله دوم gfdb است که ترتیب آمدن اعضای دنباله دوم در اولی از راست به چپ است و ترتیب را حفظ کرده است.
مثالی بزنیم که ترتیب را نه از راست به چپ و نه از چپ به راست، حفظ نکرده باشد. دنباله اولی abcdefghi و دنباله دومی bgic.
برنامه‌ای بنویسید که با گرفتن دنباله‌ها، مشخص کند آیا ترتیب (چه از راست و چه از چپ) حفظ شده است یا خیر.
توجه: ممکن است در دنباله دوم کاراکتری بیاید که در اولی نیست. روشن است که در این صورت پاسخ منفی است و ترتیب حفظ نشده است.
توجه: ممکن است از هر کاراکتر به هر تعداد موجود باشد. کافیست در یکی از حالات ترتیب حفظ شده باشد تا پاسخ مثبت باشد. برای مثال اگر دنباله اول abacdfeag و دنباله دوم bca باشد ترتیب حفظ شده است (با در نظر گرفتن آخرین a).
در خط اول به شما عدد 1≤n≤10 داده میشود که n بیان‌گر تعداد زوج‌های دنباله‌هاست. سپس به ازای هر زوج دنباله، در یک خط دنباله اول و در خط بعدی دنباله دوم می‌آید.
فرض کنید یک ردیف کتاب داریم که آنها را در یک قفسه از کتابخانه از چپ به راست چیده‌ایم. در این کتابخانه برای گذاشتن و برداشتن کتاب‌ها نظم خاصی وجود دارد به این صورت که اگر بخواهیم یک کتابی را در این قفسه بگذاریم فقط میتوانیم آن را سمت چپ یا سمت راست کتاب‌ها بگذاریم و برای برداشتن نیز فقط میتوانیم از سمت چپ کتاب برداریم.
در اصل میتوانیم سه عمل زیر را روی این ردیف کتاب انجام دهیم:
1. عبارت `(AddRight(X` : در این عمل کتاب با نام `X` را به سمت راست کتاب‌ها اضافه می‌کنیم.
2. عبارت `(AddLeft(X` : در این عمل کتاب با نام `X` را به سمت چپ کتاب‌ها اضافه می‌کنیم.
3. عبارت `RemoveLeft` : در این عمل کتاب سمت چپ را از قفسه برمیداریم.
می‌خواهیم برنامه‌ای بنویسیم که ابتدا یک دسته کتاب را به عنوان ورودی گرفته و سپس تعدادی از عمل‌های بالا را روی آن انجام دهد و دسته کتاب نهایی را به عنوان خروجی چاپ کند.
**برای پیاده‌سازی این برنامه لازم است از داده‌ساختار لیست پیوندی استفاده کنید.**
لیست پیوندی `(Linked list)` ساختاری شامل دنبالهای از عناصر است که هر عنصر دارای اشاره‌گری به عنصر بعدی در دنباله است.
برای پیاده‌سازی لیست پیوندی برای این مسئله یک `struct Book` تعریف میکنید که شامل یک `string Name` برای نگهداری نام کتاب و یک `Book* Next` برای اشاره به عنصر بعدی است.
سمت چپترین کتاب را اولین کتاب و راست‌ترین کتاب را آخرین کتاب در نظر میگیریم و همچنین کتاب بعدی هر کتاب را کتاب بلافاصله سمت راست آن در نظر میگیریم. دو اشارهگر مانند `Book* first` و `Book* last` برای اشاره به کتاب اول و کتاب آخر نگهداری می‌کنیم. پس از هر عمل حذف یا اضافه در سمت چپ یا راست یکی از این دو اشارهگر باید به روزرسانی شوند.
```
struct Book
{
string Name;
Book *Next;
};
```
برای هر عمل اضافه کردن کتاب ، باید از دستور `new` برای گرفتن حافظه برای `Book` جدید استفاده کنید و برای هر عمل حذف ، برای جلوگیری از نشت حافظه باید کتاب مورد نظر را با استفاده از دستور `delete` از حافظه پاک کنید.
در ادامه لیست دستوراتی که به برنامه داده میشود و مفهوم آنها آمده است:
|command| description|
|:------:|:-------:|
|AddLeft BookName|با دیدن این عبارت، باید یک کتاب به ابتدای کتابخانه(سمت چپ) اضافه شود|
|AddRight BookName|با دیدن این عبارت، باید یک کتاب به انتهای کتابخانه (سمت راست) اضافه شود|
|DeleteLeft|با دیدن این عبارت، باید چپترین کتاب در کتابخانه را حذف کنید|
|Exit| با دیدن این کاراکتر، برنامه به پایان میرسد و ابتدا تعداد کتابهای داخل کتابخانه را چاپ کنید و سپس لیست کتابهای داخل کتابخانه را به ترتیب از چپ به راست چاپ کنید|
## ورودی
ابتدا یک عدد `n` در ورودی داده میشود که نشانگر تعداد کتابهای داخل کتابخانه در ابتدای کار است سپس `n` رشته به ترتیب چپ به راست که هر کدام نام یکی از کتاب‌هاست. (نام هر کتاب رشته‌ای به طول حداکثر ۱۳۳ میباشد و از حروف کوچک و بزرگ انگلیسی و اعداد تشکیل شده است.(ممکن است در نام یک کتاب `space` نیز وجود داشته باشد.)
سپس در هر مرحله یکی از دستورات بالا داده میشود.
تعداد دستوراتی که به برنامه داده میشود حداکثر $10^6$ میباشد.
## خروجی
در سطر اول تعداد کتابهای موجود در کتابخانه چاپ شود.
در سطرهای بعدی در هر سطر نام یک کتاب از کتابهای موجود در کتابخانه چاپ شود. ترتیب چاپ کتاب‌ها از چپ به راست میباشد.
## مثال
ورودی نمونه
```
3
Mathematics
General Physics 2
Advanced Programming
DeleteLeft
AddLeft
Kelile va Demne
AddRight
Boostane Hafez
Exit
```
خروجی نمونه
```
4
Kelile va Demne
General Physics 2
Advanced Programming
Boostane Hafez
```
کتابخانه
فرض کنید یک ردیف کتاب داریم که آنها را در یک قفسه از کتابخانه از چپ به راست چیده‌ایم. در این کتابخانه برای گذاشتن و برداشتن کتاب‌ها نظم خاصی وجود دارد به این صورت که اگر بخواهیم یک کتابی را در این قفسه بگذاریم فقط میتوانیم آن را سمت چپ یا سمت راست کتاب‌ها بگذاریم و برای برداشتن نیز فقط میتوانیم از سمت چپ کتاب برداریم.
در اصل میتوانیم سه عمل زیر را روی این ردیف کتاب انجام دهیم:
عبارت (AddRight(X : در این عمل کتاب با نام X را به سمت راست کتاب‌ها اضافه می‌کنیم.
عبارت (AddLeft(X : در این عمل کتاب با نام X را به سمت چپ کتاب‌ها اضافه می‌کنیم.
عبارت RemoveLeft : در این عمل کتاب سمت چپ را از قفسه برمیداریم.
می‌خواهیم برنامه‌ای بنویسیم که ابتدا یک دسته کتاب را به عنوان ورودی گرفته و سپس تعدادی از عمل‌های بالا را روی آن انجام دهد و دسته کتاب نهایی را به عنوان خروجی چاپ کند.
برای پیاده‌سازی این برنامه لازم است از داده‌ساختار لیست پیوندی استفاده کنید.
لیست پیوندی (Linked list) ساختاری شامل دنبالهای از عناصر است که هر عنصر دارای اشاره‌گری به عنصر بعدی در دنباله است.
برای پیاده‌سازی لیست پیوندی برای این مسئله یک struct Book تعریف میکنید که شامل یک string Name برای نگهداری نام کتاب و یک Book* Next برای اشاره به عنصر بعدی است.
سمت چپترین کتاب را اولین کتاب و راست‌ترین کتاب را آخرین کتاب در نظر میگیریم و همچنین کتاب بعدی هر کتاب را کتاب بلافاصله سمت راست آن در نظر میگیریم. دو اشارهگر مانند Book* first و Book* last برای اشاره به کتاب اول و کتاب آخر نگهداری می‌کنیم. پس از هر عمل حذف یا اضافه در سمت چپ یا راست یکی از این دو اشارهگر باید به روزرسانی شوند.
struct Book
{
string Name;
Book *Next;
};
Plain text
برای هر عمل اضافه کردن کتاب ، باید از دستور new برای گرفتن حافظه برای Book جدید استفاده کنید و برای هر عمل حذف ، برای جلوگیری از نشت حافظه باید کتاب مورد نظر را با استفاده از دستور delete از حافظه پاک کنید.
در ادامه لیست دستوراتی که به برنامه داده میشود و مفهوم آنها آمده است:
command
description
AddLeft BookName
با دیدن این عبارت، باید یک کتاب به ابتدای کتابخانه(سمت چپ) اضافه شود
AddRight BookName
با دیدن این عبارت، باید یک کتاب به انتهای کتابخانه (سمت راست) اضافه شود
DeleteLeft
با دیدن این عبارت، باید چپترین کتاب در کتابخانه را حذف کنید
Exit
با دیدن این کاراکتر، برنامه به پایان میرسد و ابتدا تعداد کتابهای داخل کتابخانه را چاپ کنید و سپس لیست کتابهای داخل کتابخانه را به ترتیب از چپ به راست چاپ کنید
ابتدا یک عدد n در ورودی داده میشود که نشانگر تعداد کتابهای داخل کتابخانه در ابتدای کار است سپس n رشته به ترتیب چپ به راست که هر کدام نام یکی از کتاب‌هاست. (نام هر کتاب رشته‌ای به طول حداکثر ۱۳۳ میباشد و از حروف کوچک و بزرگ انگلیسی و اعداد تشکیل شده است.(ممکن است در نام یک کتاب space نیز وجود داشته باشد.)
سپس در هر مرحله یکی از دستورات بالا داده میشود.
تعداد دستوراتی که به برنامه داده میشود حداکثر 106 میباشد.
در سطر اول تعداد کتابهای موجود در کتابخانه چاپ شود.
در سطرهای بعدی در هر سطر نام یک کتاب از کتابهای موجود در کتابخانه چاپ شود. ترتیب چاپ کتاب‌ها از چپ به راست میباشد.
3
Mathematics
General Physics 2
Advanced Programming
DeleteLeft
AddLeft
Kelile va Demne
AddRight
Boostane Hafez
Exit
Plain text
خروجی نمونه
4
Kelile va Demne
General Physics 2
Advanced Programming
Boostane Hafez
Plain text
خانم دکتر دنبالهای از اعداد طبیعی دارد. همانطور که می‌دانید دکتر‌ها برعکس مهندس‌ها از صعودی‌بودن دنباله‌ها لذت می‌برند ولی بلد نیستند دنباله‌هایشان را صعودی کنند. برای همین خانم دکتر از آقای مهندس خواسته‌است تا دنباله‌اش را برایش صعودی کند. (منظور از دنبالهی صعودی دنبالهای است که هیچ عضوی از آن از عضو قبلی‌اش کمتر نیست) آقای مهندس در هر حرکت می‌تواند یکی از ارقام یکی از اعداد دنباله را حذف کند. دقت کنید که وقتی تمامی ارقام یکی از اعداد دنباله را حذف کنیم مقدارش صفر خواهد شد.
او به عنوان یک مهندس **مجبور است** در کمترین تعداد حرکت دنباله را صعودی کند. این کمترین تعداد حرکت چقدر است؟ همچنین او می‌خواهد جمع اعداد دنبالهی نهایی که با کمترین تعداد حرکات به آن میرسد کمینه باشد. (در عین استفاده از کمترین تعداد حرکت) این مجموع کمینه را نیز پیدا کنید.
## ورودی
سطر اول ورودی شامل عدد طبیعی $n$، تعداد اعداد دنباله، است.
در سطر بعد $n$ عدد طبیعی $a_i$ آمده‌است که اعداد دنباله را نشان می‌دهند.
+ $1\leq n \leq 50000$
+ $1\leq a_i \leq 10^18$
+ هیچ کدام از اعداد دنباله رقم $0$ ندارند.
## خروجی
در سطر اول خروجی کمترین تعداد حرکت برای صعودی کردن دنباله را چاپ کنید.
در سطر دوم $n$ عدد چاپ کنید که اعداد دنباله نهایی را نشان می‌دهند که هم باید صعودی باشند و هم مجموع‌شان کمینه شود. در صورت وجود چندین جواب هر کدام از آنها را می‌توانید چاپ کنید.
## مثال
ورودی نمونه ۱
```
4
63 54 45 36
```
خروجی نمونه ۱
```
3
3 4 4 36
```
ورودی نمونه ۲
```
6
8 16 16 1393 6 19
```
خروجی نمونه ۲
```
6
0 1 1 1 6 19
```
۲۴امین دوره المپیاد کامپیوتر - آزمون هفتم - ۱۳۹۳/۰۶/۱۹
حذف ارقام
خانم دکتر دنبالهای از اعداد طبیعی دارد. همانطور که می‌دانید دکتر‌ها برعکس مهندس‌ها از صعودی‌بودن دنباله‌ها لذت می‌برند ولی بلد نیستند دنباله‌هایشان را صعودی کنند. برای همین خانم دکتر از آقای مهندس خواسته‌است تا دنباله‌اش را برایش صعودی کند. (منظور از دنبالهی صعودی دنبالهای است که هیچ عضوی از آن از عضو قبلی‌اش کمتر نیست) آقای مهندس در هر حرکت می‌تواند یکی از ارقام یکی از اعداد دنباله را حذف کند. دقت کنید که وقتی تمامی ارقام یکی از اعداد دنباله را حذف کنیم مقدارش صفر خواهد شد.
او به عنوان یک مهندس مجبور است در کمترین تعداد حرکت دنباله را صعودی کند. این کمترین تعداد حرکت چقدر است؟ همچنین او می‌خواهد جمع اعداد دنبالهی نهایی که با کمترین تعداد حرکات به آن میرسد کمینه باشد. (در عین استفاده از کمترین تعداد حرکت) این مجموع کمینه را نیز پیدا کنید.
در سطر اول خروجی کمترین تعداد حرکت برای صعودی کردن دنباله را چاپ کنید.
در سطر دوم n عدد چاپ کنید که اعداد دنباله نهایی را نشان می‌دهند که هم باید صعودی باشند و هم مجموع‌شان کمینه شود. در صورت وجود چندین جواب هر کدام از آنها را می‌توانید چاپ کنید.
بیژن و منیژه که در مهد کودک شریف هم کلاس اند، یک بازی ساخته اند بدین صورت:
$$ax+by+c=0$$
برای $x$ یک کران پایین و یک کران بالا $(x_1,x_2)$ و برای $y$ هم یک کران پایین و یک کران بالا $(y_1,y_2)$ تعیین می‌کنند، سپس هر کدام اعدادی برای $c, b, a$ تعیین می کنند. بازیکنی که به ازای اعداد انتخابی اش تعداد جواب بیشتری برای معادله به دست آمد، برنده است و دیگری باید مشق‌هایش را بنویسد!
جواب های معادله ی بالا زوج مرتب های $(x,y)$ی هستند که $x$,$y$ عدد صحیح هستند و
$x_2 > x > x_1$
و
$y_2 < y < y_1$
برنامه ای بنویسید تا به آن ها کمک کند برنده را مشخص کنند.
## ورودی
در خط اول به ترتیب $x_1$ و $x_2$ و $y_1$ و $y_2$ وارد می شود ، در خط دوم $a$ و $b$ و $c$ای که بیژن تعیین می‌کند، در خط سوم $a$ و $b$ و $c$ای که منیژه تعیین می‌کند
## خروجی
در خط اول تعداد جواب هایی که بیژن بدست می آورد، در خط دوم تعداد جواب هایی که منیژه بدست می آورد ، در خط سوم اگر تعداد جواب ها مساوی بود `Tie` اگر بیژن برنده شده بود `bizhan won` و اگر منیژه برنده شده بود `manizhe won` چاپ شود.
## مثال
ورودی نمونه
```
-1 1 0 5
1 0 0
5 4 3
```
خروجی نمونه
```
4
0
bizhan won
```
مهد کودک شریف
بیژن و منیژه که در مهد کودک شریف هم کلاس اند، یک بازی ساخته اند بدین صورت:
ax+by+c=0
برای x یک کران پایین و یک کران بالا (x1,x2) و برای y هم یک کران پایین و یک کران بالا (y1,y2) تعیین می‌کنند، سپس هر کدام اعدادی برای c,b,a تعیین می کنند. بازیکنی که به ازای اعداد انتخابی اش تعداد جواب بیشتری برای معادله به دست آمد، برنده است و دیگری باید مشق‌هایش را بنویسد!
جواب های معادله ی بالا زوج مرتب های (x,y)ی هستند که x,y عدد صحیح هستند و
x2>x>x1
و
y2<y<y1
برنامه ای بنویسید تا به آن ها کمک کند برنده را مشخص کنند.
در خط اول تعداد جواب هایی که بیژن بدست می آورد، در خط دوم تعداد جواب هایی که منیژه بدست می آورد ، در خط سوم اگر تعداد جواب ها مساوی بود Tie اگر بیژن برنده شده بود bizhan won و اگر منیژه برنده شده بود manizhe won چاپ شود.
آقای مهندس در اتاق مدیریت خود گاوصندوق بزرگی دارد که همه‌ی اسرار بزرگ شرکت در آن نگهداری میشود. یک گاوصندوق بزرگ برای امنیت هرچه بیشتر نیاز به یک رمز خیلی بزرگ هم دارد. آقای مهندس ارقام رمز گاوصندوق‌ش را، که یک عدد طبیعی خیلی بزرگ است، پشت‌سرهم روی یک تکه کاغذ دراز نوشته و آن‌را همیشه در جیب کت‌ش نگه می‌دارد.
بچه‌ی آقای مهندس که امروز در مهدکودک کار با قیچی را برای ساختن کاردستی یاد گرفته، با دیدن کاغذ رمز گاوصندوق در جیب پدرش بسیار شگفت‌زده میشود و آن را به $n$ قطعه تقسیم می‌کند. (او همه‌ی برش‌هایش را عمودی و بین ارقام می‌زند، طوری که هیچ رقمی خراب نشود و در هر تکه از کاغذ تعدادی از ارقام پشت‌سرهم رمز قرار بگیرد)
آقای مهندس وقتی رمز را تکه‌تکه می‌بیند، آرامش خود را حفظ می‌کند، و سعی می‌کند رمز گاوصندوق را بازسازی کند. اما تنها این را به یاد دارد که رمز بر $11$ بخشپذیر بوده‌است، زیرا همانطور که می‌دانید $11$ عدد مورد علاقه‌ی خانم دکتر است. حال او از شما می‌خواهد با گرفتن اعداد نوشته‌شده روی تکه‌های کاغذ به او بگویید که در چند حالت چیدن تکه‌های کاغذ کنار هم یک رمز ممکن برای گاوصندوق درست میشود. (یعنی رمز بر $11$ بخشپذیر میشود)
## ورودی
در سطر اول ورودی عدد طبیعی $n$، تعداد قطعات کاغذ آمده است. در خط بعد اعداد طبیعی $a_1$ تا $a_n$ آمده است که $a_i$ عدد نوشته‌شده در کاغذ $i$ام را نشان می‌دهد.
+ اینکه $1 \le n \le 2000$
+ اینکه $1 \le a_i \le 10^6$
+ تضمین میشود که هیچ‌کدام از اعداد ورودی در ابتدای خود $0$ ندارند. (`leading zero` ندارند)
## خروجی
در خروجی تعداد حالت‌هایی از چیدن قطعات (از مجموع $n!$ حالت) که یک رمز ممکن برای گاوصندوق می‌سازند را چاپ کنید. (باقی‌مانده بر $10^9+7$)
## مثال
ورودی نمونه ۱
```
5
11 11 11 11 11
```
خروجی نمونه ۱
```
120
```
ورودی نمونه ۲
```
7
10 20 3 15 1000 60 16
```
خروجی نمونه ۲
```
336
```
(۲۴امین دوره المپیاد کامپیوتر - آزمون سوم - ۱۳۹۳/۰۶/۰۶)
گاو صندوق بزرگ
آقای مهندس در اتاق مدیریت خود گاوصندوق بزرگی دارد که همه‌ی اسرار بزرگ شرکت در آن نگهداری میشود. یک گاوصندوق بزرگ برای امنیت هرچه بیشتر نیاز به یک رمز خیلی بزرگ هم دارد. آقای مهندس ارقام رمز گاوصندوق‌ش را، که یک عدد طبیعی خیلی بزرگ است، پشت‌سرهم روی یک تکه کاغذ دراز نوشته و آن‌را همیشه در جیب کت‌ش نگه می‌دارد.
بچه‌ی آقای مهندس که امروز در مهدکودک کار با قیچی را برای ساختن کاردستی یاد گرفته، با دیدن کاغذ رمز گاوصندوق در جیب پدرش بسیار شگفت‌زده میشود و آن را به n قطعه تقسیم می‌کند. (او همه‌ی برش‌هایش را عمودی و بین ارقام می‌زند، طوری که هیچ رقمی خراب نشود و در هر تکه از کاغذ تعدادی از ارقام پشت‌سرهم رمز قرار بگیرد)
آقای مهندس وقتی رمز را تکه‌تکه می‌بیند، آرامش خود را حفظ می‌کند، و سعی می‌کند رمز گاوصندوق را بازسازی کند. اما تنها این را به یاد دارد که رمز بر 11 بخشپذیر بوده‌است، زیرا همانطور که می‌دانید 11 عدد مورد علاقه‌ی خانم دکتر است. حال او از شما می‌خواهد با گرفتن اعداد نوشته‌شده روی تکه‌های کاغذ به او بگویید که در چند حالت چیدن تکه‌های کاغذ کنار هم یک رمز ممکن برای گاوصندوق درست میشود. (یعنی رمز بر 11 بخشپذیر میشود)
(۲۴امین دوره المپیاد کامپیوتر - آزمون سوم - ۱۳۹۳/۰۶/۰۶)
کشور دور مورد تهاجم کشور تنبل ها قرار گرفته است. ارتش تنبل ها وارد کشور دور شده و قصد دارد هر شهری را که می تواند غارت کند. بین شهرهای کشور دور راه هایی کوهستانی با شیب های مختلف وجود دارد اما سربازان ارتش تنبلها به دلیل تنبلی فقط راه هایی را انتخاب می کنند که در مجموع کمترین شیب ممکن را طی کنند! متاسفانه پادشاه کشور دور با محدودیت سرباز مواجه است. پس تصمیم گرفته که سربازان خود را در شهرهای پراهمیت مستقر کند. او پس از مشورت با وزیران خود به این نتیجه می رسد که شهری پر اهمیت است که تعداد زیادی از مسیرهایی که ارتش تنبلها انتخاب می‌کنند از آن بگذرد.
حال شما باید به او کمک کنید و به او بگویید از هرشهر چه تعدادی از این مسیرها می‌گذرد.
## ورودی
در خط اول $1 \leq n \leq 100$ تعداد شهرها و $1 \leq m \leq 10000$ تعداد راه‌های کوهستانی بین شهرهاست. سپس در `m` خط بعدی در هر خط سه عدد `w, j , i` می‌آید که مشخص می کند از شهر `i`ام به شهر `j`ام مسیری کوهستانی با شیب `w` وجود دارد. توجه کنید که مسیرها یک‌طرفه می‌باشند.
## خروجی
در خروجی در سطر `i`ام تعداد مسیرهایی که رأس `i`ام روی آنها قرار دارد نمایش داده میشود. توجه کنید که در محاسبه این مقدار مسیرهایی که راس `i` در ابتدا یا انتهای آن واقع است شمرده نمی‌شوند.
## مثال
نمونه ورودی
```
5 4
1 2 64030
2 3 248393
3 4 31583
5 1 362418
```
نمونه خروجی
```
3
4
3
0
0
```
حمله به کشور دور
کشور دور مورد تهاجم کشور تنبل ها قرار گرفته است. ارتش تنبل ها وارد کشور دور شده و قصد دارد هر شهری را که می تواند غارت کند. بین شهرهای کشور دور راه هایی کوهستانی با شیب های مختلف وجود دارد اما سربازان ارتش تنبلها به دلیل تنبلی فقط راه هایی را انتخاب می کنند که در مجموع کمترین شیب ممکن را طی کنند! متاسفانه پادشاه کشور دور با محدودیت سرباز مواجه است. پس تصمیم گرفته که سربازان خود را در شهرهای پراهمیت مستقر کند. او پس از مشورت با وزیران خود به این نتیجه می رسد که شهری پر اهمیت است که تعداد زیادی از مسیرهایی که ارتش تنبلها انتخاب می‌کنند از آن بگذرد.
حال شما باید به او کمک کنید و به او بگویید از هرشهر چه تعدادی از این مسیرها می‌گذرد.
در خط اول 1≤n≤100 تعداد شهرها و 1≤m≤10000 تعداد راه‌های کوهستانی بین شهرهاست. سپس در m خط بعدی در هر خط سه عدد w, j , i می‌آید که مشخص می کند از شهر iام به شهر jام مسیری کوهستانی با شیب w وجود دارد. توجه کنید که مسیرها یک‌طرفه می‌باشند.
در خروجی در سطر iام تعداد مسیرهایی که رأس iام روی آنها قرار دارد نمایش داده میشود. توجه کنید که در محاسبه این مقدار مسیرهایی که راس i در ابتدا یا انتهای آن واقع است شمرده نمی‌شوند.
فرض کنید به شما دو دنباله داده شده است و شما مسئول آن هستید که ببینید آیا ترتیب کاراکترها در دنباله دوم، همان ترتیب در دنباله اول است یا خیر؟ کافیست از راست یا از چپ ترتیب حفظ شود.
مثلاً اگر دنباله اول `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
حفظ ترتیب
فرض کنید به شما دو دنباله داده شده است و شما مسئول آن هستید که ببینید آیا ترتیب کاراکترها در دنباله دوم، همان ترتیب در دنباله اول است یا خیر؟ کافیست از راست یا از چپ ترتیب حفظ شود.
مثلاً اگر دنباله اول abcdefghi و دنباله دوم bfhi باشد، ترتیب از چپ به راست در اولی حفظ شده است. مثالی دیگر که ترتیب را از راست به چپ حفظ کند، دنباله اول abcdefghi و دنباله دوم gfdb است که ترتیب آمدن اعضای دنباله دوم در اولی از راست به چپ است و ترتیب را حفظ کرده است.
مثالی بزنیم که ترتیب را نه از راست به چپ و نه از چپ به راست، حفظ نکرده باشد. دنباله اولی abcdefghi و دنباله دومی bgic.
برنامه‌ای بنویسید که با گرفتن دنباله‌ها، مشخص کند آیا ترتیب (چه از راست و چه از چپ) حفظ شده است یا خیر.
توجه: ممکن است در دنباله دوم کاراکتری بیاید که در اولی نیست. روشن است که در این صورت پاسخ منفی است و ترتیب حفظ نشده است.
توجه: ممکن است از هر کاراکتر به هر تعداد موجود باشد. کافیست در یکی از حالات ترتیب حفظ شده باشد تا پاسخ مثبت باشد. برای مثال اگر دنباله اول abacdfeag و دنباله دوم bca باشد ترتیب حفظ شده است (با در نظر گرفتن آخرین a).
در خط اول به شما عدد 1≤n≤10 داده میشود که n بیان‌گر تعداد زوج‌های دنباله‌هاست. سپس به ازای هر زوج دنباله، در یک خط دنباله اول و در خط بعدی دنباله دوم می‌آید.
