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

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

ورودی🔗

ورودی شامل چهار خط است. در دو خط اول ورودی دو عدد صحیح $n$ و $k$ آمده است که به ترتیب نشان دهنده‌ی تعداد مبتلایان و تعداد فوتی‌های کشور شکرستان است.

$1 \leq k \leq n \leq 1000$

در خطوط سوم و چهارم ورودی، دو عدد صحیح $p$ و $q$ آمده است که به ترتیب تعداد مبتلایان و تعداد فوتی‌های کشور نمکستان را نشان می‌دهد.

$1 \leq q \leq p \leq 1000$

خروجی🔗

در تنها خط خروجی، در صورتی که داروهای کشور شکرستان موثرتر بوده است عبارت Shekarestan، درصورتی که داروهای کشور نمکستان موثرتر بوده است Namakestan و در غیر این صورت عبارت Equal را چاپ کنید.

مثال‌ها🔗

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

2
1
4
1

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

Namakestan

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

3
1
4
2

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

Equal

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

5
1
4
2

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

Shekarestan

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

دانشگاه صنعتی شکرستان $n$ دانشجو با شماره‌های دانشجویی ١ تا $n$ دارد که هر کدام می‌توانند در تعدادی از کلاس‌های ترم جاری ثبت نام کنند (این تعداد می‌تواند صفر باشد). برنامه‌ای بنویسید که بتواند پاسخ $q$ پرسش ما را بدهد. هر پرسش به این صورت است که شماره‌ی تعدادی از کلاس‌ها را به عنوان ورودی به برنامه می‌دهیم و برنامه باید تعداد دانشجویانی که در تمام این کلاس‌ها ثبت نام کرده‌اند را به عنوان خروجی بدهد.

ورودی🔗

در خط اول به ترتیب $n$ و $k$ و $q$ داده می‌شود که $n$ تعداد دانشجویان، $k$ تعداد کلاس‌های ترم جاری و $q$ تعداد سوال‌هایی است که از برنامه می‌پرسیم.

در $k$ خط بعدی، در خط $i$ام ابتدا تعداد دانشجویانی که در درس $i$ام ثبت نام کرده‌اند و سپس شماره‌ی دانشجویانی که در درس $i$ام ثبت نام کرده‌اند، داده شده است. شماره‌ی دانشجویان از ١ تا $n$ است.

در $q$ سطر بعدی در هر سطر یک سوال از برنامه پرسیده می‌شود، در هر کدام از این $q$ سطر، ابتدا تعداد کلاس‌ها و سپس شماره‌ی کلاس‌هایی که در مورد آن‌ها سوال می‌شود، داده می‌شود. شماره‌ی کلاس‌ها از ١ تا $k$ است.

$1 \leq n \leq 200$ $1 \leq k, q \leq 500$

خروجی🔗

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

مثال‌ها🔗

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

4 4 3
3 1 2 3
3 1 2 4
1 4
2 2 4
2 1 2
3 1 2 3
2 2 4

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

2
0
2

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

رشته‌ای باینری (شامل رقم‌های 0 و 1 (به طول $n$ داریم. می‌خواهیم حداقل تعداد بیت‌هایی را تغییر دهیم که رشته‌ای قابل قبول ایجاد کنیم. رشته‌ای قابل قبول است، اگر هیچ زیر رشته (نه لزوما متوالی) به صورت 010 یا 101 نداشته باشد. برای مثال رشته‌های 1000 و 0001 قابل قبول و رشته‌های 1001 و 0110 غیر قابل قبول هستند. حداقل تعداد بیت لازم را بیابید که با تغییر آن‌ها به رشته‌ای قابل قبول برسیم.

ورودی🔗

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

$1 \leq n \leq 1000$

خروجی🔗

در تنها خط خروجی، حداقل تعداد بیت‌های لازم را اعلام کنید که با تغییر آن‌ها، رشته‌ی ورودی قابل قبول شود.

مثال‌ها🔗

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

4
0000

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

0

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

4
0101

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

1

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

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

ورودی🔗

ورودی شامل دو خط است. در خط اول دو عدد طبیعی $n$ و $k$ داده می‌شوند که به ترتیب تعداد ارقام خرید و تعداد ارقامی که اکبر باید حذف کند، را نشان می‌دهند. در خط بعدی یک عدد طبیعی $n$ رقمی داده می‌شود.

$1 \leq k \lt n \leq 2000$

خروجی🔗

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

مثال‌ها🔗

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

7 3
1231234

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

3234

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

10 4
4177252841

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

775841

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

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

ورودی🔗

خط اول ورودی شامل دو عدد صحیح $n$ و $k$ است. خط دوم شامل $n$ حرف بزرگ انگلیسی است. حرف A به معنای رنگ اول، حرف B به معنای رنگ دوم، و به همین ترتیب تا حرف Z به معنای رنگ ٢۶ام است. تنها $k$ حرف اول انگلیسی می‌توانند ظاهر شوند. هر حرف نماینده‌ی رنگ خانه متناظرش در نوار است.

$1 \leq n \leq 5 \times 10^5$ $2 \leq k \leq 26$

خروجی🔗

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

مثال‌ها🔗

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

6 3
ABBACC

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

2

در مثال بالا با تغییر دادن رنگ خانه‌ها از ABBACC به ACBABC به خواسته ی مورد نظر می‌رسیم.

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

3 2
BBA

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

1

در مثال بالا کافی است رنگ خانه‌ی اول را به A تغییر دهیم.

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

احمد $n$ شیء و $m$ جعبه دارد که هر جعبه اندازه‌اش برابر $k$ است. اشیاء به ترتیب از چپ به راست با ١ تا $n$ شماره گذاری شده‌اند و اندازه‌ی شیء $i$ام برابر $a_i$ است.

با احمد می‌خواهد اشیاء را درون جعبه‌ها قرار دهد و برای این کار الگوریتم زیر را اجرا می‌کند:

ابتدا یک جعبه‌ی خالی در دستش می‌گیرد و یک عدد $1 \leq j \leq n$ انتخاب می‌کند. سپس از شیء $j$ام شروع می‌کند و آن را در جعبه‌ی فعلی قرار می‌دهد و به سراغ شیء $j + 1$ام می‌رود. حال اگر شیء $j + 1$ام در جعبه‌ی فعلی بتواند قرار بگیرد، آن را در جعبه ی فعلی قرار می‌دهد. در غیر این صورت، جعبه‌ی فعلی را بسته بندی کرده و کنار می‌گذارد و جعبه‌ی خالی دیگری را برمی دارد تا شیء $j + 1$ام را در آن قرار دهد. او این کار را تا زمانی تکرار می‌کند که شیء $n$ام در جعبه‌ای قرار بگیرد و یا جعبه‌هایش تمام شود. سپس الگوریتم پایان می‌یابد. احمد می‌خواهد حتماً تمام شیءهای $j$ تا $n$ را در جعبه‌ای قرار داده باشد. بنابراین اگر هنگام قرار دادن یک شیء، آن شیء را نتواند در جعبه‌ی فعلی‌اش قرار دهد و جعبه‌های خالی‌اش نیز تمام شده باشند، به هدفش نرسیده است.

به احمد کمک کنید عدد $j$ را طوری انتخاب کند که بیش ترین تعداد شیء را بتواند در جعبه‌ها قرار دهد و تمام اشیاء از $j$ تا $n$ درون جعبه‌ها قرار گرفته باشند.

ورودی🔗

در خط اول ورودی به ترتیب سه عدد صحیح $n$ و $m$ و $k$ آمده اند که تعداد اشیاء، تعداد جعبه‌ها و اندازه‌ی جعبه‌ها را نشان می‌دهند.

$1 \leq n, m \leq 2 \times 10^5$ $1 \leq k \leq 10^9$

در خط بعدی، $n$ عدد $a_1, a_2, \dots, a_n\,$ آمده اند که $a_i$ نمایانگر اندازه‌ی شیء $i$ام است.

$1 \leq a_i \leq k$

خروجی🔗

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

مثال‌ها🔗

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

5 2 6
5 2 1 4 2

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

4

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

5 1 4
4 2 3 4 1

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

1

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

میلاد یک دانشجوی عاشق برنامه نویسی است. یک روز میلاد در حالی که داشت به یکی از سوالات مسابقه‌ی سال‌های پیش ICPC فکر می‌کرد، به خودش آمد و دید تعداد زیادی رقم روی کاغذ چرک نویسش نوشته است. پس از بررسی‌های فراوان میلاد فهمید که روی کاغذ، $a_0$ بار صفر، $a_1$ بار یک و... و $a_9$ بار نه نوشته است.

او که شیفته‌ی عدد ١١ است، می‌خواهد بداند چند عدد $\sum_{i = 0}^{9} a_i$ رقمی متشکل از ارقامی که میلاد روی کاغذش نوشته است وجود دارد که بر ١١ بخش پذیر باشد. به میلاد کمک کنید این تعداد را پیدا کند. از آن جایی که این عدد ممکن است خیلی بزرگ باشد، باقی‌مانده‌ی آن را بر $10^9 + 7$ بیابید. توجه کنید که صفر در ابتدای عدد مجاز است.

ورودی🔗

در تنها خط ورودی ۱۰ عدد صحیح آمده است که به ترتیب نشان دهنده ی اعداد $a_0$ تا $a_9$ است.

$0 \leq a_i \leq 200$ $1 \leq \sum_{i = 0}^{9} a_i \leq 200$

خروجی🔗

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

مثال‌ها🔗

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

0 2 1 0 0 0 0 0 0 0

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

1

در مثال بالا، تنها عدد ممکن ١٢١ است.

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

0 0 0 0 0 0 0 0 2 2

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

4

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

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

1. جمع عددهای ورق‌ها از اول دفتر تا همین صفحه (شامل همین صفحه)
2. جمع عددهای ورق‌ها از آخر دفتر تا همین صفحه (شامل همین صفحه)

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

ورودی🔗

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

$1 \leq n \leq 1000$

در $n$ خط بعدی، در خط $i$ام، دو عدد طبیعی $b_i$ و $r_i$ آمده است که به ترتیب عدد آبی و عدد قرمز روی یکی از ورق‌ها را نشان می‌دهد.

$1 \leq b_i \leq 10^6$ $1 \leq r_i \leq 10^9$

تضمین می‌شود حداقل به یک روش می‌توان ورق‌ها را مرتب کرد طوری که شرط مسئله برقرار باشد.

خروجی🔗

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

مثال‌ها🔗

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

3
2 3
1 1
3 6

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

2

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

4
4 16
4 16
4 8
4 8

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

4

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

7
1 1
2 27
3 6
4 22
5 18
6 21
7 7

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

2

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

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

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

ورودی🔗

در خط اول ورودی $n$، تعداد ستون‌ها، داده می‌شود. در $n$ خط بعدی، اطلاعات مربوط به ستون‌ها، به ترتیب داده می‌شود. در خط $i$ام، به ترتیب اعداد صحیح $a_i$ و $b_i$ داده می‌شوند که به ترتیب ارتفاع ستون $i$ام و هزینه‌ی افزایش یک واحد آن هستند.

$1 \leq n \leq 10^5$ $1 \leq a_i, b_i \leq 10^4$

خروجی🔗

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

مثال‌ها🔗

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

6
2 5
3 4
3 20
3 3
4 2
6 10

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

9

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

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

3
11 10
10 4
10 10

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

8

در مثال بالا برای کم ترین هزینه باید ارتفاع ستون دوم، دو واحد افزایش یابد.

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

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

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

برای مثال اگر رشته نمایانگر لکه‌ی aabcx باشد، هنرمند می‌تواند زیررشته‌ی aa را حذف کند چون پالیندروم است و سپس کاراکتر آخر را به b تغییر دهد تا رشته تبدیل به bcb شود. سپس در یک مرحله‌ی دیگر می‌تواند این رشته‌ی پالیندروم را حذف کند.

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

ورودی🔗

در تنها خط ورودی رشته‌ی $S$ از حروف کوچک انگلیسی که نمایانگر لکه است، به شما ورودی داده می‌شود.

$1 \leq |S| \leq 500$

خروجی🔗

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

مثال‌ها🔗

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

abcba

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

1

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

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

abcbx

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

2

در مثال بالا در حرکت اول می‌توان حرف آخر را تبدیل به a کرد و سپس در حرکت دوم رشته‌ی پالیندروم به دست آمده را حذف کرد.

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

aabcx

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

3