سریال


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

میلاد و پارسا که از رسیدن به مرحله‌ی نهایی کدکاپ ۳ جا ماندند، از بیچارگی به دیدن سریال رو آوردند.

سریالی که تصمیم به تماشای آن گرفته‌اند nn قسمت دارد. آن‌ها برنامه‌ریزی کرده‌اند که قسمت ii-ام را در روز aia_i ببینند. برای اینکه دچار اعتیاد به سریال نشوند در یک روز بیشتر از یک قسمت نمی‌بینند و قسمت‌ها را به ترتیب خواهند دید. (یعنی: ai<ai+1a_i < a_{i+1})

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

برای بیشینه کردن میزان یادگیری زبان، آن‌ها می‌توانند حداکثر kk بار عملیات زیر را انجام دهند: عدد ii-ام (aia_i) را انتخاب کنند و آن را برابر با xx قرار دهند به صورتی که ai1<x<ai+1a_{i-1} < x < a_{i+1}. (ممکن است با عملیات‌های پیش از این عملیات هریک از ai1a_{i-1} و یا ai+1a_{i+1} تغییر کرده باشند و برابر مقدار اولیه‌شان نباشند؛ اینجا مقدار کنونی پس از انجام تغییرات پیشین مدنظر است.)

بیشترین سطح زبانی که آنها می‌توانند پس از دیدن سریال با انجام حداکثر kk عملیات داشته باشند چقدر است؟

ورودی🔗

در سطر اول ورودی دو عدد طبیعی nn و kk با فاصله از هم آمده است. سپس در سطر بعد nn عدد a1,a2,...,ana_1, a_2, ..., a_n آمده است.

1kn100 0001 \le k \le n \le 100\ 000 1a1<a2<...<an1<an1091 \le a_1 < a_2 < ... < a_{n-1} < a_n \le 10^9

خروجی🔗

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

مثال🔗

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

3 1
1 2 4
Plain text

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

3
Plain text

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

5 2
1 3 5 6 8
Plain text

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

4
Plain text

سینما، سینما


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

میلاد و پارسا که از رسیدن به مرحله‌ی نهایی کدکاپ ۳ جا ماندند، از خجالت به شهر دورافتاده برره مهاجرت کردند و در آنجا مسئول بلیت فروشی سینما شدند.

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

ظرفیت جیب نفر ii-ام در صف را با aia_i نشان می‌دهیم. رییس از میلاد و پارسا خواسته که طوری بلیت فروشی کنند که:

۱- برای یک سالن بیشتر از BB بلیت نفروشند.

۲- کمترین هزینه را صرف پر کردن جیب افراد بکنند.

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

تضمین می‌شود که حتما می‌توانیم طوری nn نفر را بین سالن‌ها پخش کنیم که در هیچ‌یک از دو سالن بیشتر از BB نفر نرود.

ورودی🔗

در خط اول nn که تعداد افراد صف است و BB که ظرفیت سالن‌هاست به شما داده می‌شود.

در خط بعدی nn عدد داده می‌شود که عدد ii-ام اندازه جیب نفر ii-ام یا همان aia_i است.

1n3 000 1 \le n \le 3\ 000 0ai109 0 \le a_i \le 10^9 n2×Bn \le 2 \times B

خروجی🔗

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

مثال🔗

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

2 1
1000 50
Plain text

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

50
Plain text

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

3 2
50 10 1000
Plain text

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

10
Plain text

طراحی الگوریتم


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

میلاد و پارسا که از رسیدن به مرحله‌ی نهایی کدکاپ ۳ جا ماندند، تصمیم به ترک دنیای کدزنی گرفتند اما دنیای کدزنی تصمیم به ترک آن‌ها نگرفت.

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

دنباله‌‌ی aa از اعداد طبیعی متشکل از nn عضو در اختیار داریم. در هر مرحله می‌توانیم دو اندیس ii و jj متفاوت انتخاب کرده *(1i,jn1 \le i, j \le n) * و مقدار aia_i را برابر ai and aja_i \ and \ a_j قرار دهیم. کمترین تعداد مراحلی که می‌توانیم همه‌ی اعداد را صفر کنیم چیست؟

نتیجه‌ی عملیات x and yx\ and\ y عددی می‌شود که رقم ii-ام آن در مبنای دو در صورتی برابر با ۱ است که رقم ii-ام xx و yy در مبنای دو برابر با ۱ باشد.

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

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

توضیح تصویر

ورودی🔗

در خط اول عدد nn که طول دنباله است داده می‌شود. در خط بعدی nn عدد به شما داده می‌شود که عدد ii-ام همان aia_i است. 1n65 536 1 \le n \le 65\ 536 0ai<65 536 0 \le a_i < 65\ 536

خروجی🔗

یک عدد چاپ کنید که برابر کم‌ترین تعداد مراحلی است که لازم است تا همه‌ی اعداد را صفر کنیم.

مثال🔗

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

2
6242 50840
Plain text

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

2
Plain text

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

3
3 5 6
Plain text

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

4
Plain text

چندمینو


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

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

چندمینو، همانند دومینو است با این تفاوت که چندمینوها ارتفاعشان لزوما یکسان نیست. یک چندمینو مانند AA به شرطی چندمینوی دیگر مانند BB را می‌اندازد که فاصله‌شان کمتر از ارتفاع AA باشد و به همین ترتیب چندمینو BB هم پس از انداخته‌شدن توسط AA، چندمینوهای بعدی خودش را به شرط کمتر بودن فاصله‌‌شان از ارتفاع BB می‌اندازد.

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

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

در واقع تعداد اخطارهای یک تیم یکی کمتر از تعداد چندمینوهایی است که دستی انداخته است.

پارسا nn چندمینو‌ را در یک ردیف چیده است به طوری که فاصله دو چندمینوی متوالی دقیقا ۱ واحد است.

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

ورودی🔗

در خط اول ابتدا nn که تعداد چندمینوهاست به شما داده می‌شود.

در خط بعدی nn عدد به شما داده می‌شود که عدد ii-ام ارتفاع چندمینو ii-ام است. (می‌دانیم که ارتفاع چندمینوها اعدادی طبیعی و حداکثر ۲۰۰۰۰۰ است.) 1n200 000 1 \le n \le 200\ 000

خروجی🔗

در یک خط کمترین اخطاری که تیم میلاد اینا دریافت می‌کند را چاپ کنید.

مثال🔗

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

3
1 2 1
Plain text

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

1
Plain text

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

7
1 2 1 1 4 2 1
Plain text

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

1
Plain text

پل‌کشی


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

میلاد و پارسا که از رسیدن به مرحله‌ی نهایی کدکاپ ۳ جا ماندند، چشم و گوش‌شان باز شد و به فکر کسب درآمد افتادند. برای کسب درآمد ابتدا به برج‌سازی فکر کردند؛ اما پس از اینکه دیدند سوال برج‌سازی از مسابقه شماره ۲ Quera را هنوز کسی حل نکرده متوجه شدند که برج‌سازی کار سختی‌ست و برای انجام کاری ساده‌تر به فکر پل‌سازی افتادند!

میلاد و پارسا به اقیانوس اطلس رفتند و می‌خواهند طی یک پروژه‌ی بزرگ پل‌سازی، مجمع‌الجزایرهای شکرآباد را همبند کنند! در شکرآباد tt مجمع‌الجزایر وجود دارد که باید همبند شود؛ یعنی از هریک از جزیره‌های یک مجمع‌الجزایر باید بتوان با استفاده از پل‌های ساخته شده به همه‌ی جزیره‌های آن مجمع‌الجزایر رفت. این مجمع‌الجزایرها کاملاً مستقل از هم فرض می‌شوند و هریک بصورت جدا باید همبند شود. هر یک از این مجمع‌الجزایرها شامل تعدادی جزیره است که هر جزیره در نقشه به شکل یک مستطیل است. مستطیل‌های نشان‌دهنده‌ی جزیره‌ها مجزا از هم هستند و با یک‌دیگر مساحت مشترک ندارند، البته می‌توانند در ضلع با هم مشترک باشند. هم‌چنین اضلاع این مستطیل‌ها موازی با محورهای استوا و نصف‌النهار مبدأ (محورهای مختصات!) است. برای همبند کردن این جزایر این دو پل‌ساز با استفاده از ابزارآلات پیشرفته، می‌توانند پل‌هایی بکشند که در راستای محورهای مختصات باشد. (دو جزیره که ضلع مشترک هم داشته باشد هم به هم متصل نیستند و باید بین‌شان پل کشید تا به هم متصل شود.) پل‌های کشیده شده نباید با یکدیگر تقاطع داشته باشد، اما انتهای یک پل می‌تواند یک پل ساخته‌شده‌ی دیگر باشد. انتهای پل‌ها می‌تواند ضلع‌های جزیره‌ها، دریا و یا پل‌های دیگر باشد، اما نمیتواند از روی یک جزیره و یا از روی ضلع یک جزیره به طور کامل رد شود. هم‌چنین یک پل می‌تواند از یک جزیره شروع شود و در دریا تمام شود، یا حتی یک پل می‌تواند از دریا شروع شود و در دریا تمام شود!

توضیح تصویر

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

یک مثال جهت وضوع بیشتر: در عکس زیر ۱۰ جزیره‌ی مستطیلی وجود دارد که با ۱۰ پل با هم همبند شده‌اند که یکی از پاسخ‌های بهینه است.

توضیح تصویر

ورودی🔗

در اولین سطر ورودی یک عدد tt آمده است که نمایانگر تعداد مجمع‌الجزایرهای شکرستان است. سپس tt توضیح مجمع‌الجزایر آمده است. در هر یک از این توضیحات، ابتدا یک عدد nn آمده‌است که برابر تعداد جزیره‌های این مجمع‌الجزایر است. سپس در هریک از nn سطر بعدی، ۴ عدد x1x_1 ، y1y_1 ، x2x_2 و y2y_2 آمده‌است که مختصات ۴ گوشه‌ی مستطیل متناظر جزیره را نشان می‌دهند.

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

1t51 \le t \le 5 1n200 0001 \le n \le 200\ 000 x1,x2,y1,y2109|x_1, x_2, y_1, y_2| \le 10^9 x1<x2x_1 < x_2 y1<y2y_1 < y_2

خروجی🔗

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

مثال🔗

ورودی نمونه🔗

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

خروجی نمونه🔗

1
5
6
Plain text

زوج ما


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

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

دفعه آخری که میلاد و پارسا تخته نرد بازی کردند، پارسا مجموع تاس ۲۳۰ داشت و میلاد مجموع تاس ۱۵۰. میلاد به این باور رسیده‌است که نمی‌تواند در یک بازی که شانس در آن دخیل است پارسا را شکست دهد زیرا پارسا یک آدم خرشانس است.

میلاد می‌داند تنها زمینه‌ای که او از پارسا بهتر است، زبان C++C++ است، به همین دلیل پارسا را مجبور می‌کند که با او pairpair بازی کند.

بازی pairpair به این صورت است که ابتدا میلاد تعدادی کلمه pairpair یا intint پشت هم می‌نویسد که می‌توان بین آن‌ها طوری علامت گذاشت که pairpair ای قابل قبول برای C++C++ شود. (یعنی علامت های , و ‍‍< و ‍> که در میان این کلمات است را نمی‌گذارد.)

پس از آن بین کلمات pairpair و intint، به تعداد kk کلمه، pairpair یا intint دیگر اضافه می‌کند.

حال میلاد با گفتن عدد kk به پارسا از او می‌خواهد که تعداد راه‌هایی که او می‌تواند kk کلمه حذف کند به طوری که کلمات باقی‌مانده یک تعریف متغیر قابل قبول برای C++C++ باشد را به او بگوید.

از آنجایی که ممکن است این عدد خیلی بزرگ باشد پارسا باید باقیمانده آن به 109+710^9 + 7 را به میلاد بگوید.

از‌ آنجایی که پارسا سواد کافی در C++C++ ندارد از شما خواسته تا جواب میلاد را بدهید.

یک pairpair قابل قبول یک جفت به صورت pair<T1,T2> pair < T_1 , T_2 > است که در آن T1T_1 و T2T_2یا intint است یا یک pairpair قابل قبول.

با تعریف فوق مثال‌های زیر تعریف متغیر‌هایی قابل قبول می‌باشد:

pair < int , int >
pair < pair < int , int > , pair < int , int > >
pair < int , pair < pair < int , int > , int > >
Plain text

و مثال‌های زیر تعریف متغیرهایی غیر قابل قبول:

pair < int , int , int >
pair < pair < int , int > >
pair < int , pair >
Plain text

دقت کنید که حالتی وجود دارد که می‌توان طوری kk کلمه را حذف کرد به طوری که کلمات باقی‌مانده قابل قبول باشد.

ورودی🔗

در خط اول ابتدا عدد nn که تعداد کلمات رشته پس از تغییر است و سپس عدد kk به شما داده می‌شود.

در خط بعدی nn کلمه به شما داده می‌شود که هر کدام از کلمات یا pair است یا int.

4k+3n100 000 4 \le k + 3 \le n \le 100\ 000 1k10 1 \le k \le 10

خروجی🔗

باقیمانده تعداد راه‌های ممکن به 109+710^9 + 7 را در یک خط چاپ کنید.

مثال🔗

ورودی نمونه🔗

12 1
pair int pair pair int int pair pair int int int int
Plain text

خروجی نمونه🔗

7
Plain text

تیله‌های توی کیسه ۲


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

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

پس از بحث‌ها و مشاجرات فراوان، تصمیم گرفتند تا برای دادرسی به سراغ شخص ثالث بروند.

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

در ابتدا nn کیسه خالی وجود دارد. میلاد می‌خواهد طوری کیسه‌ها را پر کند که حتما برنده بازی باشد.

میلاد در هر مرحله می‌تواند دو عدد ll و rr انتخاب کند به طوری که 1lrn 1 \le l \le r \le n و به تمام کیسه‌های بین ll و rr (شامل ابتدا و انتهای‌ بازه) یک تیله اضافه کند.

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

ورودی🔗

در خط اول ابتدا nn که تعداد کیسه‌هاست و سپس qq که تعداد مراحل پر کردن است به شما داده می‌شود.

سپس در qq خط بعدی، در هر خط دو عدد lil_i و rir_i داده می‌شود که ابتدا و انتهای بازه‌ای است که در مرحله ii-ام توسط میلاد تغییر می‌کند.

1n,q100 000 1 \le n , q \le 100\ 000 1lirin 1 \le l_i \le r_i \le n

خروجی🔗

در qq خط، در خط ii ام، xorxor تعداد تیله‌های تمام کیسه‌ها پس از انجام مرحله ii ام را چاپ کنید.

مثال🔗

ورودی نمونه🔗

5 4
1 5
3 5
5 5
1 5
Plain text

خروجی نمونه🔗

1
2
3
4
Plain text