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

مهدی یه برنامه نویس تازه کاره که کلی اطلاعات مهم توی لپتاپش داره؛ برای همین سعی میکنه برای لپتابش رمزی بذاره که قوی باشه و به راحتی نشکنه.

رمز قوی رمزیه که همه ی حروف انگلیسی حداقل یک بار (بزرگ یا کوچیکش) توی رمز وجود داشته باشن. به مهدی کمک کنید یه رمز قوی واسه خودش بسازه.

ورودی🔗

خط اول شامل یک عدد است که نشان دهنده ی تعداد حروف این رشته میباشد.$1 \le n \le 100$ خط دوم شامل خود رشته می باشد که حاوی حروف کوچک و بزرگ است.

خروجی🔗

اگر این رشته یک رمز قوی است YES در غیر اینصورت NO چاپ شود.

مثال🔗

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

15
thisisnotenough

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

NO

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

35
TheQuickBrownFoxJumpsOverTheLazyDog

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

YES

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

مهدی خیلی خودش رو دوست داره. برای همین تصمیم میگیره رو هر کدوم از دیوارهای خونه اش، دوتا از عکس های خودش رو قرار بده. هر دیوار خونه مهدی یه طول و عرض خاصی داره . هر کدوم از عکس هاش هم یه طول و عرضی داره. مهدی میتونه هر کدوم از عکس هاشو 90 درجه بچرخونه.

مهدی از شما کمک خواسته تا بتونه عکس هاشو رو روی دیوارهای خونه اش جا بده. حالا شما بهش بگین ایا میتونه این عکس ها رو روی دیوار خونه اش نصب کنه یا نه؟

ورودی🔗

خط اول شامل طول و عرض دیوار خونه و در دو خط بعدی طول و عرض نقاشی آمده است که با فاصله از هم جدا شده اند.

همه اعداد در محدوده 1 تا 1000 قرار دارند.

خروجی🔗

اگر نقاشی ها را میتوان بر روی دیوار جا داد YES در غیر این صورت NO چاپ شود.

مثال🔗

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

3 2
1 3
2 1

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

YES

به این صورت میتوان تصاویر را بروی دیوار جا داد:

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

5 5
3 3
3 3

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

NO

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

4 2
2 3
1 2

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

YES

به این صورت میتوان تصاویر را بروی دیوار جا داد:

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

مهدی یه ماشین حساب قدیمی داره که فقط دوتا کار میتونه بکنه (به غیر از روشن و خاموش شدن) این که عدد روی صفحه رو در دو ضرب، یا یه واحد ازش کم کنه.

اون هر بار که ماشین حسابش رو روشن میکنه روش یه عدد تصادفی میاد. حالا مهدی میخواد اون عدد رو تبدیل کنه به عددی که میخواد. از اونجایی که مهدی آدم خسیسی هستش میخواد تا جایی که ممکنه کمتر از ماشین حساب کار بکشه.

حالا به مهدی بگید که کمترین تعداد عملی که لازمه تا به عدد مورد نظرش برسه چندتاست؟

ورودی🔗

در تنها خط ورودی دو عدد طبیعی n و m دریافت میشود که با یک فاصله از هم جدا شده اند , n اولین عدد روی ماشین حساب و m عددی است که مهدی میخواد.

$1 \le n, m \le 10^4$

خروجی🔗

یک عدد چاپ میشود که حداقل تعداد دفعاتی است که مهدی باید عملی با ماشین حسابش انجام دهد تا عدد m را از n بدست بیاورد

مثال🔗

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

4 6

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

2

یک واحد کم کرده سپس در دو ضرب میکند.

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

10 1

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

9

نه واحد کم میکند.

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

مهدی که از کارش تو شرکت بیکار شده میخواد واسه خودش یه مغازه مانتو فروشی بزنه.

اون تو انبار مغازش تعداد n مانتو دارد. هر مانتو دارای دو مشخصه قیمت ($p_{i}$) و سایز ($s_{i}$) می‌باشد که سایز هر یک از این مانتوها از سایز دیگر مانتوها متفاوت است. (یعنی برای هر سایز بیش از یک مانتو وجود ندارد!)

فرض کنید c مشتری داخل مغازه مهدی وجود دارند که هر مشتری دارای دو مشخصه مقدار موجودی کارت ($b_{i}$) و سایز($f_{i}$) می‌باشد. با این اوصاف مشتری i می‌تواند مانتو j را با شرایط زیر خریداری نماید:

• موجودی کارتش از قیمت مانتو بیشتر باشد، یعنی: $p_{j} \le b_{i}$

• سایز مانتو یا هم سایز خودش باشد یا حداکثر یک سایز بزرگتر از خودش باشد، یعنی: $f_{i}=s_{j}$ یا $f_{i}=s_{j}-1$

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

ورودی🔗

در خط اول ورودی تنها یک عدد n که بیانگر تعداد مانتوهای داخل انبار است آمده. و در n خط بعدی مشخصه های هر یک از این مانتوها با دو عدد $p_{i}$ و $s_{i}$ آمده است که با فاصله از هم جدا شده اند.

(تضمین می‌شود که هیچ یک از مشتری ها قصد خرید بیش از یک مانتو را ندارند و هر مانتو به بیش از یک مشتری فروخته نخواهد شد. همچنین تضمین می‌شود که تمام $s_{i}$ ها از هم متمایزند.)

در خط بعدی یک عدد c آمده که بیانگر تعداد مشتری‌های داخل مغازه است و در m خط بعدی مشخصه‌های هر یک از این مشتری‌ها با دو عدد $b_{i}$ و $f_{i}$ آمده است که با فاصله از هم جدا شده اند.

$1 \le n, c \le 10^5$ $1 \le p_{j}, s_{j}, b_{i}, f_{i} \le 10^9$

خروجی🔗

در تنها خط خروجی بیشینه فروش ممکن را چاپ کنید.

مثال🔗

ورودی نمونه🔗

3
100 10
300 11
200 12
2
200 10
200 11

خروجی نمونه🔗

300

در صورتیکه مشتری اول مانتوی شماره یک را خریداری کند و مشتری دوم مانتوی شماره سه را خریداری نماید، در مجموع مهدی 300 تومان فروش خواهد داشت.

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

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

فرض کنید n استاد در این جشن شرکت کرده اند و "امتیاز" استاد iام با $p_{i}$ مشخص شده است. مهدی قصد دارد صندلی و میز اساتید را بصورت زیر مشخص کند:

1. دور هر میزی حداقل سه استاد نشسته باشند.
2. مجموع "امتیاز" هر دو استادی که در مجاورت یکدیگر نشسته‌اند عددی اول باشد.

ورودی🔗

در خط اول عدد n آمده است.

در خط دوم "امتیاز" اساتید (pi ها) در n عدد آمده است که با کاراکتر فاصله از هم جدا شده‌اند. $3 \le n \le 200$ $2 \le p_{i} \le 10^4$

خروجی🔗

در خط اول خروجی عدد t را به عنوان تعداد میزهای مورد نیاز چاپ کنید و در t خط بعدی مشخصات هر یک از میزها را بصورت زیر چاپ کنید:

در هر یک از این خطوط ابتدا عدد d که بیانگر تعداد اساتیدی است که دور آن میز باید بنشینند را چاپ کنید و پس از آن "شماره ورود" هر یک از اساتیدی که دور آن میز به ترتیب ساعتگرد باید بنشینند را چاپ کنید.

درصورتیکه راه حلی برای مسئله وجود نداشت، در خروجی عبارت "Impossible" چاپ کنید.

اگر چندین حالت برای پاسخ مسئله وجود داشت، شما تنها یکی از آنها را در خروجی چاپ کنید

برای درک بهتر سوال، توضیح نمونه 2 و توضیح نمونه 3 که در ادامه متن آمده‌اند را بخوانید.

مثال🔗

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

6
2 2 2 2 2 2

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

Impossible

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

10
5 5 7 7 5 6 6 6 6 6

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

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

امتیاز ده استادی که وارد می‌شوند به ترتیب در ورودی از چپ به راست آمده است. و طبق خط اول خروجی کافیست 2 میز برای آنها تدارک دیده شود. دور میز اول 6 استاد با شماره ورودهای 1،7،2،6،5،10 به صورت ساعتگرد خواهند نشست و دور میز دوم 4 استاد با شماره ورودهای 3،8،4،9 به صورت ساعتگرد خواهند نشست.

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

4
12 7 5 6

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

1
4 1 2 4 3

این چهار نفر اگر به ترتیب با شماره های 3 , 4 ,2 ,1 دور میز بنشینند (یعنی ترتیب امتیازات دور میز بصورت 12,1,6,5 باشد) مجموع امتیاز هر دو نفر مجاور با هم عددی اول خواهد بود: 12+7=19 و 7+6=13 و 6+5=11 و 5+12=17 (دقت کنید چون دور یک میز می‌نشنیند نفر اول و چهارم نیز مجاور با هم در نظر گرفته می‌شوند.)

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

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

یه شرکت روسی دارو برای درمان کرونا پیدا کرده اما قیمتش خیلی بالاست. مهدی هم که بسیار خسیسه، حتی حاضر نیست برای جون خودش پول خرج کنه! این شرکت روسی یه مسابقه گذاشته و توش یه سوال هست که هرکس بتونه اونو حل کنه بهش داروی کرونا رو رایگان میدن.

سوال به این صورته که به شما یک دنباله a شامل n عدد صحیح داده میشود که مهدی باید تعداد بازه های این دنباله رو که مجموع اعداد اون بازه کمتر از t هست رو خروجی بده.

به طور دقیق تر شما باید تعداد زوج مرتب های به صورت $( l , r )$ را خروجی دهد که :

• $l \le r$
• $a_l + a_{l+1} + \dots + a_{r-1} + a_r < t$

به مهدی کمک کنید زنده بمونه.

ورودی🔗

خط اول به ترتیب شامل دو عدد n و t است که با فاصله از هم جدا شده اند.

در خط دوم دنباله حاوی اعداد صحیح $a_1, a_2, \dots, a_n$ داده شده است $1 \le n \le 200\,000$ $|t| \le 2\cdot10^{14}$ $|a_{i}| \le 10^{9}$

خروجی🔗

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

مثال🔗

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

5 4
5 -1 3 4 -1

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

5

در این مثال بازه های زیر مجموع کمتر از 4 دارند.

• [2, 2] با مجموع بازه $-1$
• [3, 2] با مجموع بازه $2$
• [3, 3] با مجموع بازه $3$
• [5, 4] با مجموع بازه $3$
• [5, 5] با مجموع بازه $-1$

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

3 0
-1 2 -3

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

4

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

4 -1
-2 1 -2 3

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

3

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

از قرار معلوم اون شرکت روسی که ادعا کرده بود داروی کرونا رو به حل کننده سوال به طور رایگان می ده شرکت تقلبی بوده و دارویی به دست مهدی نرسید و الان مهدی به رحمت خدا رفته :(

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

رشته ی p به صورت الفبایی کوچک تر از رشته ی q است، در صورتی که p پیش رشته ی q و نامساوی q باشد، یا i ای وجود داشته باشد که $p_{i}<q_{i}$ و به ازای j < i داشته باشیم $p_{j}=q_{j}$. به عنوان مثال:

a < b و ab < abc و abc < abd و abec < afa

امیر دوست قدیمیه مهدیه و مهدی به امیر گفته بود که آرزوش بوده که مقبرش کنار مقبره استیو جابز که از اقوام نزدیکشون بوده باشه. از اونجایی که تخصص امیر تو دبیرستان هک کردن بوده، به سیستم ارامگاه خاندان مهدی نفوذ می کنه و موفق میشه که رمز متعلق به مهدی رو عوض کنه. برای این که مقبره مهدی مقبره بلافاصله بعدی مقبره استیو جابز باشه امیر باید رمز مهدی رو به گونه ای تغییر بده که کوچکترین رمز بزرگتر از رمز استیو جابز باشه. از اونجایی که خاندان مهدی توی رمزشون از حروف خاصی استفاده می کنن امیر نمی خواد ریسک کنه و فقط از حروف رمز استیو جابز استفاده کنه؛ یعنی اگه مثلا رمز استیو جابز رشته ی acd هستش، امیر می خواد فقط از حروف a و c و d استفاده کنه (که پاسخ می شه ada)

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

ورودی🔗

در خط اول ورودی دو عدد n و k وجود دارد به صورتی که: $1 \le n,k \le 100000$ که n طول رمز استیو جابز و k طول رمز لازم برای مهدی است. خط دوم ورودی شامل یک رشته با حروف کوچک است که رمز استیو جابز میباشد.

خروجی🔗

در تنها خط خروجی باید رمز مهدی را بنویسید. تضمین میشود که همچین رمزی وجود دارد.

مثال🔗

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

3 3
abc

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

aca

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

3 2
abc

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

ac

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

3 3
ayy

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

yaa