+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- میلاد و پارسا که از رسیدن به مرحله‌ی نهایی کدکاپ ۳ جا ماندند، از بیچارگی به دیدن سریال رو آوردند. سریالی که تصمیم به تماشای آن گرفته‌اند $n$ قسمت دارد. آن‌ها برنامه‌ریزی کرده‌اند که قسمت $i$-ام را در روز $a_i$ ببینند. برای اینکه دچار اعتیاد به سریال نشوند در یک روز بیشتر از یک قسمت نمی‌بینند و قسمت‌ها را به ترتیب خواهند دید. (یعنی: $a_i < a_{i+1}$) میلاد و پارسا می‌خواهند علاوه بر لذتی که از دیدن سریال می‌برند زبانشان نیز قوی بشود. اگر طول بیشترین تعداد روز متوالی که در هر روزش یک قسمت سریال می‌بینند $x$ باشد، زبان آن‌ها به سطح $x$ می‌رسد. برای بیشینه کردن میزان یادگیری زبان، آن‌ها می‌توانند حداکثر $k$ بار عملیات زیر را انجام دهند: عدد $i$-ام ($a_i$) را انتخاب کنند و آن را برابر با $x$ قرار دهند به صورتی که $a_{i-1} < x < a_{i+1}$. (ممکن است با عملیات‌های پیش از این عملیات هریک از $a_{i-1}$ و یا $a_{i+1}$ تغییر کرده باشند و برابر مقدار اولیه‌شان نباشند؛ اینجا مقدار کنونی پس از انجام تغییرات پیشین مدنظر است.) بیشترین سطح زبانی که آنها می‌توانند پس از دیدن سریال با انجام حداکثر $k$ عملیات داشته باشند چقدر است؟ # ورودی در سطر اول ورودی دو عدد طبیعی $n$ و $k$ با فاصله از هم آمده است. سپس در سطر بعد $n$ عدد $a_1, a_2, ..., a_n$ آمده است. $$1 \le k \le n \le 100\ 000$$ $$1 \le a_1 < a_2 < ... < a_{n-1} < a_n \le 10^9$$ # خروجی در تنها سطر خروجی بیشترین سطح زبانی را که آنها می‌توانند پس از دیدن سریال با انجام حداکثر $k$ عملیات داشته باشند چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 3 1 1 2 4 ``` ## خروجی نمونه ۱ ``` 3 ``` ## ورودی نمونه ۲ ``` 5 2 1 3 5 6 8 ``` ## خروجی نمونه ۲ ``` 4 ```

سریال

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

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

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

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

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

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

ورودی🔗

در سطر اول ورودی دو عدد طبیعی $n$ و $k$ با فاصله از هم آمده است. سپس در سطر بعد $n$ عدد $a_1, a_2, ..., a_n$ آمده است.

$1 \le k \le n \le 100\ 000$ $1 \le a_1 < a_2 < ... < a_{n-1} < a_n \le 10^9$

خروجی🔗

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

مثال🔗

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

3 1
1 2 4

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

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

5 2
1 3 5 6 8

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

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- میلاد و پارسا که از رسیدن به مرحله‌ی نهایی کدکاپ ۳ جا ماندند، از خجالت به شهر دورافتاده برره مهاجرت کردند و در آنجا مسئول بلیت فروشی سینما شدند. سینما برره دو سالن دارد که فیلم‌های متفاوتی را نشان می‌دهد و هرکدام ظرفیت $B$ نفر آدم را دارد. مردم برره، مردمی فرهیخته هستند و اعتقاد زیادی به صف دارند اما یک عادت بد دارند، هر شخص دوست دارد فیلمی را ببیند که نفر جلویی‌اش در صف می‌بیند و به صورت پیش‌فرض بلیت همان فیلم را می‌خرد مگر اینکه به او به اندازه جیبش پول بدهیم تا راضی شود فیلم دیگر را ببیند. ظرفیت جیب نفر $i$-ام در صف را با $a_i$ نشان می‌دهیم. رییس از میلاد و پارسا خواسته که طوری بلیت فروشی کنند که: ۱- برای یک سالن بیشتر از $B$ بلیت نفروشند. ۲- کمترین هزینه را صرف پر کردن جیب افراد بکنند. از شما می‌خواهیم این کمترین هزینه را برای میلاد و پارسا، دو دوست مهربان قصه‌ی ما، حساب کنید. تضمین می‌شود که حتما می‌توانیم طوری $n$ نفر را بین سالن‌ها پخش کنیم که در هیچ‌یک از دو سالن بیشتر از $B$ نفر نرود. # ورودی در خط اول $n$ که تعداد افراد صف است و $B$ که ظرفیت سالن‌هاست به شما داده می‌شود. در خط بعدی $n$ عدد داده می‌شود که عدد $i$-ام اندازه جیب نفر $i$-ام یا همان $a_i$ است. $$ 1 \le n \le 3\ 000$$ $$ 0 \le a_i \le 10^9 $$ $$n \le 2 \times B$$ # خروجی در یک خط کمترین هزینه لازم برای برآورده کردن شرط‌ها را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 2 1 1000 50 ``` ## خروجی نمونه ۱ ``` 50 ``` ## ورودی نمونه ۲ ``` 3 2 50 10 1000 ``` ## خروجی نمونه ۲ ``` 10 ```

سینما، سینما

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

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

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

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

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

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

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

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

ورودی🔗

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

در خط بعدی $n$ عدد داده می‌شود که عدد $i$ -ام اندازه جیب نفر $i$ -ام یا همان $a_i$ است.

$1 \le n \le 3\ 000$ $0 \le a_i \le 10^9$ $n \le 2 \times B$

خروجی🔗

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

مثال🔗

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

2 1
1000 50

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

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

3 2
50 10 1000

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

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- میلاد و پارسا که از رسیدن به مرحله‌ی نهایی کدکاپ ۳ جا ماندند، تصمیم به ترک دنیای کدزنی گرفتند اما دنیای کدزنی تصمیم به ترک آن‌ها نگرفت. متاسفانه آن‌ها در امتحان درس طراحی الگوریتم با سوالی مواجه شدند که قادر به حل آن نیستند. متن سوال به صورت زیر است: *دنباله‌‌ی $a$ از اعداد طبیعی متشکل از $n$ عضو در اختیار داریم. در هر مرحله می‌توانیم دو اندیس $i$ و $j$ متفاوت انتخاب کرده *($1 \le i, j \le n$) * و مقدار $a_i$ را برابر $a_i \ and \ a_j$ قرار دهیم. کمترین تعداد مراحلی که می‌توانیم همه‌ی اعداد را صفر کنیم چیست؟* نتیجه‌ی عملیات $x\ and\ y$ عددی می‌شود که رقم $i$-ام آن در مبنای دو در صورتی برابر با ۱ است که رقم $i$-ام $x$ و $y$ در مبنای دو برابر با ۱ باشد. میلاد و پارسا را دیگر بکشیدشان هم دست به کیبورد نمی‌زنند پس شما باید کدی بزنید که با گرفتن دنباله کمترین تعداد مراحل را چاپ کند. تضمین می‌شود که حتما می‌توانیم همه اعداد دنباله ورودی را بعد از انجام تعدادی مرحله صفر کنیم. ![توضیح تصویر](https://blog.quera.ir/wp-content/uploads/2018/05/da-lq.jpg) # ورودی در خط اول عدد $n$ که طول دنباله است داده می‌شود. در خط بعدی $n$ عدد به شما داده می‌شود که عدد $i$-ام همان $a_i$ است. $$ 1 \le n \le 65\ 536 $$ $$ 0 \le a_i < 65\ 536 $$ # خروجی یک عدد چاپ کنید که برابر کم‌ترین تعداد مراحلی است که لازم است تا همه‌ی اعداد را صفر کنیم. # مثال ## ورودی نمونه ۱ ``` 2 6242 50840 ``` ## خروجی نمونه ۱ ``` 2 ``` ## ورودی نمونه ۲ ``` 3 3 5 6 ``` ## خروجی نمونه ۲ ``` 4 ```

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

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

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

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

دنباله‌‌ی $a$ از اعداد طبیعی متشکل از $n$ عضو در اختیار داریم. در هر مرحله می‌توانیم دو اندیس $i$ و $j$ متفاوت انتخاب کرده *( $1 \le i, j \le n$ ) * و مقدار $a_i$ را برابر $a_i \ and \ a_j$ قرار دهیم. کمترین تعداد مراحلی که می‌توانیم همه‌ی اعداد را صفر کنیم چیست؟

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

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

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

توضیح تصویر

ورودی🔗

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

خروجی🔗

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

مثال🔗

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

2
6242 50840

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

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

3
3 5 6

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

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- میلاد و پارسا که از رسیدن به مرحله‌ی نهایی کدکاپ ۳ جا ماندند، تصمیم به ترک دنیای کدزنی گرفتند و خود را برای لیگ‌ جهانی *چندمینو* آماده می‌کنند. چندمینو، همانند دومینو است با این تفاوت که چندمینوها ارتفاعشان لزوما یکسان نیست. یک چندمینو مانند $A$ به شرطی چندمینوی دیگر مانند $B$ را می‌اندازد که فاصله‌شان **کمتر** از ارتفاع $A$ باشد و به همین ترتیب چندمینو $B$ هم پس از انداخته‌شدن توسط $A$، چندمینوهای بعدی خودش را به شرط **کمتر** بودن فاصله‌‌شان از ارتفاع $B$ می‌اندازد. دقت کنید که چندمینوها در یک ردیف چیده شده‌اند و تنها در یک جهت، می‌افتند. (یعنی یک چندمینو پس از افتادن یا چندمینوهای قبلی خودش را می‌اندازد یا چندمینوهای بعدی) در لیگ چندمینو هر تیم در شروع تنها می‌تواند یک چندمینو را بیندازد. چنانچه پس از انداختن اولین چندمینو همه چندمینوها نیفتد، داوران در ازای دادن یک اخطار به آن تیم اجازه می‌دهند که یکبار دیگر چندمینویی دیگر را بیندازد و این روال تا زمانی که همه چندمینوها بیفتد ادامه دارد. یک تیم در یک مرحله می‌تواند هریک از چندمینوها را به هریک از ۲ جهت راست یا چپ که انتخاب کرد بیندازد. در واقع تعداد اخطارهای یک تیم یکی کمتر از تعداد چندمینوهایی است که دستی انداخته است. پارسا $n$ چندمینو‌ را در یک ردیف چیده است به طوری که فاصله دو چندمینوی متوالی دقیقا ۱ واحد است. حال میلاد می‌خواهد بداند با توجه به چینش پارسا کمترین اخطاری که تیم‌شان دریافت می‌کند چقدر است. از آنجایی که میلاد و پارسا دیگر کیبورد‌هایشان را آویزان کرده‌اند از شما می‌خواهند که بهشان کمک کنید. # ورودی در خط اول ابتدا $n$ که تعداد چندمینوهاست به شما داده می‌شود. در خط بعدی $n$ عدد به شما داده می‌شود که عدد $i$-ام ارتفاع چندمینو $i$-ام است. (می‌دانیم که ارتفاع چندمینوها اعدادی طبیعی و حداکثر ۲۰۰۰۰۰ است.) $$ 1 \le n \le 200\ 000$$ # خروجی در یک خط کمترین اخطاری که تیم میلاد اینا دریافت می‌کند را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 3 1 2 1 ``` ## خروجی نمونه ۱ ``` 1 ``` ## ورودی نمونه ۲ ``` 7 1 2 1 1 4 2 1 ``` ## خروجی نمونه ۲ ``` 1 ```

چندمینو

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

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

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

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

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

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

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

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

ورودی🔗

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

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

خروجی🔗

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

مثال🔗

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

3
1 2 1

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

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

7
1 2 1 1 4 2 1

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

+ محدودیت زمان: ۴ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- میلاد و پارسا که از رسیدن به مرحله‌ی نهایی کدکاپ ۳ جا ماندند، چشم و گوش‌شان باز شد و به فکر کسب درآمد افتادند. برای کسب درآمد ابتدا به برج‌سازی فکر کردند؛ اما پس از اینکه دیدند سوال برج‌سازی از مسابقه شماره ۲ *Quera* را هنوز کسی حل نکرده متوجه شدند که برج‌سازی کار سختی‌ست و برای انجام کاری ساده‌تر به فکر پل‌سازی افتادند! میلاد و پارسا به اقیانوس اطلس رفتند و می‌خواهند طی یک پروژه‌ی بزرگ پل‌سازی، مجمع‌الجزایرهای شکرآباد را همبند کنند! در شکرآباد $t$ مجمع‌الجزایر وجود دارد که باید همبند شود؛ یعنی از هریک از جزیره‌های یک مجمع‌الجزایر باید بتوان با استفاده از پل‌های ساخته شده به همه‌ی جزیره‌های آن مجمع‌الجزایر رفت. این مجمع‌الجزایرها کاملاً مستقل از هم فرض می‌شوند و هریک بصورت جدا باید همبند شود. هر یک از این مجمع‌الجزایرها شامل تعدادی جزیره است که هر جزیره در نقشه به شکل یک مستطیل است. مستطیل‌های نشان‌دهنده‌ی جزیره‌ها *مجزا* از هم هستند و با یک‌دیگر مساحت مشترک ندارند، البته می‌توانند در ضلع با هم مشترک باشند. هم‌چنین اضلاع این مستطیل‌ها موازی با محورهای استوا و نصف‌النهار مبدأ (محورهای مختصات!) است. برای همبند کردن این جزایر این دو پل‌ساز با استفاده از ابزارآلات پیشرفته، می‌توانند پل‌هایی بکشند که در راستای محورهای مختصات باشد. (دو جزیره که ضلع مشترک هم داشته باشد هم به هم متصل نیستند و باید بین‌شان پل کشید تا به هم متصل شود.) پل‌های کشیده شده نباید با یکدیگر تقاطع داشته باشد، اما انتهای یک پل می‌تواند یک پل ساخته‌شده‌ی دیگر باشد. انتهای پل‌ها می‌تواند ضلع‌های جزیره‌ها، دریا و یا پل‌های دیگر باشد، اما نمیتواند از روی یک جزیره و یا از روی ضلع یک جزیره به طور کامل رد شود. هم‌چنین یک پل می‌تواند از یک جزیره شروع شود و در دریا تمام شود، یا حتی یک پل می‌تواند از دریا شروع شود و در دریا تمام شود! ![توضیح تصویر](https://blog.quera.ir/wp-content/uploads/2018/05/bridge-lq.jpg) حال میلاد و پارسا متوجه شدند که علی‌رغم تمام تلاش‌شان، باز هم به مسئله‌ای برنامه‌نویسی برخوردند و سر به بیابان زده و این سوال را برای شما باقی گذاشتند. پس شما با ورودی گرفتن نقشه‌ی هر مجمع‌الجزایر، کم‌ترین تعداد پل‌هایی را بگویید که با وصل کردن‌شان طبق شرایط گفته شده تمام جزیره‌های این مجمع‌الجزایر همبند شود. **یک مثال جهت وضوع بیشتر:** در عکس زیر ۱۰ جزیره‌ی مستطیلی وجود دارد که با ۱۰ پل با هم همبند شده‌اند که یکی از پاسخ‌های بهینه است. ![توضیح تصویر](https://blog.quera.ir/wp-content/uploads/2018/05/sample.png) # ورودی در اولین سطر ورودی یک عدد $t$ آمده است که نمایانگر تعداد مجمع‌الجزایرهای شکرستان است. سپس $t$ توضیح مجمع‌الجزایر آمده است. در هر یک از این توضیحات، ابتدا یک عدد $n$ آمده‌است که برابر تعداد جزیره‌های این مجمع‌الجزایر است. سپس در هریک از $n$ سطر بعدی، ۴ عدد $x_1$ ، $y_1$ ، $x_2$ و $y_2$ آمده‌است که مختصات ۴ گوشه‌ی مستطیل متناظر جزیره را نشان می‌دهند. تضمین می‌شود مستطیل‌های داده شده در شرایط صورت سوال صدق می‌کنند. دقت کنید که مجمع‌الجزایرها مستقل از هم هستند؛ یعنی ممکن است دو مستطیل از دو مجمع‌الجزایر مختلف با هم مساحت مشترک داشته باشند ولی در یک مجمع‌الجزایر هیچ دو مستطیلی با هم مساحت مشترک ندارند. $$1 \le t \le 5$$ $$1 \le n \le 200\ 000$$ $$|x_1, x_2, y_1, y_2| \le 10^9$$ $$x_1 < x_2$$ $$y_1 < y_2$$ # خروجی در خروجی $t$ عدد چاپ کنید که پاسخ مسئله برای هر مجمع‌الجزایر است. # مثال ## ورودی نمونه ``` 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 ``` ## خروجی نمونه ``` 1 5 6 ```

پل‌کشی

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

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

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

توضیح تصویر

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

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

توضیح تصویر

ورودی🔗

در اولین سطر ورودی یک عدد $t$ آمده است که نمایانگر تعداد مجمع‌الجزایرهای شکرستان است. سپس $t$ توضیح مجمع‌الجزایر آمده است. در هر یک از این توضیحات، ابتدا یک عدد $n$ آمده‌است که برابر تعداد جزیره‌های این مجمع‌الجزایر است. سپس در هریک از $n$ سطر بعدی، ۴ عدد $x_1$ ، $y_1$ ، $x_2$ و $y_2$ آمده‌است که مختصات ۴ گوشه‌ی مستطیل متناظر جزیره را نشان می‌دهند.

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

$1 \le t \le 5$ $1 \le n \le 200\ 000$ $|x_1, x_2, y_1, y_2| \le 10^9$ $x_1 < x_2$ $y_1 < y_2$

خروجی🔗

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

مثال🔗

ورودی نمونه🔗

خروجی نمونه🔗

1
5
6

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- میلاد و پارسا که از رسیدن به مرحله‌ی نهایی کدکاپ ۳ جا ماندند، تصمیم به ترک دنیای کدزنی گرفتند و می‌خواهند تا آخر عمر با هم بازی کنند. میلاد از بازی‌هایی که شانس در آن‌ها دخیل است خسته‌ شده‌است. دفعه آخری که میلاد و پارسا تخته نرد بازی کردند، پارسا مجموع تاس ۲۳۰ داشت و میلاد مجموع تاس ۱۵۰. میلاد به این باور رسیده‌است که نمی‌تواند در یک بازی که شانس در آن دخیل است پارسا را شکست دهد زیرا پارسا یک آدم خرشانس است. میلاد می‌داند تنها زمینه‌ای که او از پارسا بهتر است، زبان $C++$ است، به همین دلیل پارسا را مجبور می‌کند که با او $pair$ بازی کند. بازی $pair$ به این صورت است که ابتدا میلاد تعدادی کلمه $pair$ یا $int$ پشت هم می‌نویسد که می‌توان بین آن‌ها طوری علامت گذاشت که $pair$ ای قابل قبول برای $C++$ شود. (یعنی علامت های `,` و ‍‍`<` و ‍`>` که در میان این کلمات است را نمی‌گذارد.) پس از آن بین کلمات $pair$ و $int$، به تعداد $k$ کلمه، $pair$ یا $int$ دیگر اضافه می‌کند. حال میلاد با گفتن عدد $k$ به پارسا از او می‌خواهد که تعداد راه‌هایی که او می‌تواند $k$ کلمه حذف کند به طوری که کلمات باقی‌مانده یک تعریف متغیر قابل قبول برای $C++$ باشد را به او بگوید. از آنجایی که ممکن است این عدد خیلی بزرگ باشد پارسا باید باقیمانده آن به $10^9 + 7$ را به میلاد بگوید. از‌ آنجایی که پارسا سواد کافی در $C++$ ندارد از شما خواسته تا جواب میلاد را بدهید. یک $pair$ قابل قبول یک جفت به صورت $$ pair < T_1 , T_2 > $$ است که در آن $T_1$ و $T_2$یا $int$ است یا یک $pair$ قابل قبول. با تعریف فوق مثال‌های زیر تعریف متغیر‌هایی قابل قبول می‌باشد: ``` pair < int , int > pair < pair < int , int > , pair < int , int > > pair < int , pair < pair < int , int > , int > > ``` و مثال‌های زیر تعریف متغیرهایی غیر قابل قبول: ``` pair < int , int , int > pair < pair < int , int > > pair < int , pair > ``` دقت کنید که حالتی وجود دارد که می‌توان طوری $k$ کلمه را حذف کرد به طوری که کلمات باقی‌مانده قابل قبول باشد. # ورودی در خط اول ابتدا عدد $n$ که تعداد کلمات رشته پس از تغییر است و سپس عدد $k$ به شما داده می‌شود. در خط بعدی $n$ کلمه به شما داده می‌شود که هر کدام از کلمات یا `pair` است یا `int`. $$ 4 \le k + 3 \le n \le 100\ 000 $$ $$ 1 \le k \le 10$$ # خروجی باقیمانده تعداد راه‌های ممکن به $10^9 + 7$ را در یک خط چاپ کنید. # مثال ## ورودی نمونه ``` 12 1 pair int pair pair int int pair pair int int int int ``` ## خروجی نمونه ``` 7 ```

زوج ما

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

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

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

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

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

پس از آن بین کلمات $pair$ و $int$ ، به تعداد $k$ کلمه، $pair$ یا $int$ دیگر اضافه می‌کند.

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

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

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

یک $pair$ قابل قبول یک جفت به صورت $pair < T_1 , T_2 >$ است که در آن $T_1$ و $T_2$ یا $int$ است یا یک $pair$ قابل قبول.

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

pair < int , int >
pair < pair < int , int > , pair < int , int > >
pair < int , pair < pair < int , int > , int > >

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

pair < int , int , int >
pair < pair < int , int > >
pair < int , pair >

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

ورودی🔗

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

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

$4 \le k + 3 \le n \le 100\ 000$ $1 \le k \le 10$

خروجی🔗

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

مثال🔗

ورودی نمونه🔗

12 1
pair int pair pair int int pair pair int int int int

خروجی نمونه🔗

+ محدودیت زمان: ۶ ثانیه + محدودیت حافظه: ۵۱۲ مگابایت ---------- میلاد و پارسا که از رسیدن به مرحله‌ی نهایی کدکاپ ۳ جا ماندند، تصمیم گرفتند تا بالاخره بفهمند چه شد که در کدکاپ نتیجه نگرفتند. پس از بحث‌ها و مشاجرات فراوان، تصمیم گرفتند تا برای دادرسی به سراغ شخص ثالث بروند. شخص ثالث عقیده دارد نتیجه نگرفتن تقصیر کسی است که در بازی نیم ضعیف‌تر باشد، بازی نیم، بازی است که با $n$ کیسه تیله انجام می‌شود. همانطور که می‌دانید برنده شدن در بازی نیم بستگی به $xor$ تعداد تیله‌های همه کیسه‌ها با هم دارد. در ابتدا $n$ کیسه خالی وجود دارد. میلاد می‌خواهد طوری کیسه‌ها را پر کند که حتما برنده بازی باشد. میلاد در هر مرحله می‌تواند دو عدد $l$ و $r$ انتخاب کند به طوری که $ 1 \le l \le r \le n$ و به تمام کیسه‌های بین $l$ و $r$ (شامل ابتدا و انتهای‌ بازه) یک تیله اضافه کند. میلاد کار خودش را بلد است و تنها کمکی که از شما می‌خواهد این است که پس از هر مرحله که میلاد انجام می‌دهد، $xor$ تعداد تیله‌های تمام کیسه‌ها را به او بگویید. # ورودی در خط اول ابتدا $n$ که تعداد کیسه‌هاست و سپس $q$ که تعداد مراحل پر کردن است به شما داده می‌شود. سپس در $q$ خط بعدی، در هر خط دو عدد $l_i$ و $r_i$ داده می‌شود که ابتدا و انتهای بازه‌ای است که در مرحله $i$-ام توسط میلاد تغییر می‌کند. $$ 1 \le n , q \le 100\ 000$$ $$ 1 \le l_i \le r_i \le n$$ # خروجی در $q$ خط، در خط $i$ ام، $xor$ تعداد تیله‌های تمام کیسه‌ها پس از انجام مرحله $i$ ام را چاپ کنید. # مثال ## ورودی نمونه ``` 5 4 1 5 3 5 5 5 1 5 ``` ## خروجی نمونه ``` 1 2 3 4 ```

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

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

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

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

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

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

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

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

ورودی🔗

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

سپس در $q$ خط بعدی، در هر خط دو عدد $l_i$ و $r_i$ داده می‌شود که ابتدا و انتهای بازه‌ای است که در مرحله $i$ -ام توسط میلاد تغییر می‌کند.

$1 \le n , q \le 100\ 000$ $1 \le l_i \le r_i \le n$

خروجی🔗

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

مثال🔗

ورودی نمونه🔗

خروجی نمونه🔗