+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- حسنی و $n - 1$ نفر از دوستانش دور یک دایره نشستند و شروع به انجام بازی اتل‌متل $k$توله می‌کنند. شیوه انجام بازی این جوری هست که حسنی به عنوان نفر اول می‌گوید "سلام!". بعد از آن در هر مرحله نفر $k$ تا جلوتر نفر قبلی می‌گوید "سلام!". این روال ادامه دارد تا دوباره نوبت حسنی شود و آن موقع بازی تموم می‌شود. حالا حسنی می‌خواهد بداند که این بازی چند مرحله طول می‌کشد و از آن‌جا که خیلی سرگرم بازی شده، از شما می‌خواهد تا جواب را به او بگویید. # ورودی در خط اول ورودی $n$ و $k$ آمده‌ است. $$1 \le k \le n \le 1\ 000$$ # خروجی در تنها خط خروجی تعداد مراحلی را که طول می‌کشد تا دوباره نوبت حسنی شود را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 5 2 ``` ## خروجی نمونه ۱ ``` 5 ``` اگر افراد دور دایره را از $1$ تا $5$ شماره‌گذاری کنیم به طوری که حسنی شماره یک را بگیرد طبق چنین روندی دوباره نوبت حسنی می‌شود: $$(1, 3, 5, 2, 4, 1)$$ ## ورودی نمونه ۲ ``` 6 2 ``` ## خروجی نمونه ۲ ``` 3 ``` در این حالت افرادی که سلام می‌کنند چنین شماره‌هایی را دارند: $$ (1, 3, 5, 1) $$ ## ورودی نمونه ۳ ``` 6 6 ``` ## خروجی نمونه ۳ ``` 1 ``` در این حالت نفر $k$تا بعدی حسنی خود حسنی است! ---------------------------------- <details class="blue"> <summary> راهنمایی ۱ </summary> سعی کنید روند بازی را به صورت ساده، جوری که بتوانید کد آن را بزنید، در بیاورید. برای مثال در سوال آمده است "تا زمانی که نوبت دوباره به حسنی نرسیده‌است، بازی ادامه دارد." که این همان *حلقه* است. (با [این لینک](https://fullkade.com/1397/08/programming-loop/) می‌توانید بیشتر با حلقه آشنا شوید.) </details> <details class="blue"> <summary> راهنمایی ۲ </summary> فرض کنید دو متغیر *cnt* و *cur* دارید که در هر مرحله *cnt* برابر تعداد مراحل تا الان است و *cur* برابر اینکه اخرین نفری که گفت "سلام" چه کسی است. برای مثال‌ها مراحل را اجرا کنید و مقدار *cur* و *cnt* را در هر مرحله یادداشت کنید. فرض کنید که افراد را از ۰ تا $n-1$ شماره‌گذاری کردیم و حسنی شماره ۰ است. مثلا برای ورودی نمونه ۲ که $n = 6$ و $k=2$ است به این شکل مقدار‌های متغیر بعد از هر مرحله تغییر می‌کند. | cnt | cur | |:---:|:---:| | ۱ | ۰ | | ۲ | ۲ | | ۳ | ۴ | و بعد از مرحله ۳ دوباره حسنی را می‌بینیم و بازی تمام می‌شود. </details> <details class="blue"> <summary> راهنمایی ۳ </summary> قسمت اصلی الگوریتم، یعنی شبیه‌سازی کردن بازی، از یک *حلقه* تشکیل شده است و دو متغیر *cnt* و *cur*که حلقه تا زمانی که بازی تمام نشده است، اجرا می‌شود. شبه کد الگوریتم: ``` assign 0 to *cnt* assign 0 to *cur* while true : increase value of *cnt* by one update value of *cur* if *cur* = 0: break ``` منظور از دستور `break` این است که از حلقه `while` بیرون بیاید و منظور از `while true` یعنی تا زمانی که به دستور `break` نرسیده است، حلقه را تکرار کند و منظور از `assign 0 to *cnt*` این است که مقدار متغیر `cnt` را برابر صفر بکن. </details> <details class="blue"> <summary> راه حل </summary> می‌توانید مشاهده کنید که بعد هر مرحله *cnt* یک واحد زیاد می‌شود و *cur* باید برابر *k*-امین نفر جلو باشد. در صورتی که افراد را به ترتیب از 0 تا $n-1$ شماره گذاری کنید و حسنی 0 باشد. بعد هر مرحله *cur* به علاوه *k* می‌شود و سپس به پیمانه *n* باقی مانده گرفته می‌شود. ``` assign 0 to *cnt* assign 0 to *cur* while true : increase value of *cnt* by one assign (*cur* + *k*) to *cur* assign (*cur* mod *n*) to *cur* if *cur* = 0: break ``` </details>

دایره عجیب

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

حسنی و $n - 1$ نفر از دوستانش دور یک دایره نشستند و شروع به انجام بازی اتل‌متل $k$ توله می‌کنند. شیوه انجام بازی این جوری هست که حسنی به عنوان نفر اول می‌گوید "سلام!". بعد از آن در هر مرحله نفر $k$ تا جلوتر نفر قبلی می‌گوید "سلام!". این روال ادامه دارد تا دوباره نوبت حسنی شود و آن موقع بازی تموم می‌شود.

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

ورودی🔗

در خط اول ورودی $n$ و $k$ آمده‌ است.

$1 \le k \le n \le 1\ 000$

خروجی🔗

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

مثال🔗

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

5 2

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

اگر افراد دور دایره را از $1$ تا $5$ شماره‌گذاری کنیم به طوری که حسنی شماره یک را بگیرد طبق چنین روندی دوباره نوبت حسنی می‌شود:

$(1, 3, 5, 2, 4, 1)$

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

6 2

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

در این حالت افرادی که سلام می‌کنند چنین شماره‌هایی را دارند:

$(1, 3, 5, 1)$

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

6 6

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

در این حالت نفر $k$ تا بعدی حسنی خود حسنی است!

راهنمایی ۱

سعی کنید روند بازی را به صورت ساده، جوری که بتوانید کد آن را بزنید، در بیاورید.
برای مثال در سوال آمده است "تا زمانی که نوبت دوباره به حسنی نرسیده‌است، بازی ادامه دارد." که این همان حلقه است. (با این لینک می‌توانید بیشتر با حلقه آشنا شوید.)

راهنمایی ۲

فرض کنید دو متغیر cnt و cur دارید که در هر مرحله cnt برابر تعداد مراحل تا الان است و cur برابر اینکه اخرین نفری که گفت "سلام" چه کسی است.
برای مثال‌ها مراحل را اجرا کنید و مقدار cur و cnt را در هر مرحله یادداشت کنید.
فرض کنید که افراد را از ۰ تا $n-1$ شماره‌گذاری کردیم و حسنی شماره ۰ است.
مثلا برای ورودی نمونه ۲ که $n = 6$ و $k=2$ است به این شکل مقدار‌های متغیر بعد از هر مرحله تغییر می‌کند.

cnt	cur
۱	۰
۲	۲
۳	۴

و بعد از مرحله ۳ دوباره حسنی را می‌بینیم و بازی تمام می‌شود.

راهنمایی ۳

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

شبه کد الگوریتم:

assign 0 to *cnt*
assign 0 to *cur*
while true :
    increase value of *cnt* by one
    update value of *cur*
    if *cur* = 0:
        break

منظور از دستور break این است که از حلقه while بیرون بیاید و منظور از while true یعنی تا زمانی که به دستور break نرسیده است، حلقه را تکرار کند و منظور از assign 0 to *cnt* این است که مقدار متغیر cnt را برابر صفر بکن.

راه حل

می‌توانید مشاهده کنید که بعد هر مرحله cnt یک واحد زیاد می‌شود و cur باید برابر k-امین نفر جلو باشد. در صورتی که افراد را به ترتیب از 0 تا $n-1$ شماره گذاری کنید و حسنی 0 باشد. بعد هر مرحله cur به علاوه k می‌شود و سپس به پیمانه n باقی مانده گرفته می‌شود.

assign 0 to *cnt*
assign 0 to *cur*
while true :
    increase value of *cnt* by one
    assign (*cur* + *k*) to *cur*
    assign (*cur* mod *n*) to *cur*
    if *cur* = 0:
        break

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- **می‌توانید شعر زیر را نخوانید و تاثیری در فهم سوال ندارد.** توی ده [شلمرود](https://quera.ir/problemset/technology/33127/%D8%B3%D8%A4%D8%A7%D9%84-%D9%81%D8%B1%D8%A7%D9%86%D8%AA-%D8%A7%D9%86%D8%AF-%D8%B4%D9%84%D9%85%D8%B1%D9%88%D8%AF) حسنی تک و تنها بود حسنی نگو بلا بگو تنبل تنبل‌ها بگو موی بلند، روی سیاه ناخن دراز، واه و واه و واه نه فلفی، نه قلقلی نه مرغ زرد کاکلی هیچکس باهاش رفیق نبود تنها روی سه پایه، نشسته بود تو سایه باباش می‌گفت: حسنی میای بریم حموم؟ «نه نمیام، نه نمیام» سرت رو می‌خوای اصلاح کنی؟ «نه نمی‌خوام، نه نمی‌خوام» کره الاغ کدخدا یورتمه می‌رفت تو کوچه‌ها «الاغه چرا یورتمه میری؟» «دارم می‌رم بار ببرم دیرم شده عجله دارم» «الاغ خوب و نازنین سر در هوا سم بر زمین یالت بلند و پرمو دمت مثال جارو یک کمی به من سواری میدی؟» «نه که نمی‌دم» «چرا نمی‌دی؟» «واسه این که من تمیزم پیش همه عزیزم اما تو چی؟ موی بلند، روی سیاه ناخن دراز، واه و واه و واه!» غازه پرید تو استخر «تو اردکی یا غازی؟» «من غاز خوش زبانم» «میای بریم به بازی؟» «نه جانم» «چرا نمیای؟» «واسه این که من صبح تا غروب میون آب، کنار جو مشغول کار و شستشو اما تو چی؟ موی بلند، روی سیاه ناخن دراز، واه و واه و واه» در وا شد و یه جوجه دوید و اومد تو کوچه جیک‌جیک‌کنان گردش‌زنان اومد و اومد پیش حسنی «جوجه کوچولو کوچول موچولو میای با من بازی کنی؟» مادرش اومد «قدقدقدا برو خونتون تو رو به خدا جوجه‌ی ریزه میزه ببین چقد تمیزه؟ اما تو چی؟ موی بلند، روی سیاه ناخن دراز، واه و واه و واه» حسنی با چشم گریون پا شد و اومد تو میدون «آی فلفلی، آی قلقلی میاین با من بازی کنین؟» «نه که نمیایم» «چرا نمیاین؟» فلفلی گفت: من و داداشم و بابام و عموم هفته‌ای دو بار میریم حموم اما تو چی؟ قلقلی گفت: نگاش کنین موی بلند، روی سیاه ناخن دراز، واه و واه و واه حسنی دویید پیش باباش «حسنی میای بریم حموم؟» «میام، میام» «سرتو میخوای اصلاح کنی؟» «میخوام، میخوام» حسنی نگو یه دسته گل تر و تمیز و تپل مپل الاغ و خروس و جوجه غاز و ببعی با فلفلی با قلقلی با مرغ زرد کاکلی حلقه زدن دور حسن الاغه می‌گفت: اگر کاری نداری بریم الاغ سواری خروسه می‌گفت: قوقولی قوقو، قوقولی قوقو هر چی میخوای، فوری بگو مرغه می‌گفت: حسنی برو تو کوچه بازی بکن با جوجه غازه می‌گفت: حسنی بیا با همدیگه بریم شنا توی ده شلمرود حسنی دیگه تنها نبود! ---------- بعد از این که حسنی تمیز شد و با همه بازی کرد، همه دور هم جمع شدند و از بابای حسنی خواستند که ازشون عکس بگیره. ولی وقتی بابای حسنی اومد، فهمیدند که حداکثر $k$تاشون درون یه عکس جا می‌شوند. بابای حسنی گفت: «خب حالا عیبی نداره، $k$تا $k$تا بیایید ازتون عکس می‌گیرم.» مرغه گفت: «این‌طوری که نمی‌شه، من می‌خوام با جوجه‌هام توی یه عکس باشم.» الاغه گفت: «تازه من هم می‌خوام با خروسه توی یه عکس باشم. اگه این‌طوریه، من اصلا عکس نمی‌گیرم.» بابای حسنی یه ذره مِن‌و‌مِن کرد و گفت: «خب عیبی نداره. شما بیایید توی یه صف وایسید، بعد هم تا جایی که جا شدید می‌آیید توی عکس» بالاخره اهالی ده شلمرود تصمیم گرفتند که به $n$تا دسته تقسیم بشوند و توی دسته‌ی $i$ام $a_i$نفر بودند که می‌خواستند با هم عکس بگیرند. حالا بابای حسنی از شما می‌پرسد که حداقل باید چند تا عکس بگیرد تا همه در یک عکس افتاده باشند. در هر عکسی که بابای حسنی می‌گیرد یک بازه پشت سر هم از دسته‌ها می‌توانند حضور داشته باشند که جمع اعضای این بازه باید حداکثر $k$ باشد. در واقع شما یه آرایه‌ی $n$تایی دارید و باید بگید حداقل $m$ چقدر هست که بتوان آرایه‌ را به $m$ بازه تقسیم کرد که مجموع اعداد هر بازه حداکثر $k$ باشد. *توجه کنید که بازه به دنباله‌ای متوالی از اعضای یک آرایه گفته می‌شود.* # ورودی ورودی شامل دو خط است. در خط اول به ترتیب ابتدا $n$ تعداد گروه‌ها و سپس $k$ حداکثر ظرفیت یک عکس به شما داده می‌شود. در خط دوم $n$ عدد به شما داده می‌شود که عدد $i$ام آن‌ها، $a_i$ است. $$ 1 \le n, k \le 100\ 000$$ $$0 \le a_i \le k$$ # خروجی خروجی برنامه شامل یک عدد صحیح است، حداقل تعداد عکس‌هایی که پدر حسنی باید بگیرد. # مثال ## ورودی نمونه ۱ ``` 5 4 3 4 1 2 2 ``` ## خروجی نمونه ۱ ``` 4 ``` بازه‌ها به صورت $\{3\}, \{4\}, \{1, 2\}, \{2\}$ خواهند بود. یک جواب دیگر برای این مثال $\{3\}, \{4\}, \{1\}, \{2, 2\}$ است. ## ورودی نمونه ۲ ``` 5 8 3 4 1 2 2 ``` ## خروجی نمونه ۲ ``` 2 ``` --------------------------- <details class="blue"> <summary> راهنمایی ۱ </summary> اگر دسته اول و دوم نتوانند در یک عکس باشند، (یعنی $a_1+a_2 \gt k$) حتما دسته اول باید تنهایی عکس بگیرند و با دسته دیگری نمی‌توانند در یک عکس باشند. </details> <details class="blue"> <summary> راهنمایی ۲ </summary> در چه صورت جواب بهینه‌ای وجود دارد که دسته اول و دوم هر دو در یک عکس باشند؟ </details> <details class="blue"> <summary> راهنمایی ۳ </summary> ثابت کنید اگر دسته دوم می‌توانست در عکس با دسته اول باشد (یعنی $a_1+a_2 \le k$) جواب بهینه‌ای وجود دارد که دسته اول و دوم هر دو در یک عکس باشند. </details> <details class="blue"> <summary> راهنمایی ۴ </summary> اگر دسته اول و دوم با هم نمی‌توانستند در یک عکس باشند، یک عکس تکی از دسته اول بگیرید. اگر دسته اول و دوم می‌توانستند با هم باشند، این دو دسته را یک دسته جدید با اندازه $a_1+a_2$ در نظر بگیرید و مسئله را دوباره حل کنید. </details> <details class="blue"> <summary> راه حل </summary> دسته اول را در عکس اول قرار بدهید. سپس دسته دوم را اگر می‌شد، در عکس قرار بدهید، سپس دسته سوم و به همین روال ادامه دهید تا زمانی که دیگر نمی‌توانید دسته جدیدی قرار بدهید. فرض کنید *t* دسته اول را در عکس اول قرار دادید و نمی‌توانید دسته بعدی را در عکس قرار بدهید. حالا *t* دسته اول حذف شدند و با همین روش بقیه افراد را در عکس قرار بدهید. در واقع از اولین دسته شروع کنید و تاجایی که می‌توانید دسته‌ها را در داخل عکس قرار بدهید. اثبات درستی به صورت خلاصه این است که در هر مرحله اگر دسته‌ای رو می توانید قرار بدهید. دلیلی وجود ندارد که قرار ندهید و عکس بگیرید چون این دسته باید در عکس بعدی قرار بگیرد و می‌توانست در عکس اول باشد و در عکس دوم نباشد. درستی الگوریتم را با استقرا نیز می‌توانید اثبات کنید چون دسته اول و دوم را در صورت امکان می‌توانید یک دسته بکنید و تعداد دسته‌ها کم می‌شود. </details>

حسنی نگو عکاس بگو

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

می‌توانید شعر زیر را نخوانید و تاثیری در فهم سوال ندارد.

توی ده شلمرود

حسنی تک و تنها بود

حسنی نگو بلا بگو

تنبل تنبل‌ها بگو

موی بلند، روی سیاه

ناخن دراز، واه و واه و واه

نه فلفی، نه قلقلی

نه مرغ زرد کاکلی

هیچکس باهاش رفیق نبود

تنها روی سه پایه، نشسته بود تو سایه

باباش می‌گفت: حسنی میای بریم حموم؟

«نه نمیام، نه نمیام»

سرت رو می‌خوای اصلاح کنی؟

«نه نمی‌خوام، نه نمی‌خوام»

کره الاغ کدخدا

یورتمه می‌رفت تو کوچه‌ها

«الاغه چرا یورتمه میری؟»

«دارم می‌رم بار ببرم

دیرم شده عجله دارم»

«الاغ خوب و نازنین

سر در هوا سم بر زمین

یالت بلند و پرمو

دمت مثال جارو

یک کمی به من سواری میدی؟»

«نه که نمی‌دم»

«چرا نمی‌دی؟»

«واسه این که من تمیزم

پیش همه عزیزم اما تو چی؟

موی بلند، روی سیاه

ناخن دراز، واه و واه و واه!»

غازه پرید تو استخر

«تو اردکی یا غازی؟»

«من غاز خوش زبانم»

«میای بریم به بازی؟»

«نه جانم»

«چرا نمیای؟»

«واسه این که من

صبح تا غروب

میون آب، کنار جو

مشغول کار و شستشو

اما تو چی؟

موی بلند، روی سیاه

ناخن دراز، واه و واه و واه»

در وا شد و یه جوجه

دوید و اومد تو کوچه

جیک‌جیک‌کنان

گردش‌زنان

اومد و اومد پیش حسنی

«جوجه کوچولو

کوچول موچولو

میای با من بازی کنی؟»

مادرش اومد «قدقدقدا

برو خونتون تو رو به خدا

جوجه‌ی ریزه میزه

ببین چقد تمیزه؟

اما تو چی؟

موی بلند، روی سیاه

ناخن دراز، واه و واه و واه»

حسنی با چشم گریون

پا شد و اومد تو میدون

«آی فلفلی، آی قلقلی

میاین با من بازی کنین؟»

«نه که نمیایم»

«چرا نمیاین؟»

فلفلی گفت:

من و داداشم و بابام و عموم

هفته‌ای دو بار میریم حموم

اما تو چی؟

قلقلی گفت: نگاش کنین

موی بلند، روی سیاه

ناخن دراز، واه و واه و واه

حسنی دویید پیش باباش

«حسنی میای بریم حموم؟»

«میام، میام»

«سرتو میخوای اصلاح کنی؟»

«میخوام، میخوام»

حسنی نگو یه دسته گل

تر و تمیز و تپل مپل

الاغ و خروس و جوجه غاز و ببعی

با فلفلی با قلقلی با مرغ زرد کاکلی

حلقه زدن دور حسن

الاغه می‌گفت:

اگر کاری نداری

بریم الاغ سواری

خروسه می‌گفت:

قوقولی قوقو، قوقولی قوقو

هر چی میخوای، فوری بگو

مرغه می‌گفت:

حسنی برو تو کوچه

بازی بکن با جوجه

غازه می‌گفت:

حسنی بیا با همدیگه بریم شنا

توی ده شلمرود

حسنی دیگه تنها نبود!

بعد از این که حسنی تمیز شد و با همه بازی کرد، همه دور هم جمع شدند و از بابای حسنی خواستند که ازشون عکس بگیره. ولی وقتی بابای حسنی اومد، فهمیدند که حداکثر $k$ تاشون درون یه عکس جا می‌شوند. بابای حسنی گفت: «خب حالا عیبی نداره، $k$ تا $k$ تا بیایید ازتون عکس می‌گیرم.»

مرغه گفت: «این‌طوری که نمی‌شه، من می‌خوام با جوجه‌هام توی یه عکس باشم.»

الاغه گفت: «تازه من هم می‌خوام با خروسه توی یه عکس باشم. اگه این‌طوریه، من اصلا عکس نمی‌گیرم.»

بابای حسنی یه ذره مِن‌و‌مِن کرد و گفت: «خب عیبی نداره. شما بیایید توی یه صف وایسید، بعد هم تا جایی که جا شدید می‌آیید توی عکس»

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

در هر عکسی که بابای حسنی می‌گیرد یک بازه پشت سر هم از دسته‌ها می‌توانند حضور داشته باشند که جمع اعضای این بازه باید حداکثر $k$ باشد.

در واقع شما یه آرایه‌ی $n$ تایی دارید و باید بگید حداقل $m$ چقدر هست که بتوان آرایه‌ را به $m$ بازه تقسیم کرد که مجموع اعداد هر بازه حداکثر $k$ باشد.

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

ورودی🔗

ورودی شامل دو خط است. در خط اول به ترتیب ابتدا $n$ تعداد گروه‌ها و سپس $k$ حداکثر ظرفیت یک عکس به شما داده می‌شود.

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

$1 \le n, k \le 100\ 000$

$0 \le a_i \le k$

خروجی🔗

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

مثال🔗

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

5 4
3 4 1 2 2

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

بازه‌ها به صورت $\{3\}, \{4\}, \{1, 2\}, \{2\}$ خواهند بود. یک جواب دیگر برای این مثال $\{3\}, \{4\}, \{1\}, \{2, 2\}$ است.

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

5 8
3 4 1 2 2

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

راهنمایی ۱

اگر دسته اول و دوم نتوانند در یک عکس باشند، (یعنی $a_1+a_2 \gt k$ ) حتما دسته اول باید تنهایی عکس بگیرند و با دسته دیگری نمی‌توانند در یک عکس باشند.

راهنمایی ۲

در چه صورت جواب بهینه‌ای وجود دارد که دسته اول و دوم هر دو در یک عکس باشند؟

راهنمایی ۳

ثابت کنید اگر دسته دوم می‌توانست در عکس با دسته اول باشد (یعنی $a_1+a_2 \le k$ ) جواب بهینه‌ای وجود دارد که دسته اول و دوم هر دو در یک عکس باشند.

راهنمایی ۴

اگر دسته اول و دوم با هم نمی‌توانستند در یک عکس باشند، یک عکس تکی از دسته اول بگیرید.
اگر دسته اول و دوم می‌توانستند با هم باشند، این دو دسته را یک دسته جدید با اندازه $a_1+a_2$ در نظر بگیرید و مسئله را دوباره حل کنید.

راه حل

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

فرض کنید t دسته اول را در عکس اول قرار دادید و نمی‌توانید دسته بعدی را در عکس قرار بدهید. حالا t دسته اول حذف شدند و با همین روش بقیه افراد را در عکس قرار بدهید.

در واقع از اولین دسته شروع کنید و تاجایی که می‌توانید دسته‌ها را در داخل عکس قرار بدهید.

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

+ محدودیت زمان: ۳ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- حسنی برای این که در تابستان وقتش را تلف نکند به کسب و کار روی آورده و به تازگی بانکی به نام **کناب** تاسیس کرده است. از آن‌جایی که دوست دارد شما نیز عضو کناب باشید به شما یک پروژه داده و خواسته تا همراه‌بانکی بنویسید که درخواست‌های زیر را اجرا کند. ``` 1 ip:username ``` این درخواست یعنی کاربری با نام‌ کاربری *username* و آی‌پی *ip* به همراه‌بانک وصل شد و در صورتی که *username* معتبر نباشد باید عبارت ‍‍‍`invalid username` را چاپ کنید. **به یک نام‌ کاربری معتبر می‌گوییم اگر فقط از حروف کوچک و بزرگ انگلیسی و اعداد تشکیل شده باشد.** برای مثال `1aAB2` معتبر است ولی `ab*2` معتبر نیست. ``` 2 ip:username:money ``` این درخواست یعنی کاربری با آی‌پی *ip* به حسابی با نام‌ کاربری *username* به اندازه *money* پول ریخته‌ است. در واقع باید از حساب *ip* به اندازه *money* کم کنید و به حساب *username* اضافه کنید. ``` 3 ip ``` با داده شدن این درخواست مقدار پول داخل حساب فرد با آی‌پی *ip* را نمایش دهید. **(دقت کنید که پول هر فرد می‌تواند منفی هم بشود و هرکس در ابتدا ۰ واحد پول دارد)** # ورودی در اولین خط ورودی عدد $q$ که بیانگر تعداد درخواست‌ها است به شما داده می‌شود و در $q$ خط بعد، در هر خط یک در‌خواست داده می‌شود. در هر درخواست ابتدا *type* داده می‌شود که برابر یکی از اعداد ۱ یا ۲ یا ۳ است و اگر $type$ برابر با ۱ باشد در ادامه دو رشته *ip* و *username* به شما داده می‌شود که توسط کاراکتر `:` از هم جدا شده‌اند. اگر $type$ مساوی ۲ باشد سه رشته *ip* و *username* و *money* داده می‌شود که با `:` از هم جدا شده‌اند و اگر هم $type$ مساوی ۳ باشد رشته *ip* داده می‌شود. $$0 \le q,money \le 100\ 000$$ طول *username* و *ip* حداکثر ۱۵ است. تضمین می‌شود که: + یک کاربر دوبار به همراه بانک وصل نمی‌شود و آی‌پی و نام‌ کاربری هیچ دو فردی یکسان نیست. + در صورتی که نام کاربری معتبر نباشد تنها ممکن است کاراکترهای `_` یا `*` یا `#` یا `$` در آن به کار رفته باشد. + همه‌ی ورودی‌های نوع ۲ و ۳ معتبر هستند؛ یعنی کاربری با آی‌پی یا نام کاربری مشخص شده‌، وجود دارد. + همه *ip*ها به صورت ۴ عدد بین ۰ تا ۲۵۵ هستند که با نقطه از هم جدا شده‌اند. + حداکثر پولی که یک نفر می‌تواند داشته باشد $10^9$ است. # خروجی برای هر درخواست نوع ۱ در صورتی که *username* معتبر نیست باید عبارت `invalid username` را چاپ کنید و برای هر درخواست نوع ۳ باید مقدار پول حساب فرد خواسته شده را چاپ کنید. (پاسخ هر درخواست را در یک خط جدید چاپ کنید.) # مثال ## ورودی نمونه ``` 9 1 46.51.16.72:SmsS 1 192.168.10.13:#hacker$user 1 131.41.61.213:faeila 2 46.51.16.72:faeila:1000 3 46.51.16.72 3 131.41.61.213 2 131.41.61.213:SmsS:500 3 46.51.16.72 3 131.41.61.213 ``` ## خروجی نمونه ``` invalid username -1000 1000 -500 500 ``` توضیحات: - نام کاربری `#hacker$user` معتبر نیست برای همین باید `invalid username` خروجی بدهید. - از حساب `SmsS` هزار واحد پول کم می‌شود و به حساب `faeila` اضافه می‌شود و حالا `SmsS` منفی هزار و `faeila` هزار واحد پول دارد. - از حساب `faeila` پانصد واحد کم می‌شود و حالا پانصد واحد پول دارد و `SmsS` منفی پانصد. --------------------------------- <details class="blue"> <summary> راهنمایی ۱ </summary> برای پیاده‌سازی تمیز این سوال می‌توانید از [Regex](https://en.wikipedia.org/wiki/Regular_expression) یا [عبارت باقاعده](https://fa.wikipedia.org/wiki/%D8%B9%D8%A8%D8%A7%D8%B1%D8%AA_%D8%A8%D8%A7%D9%82%D8%A7%D8%B9%D8%AF%D9%87) و [Associative array](https://en.wikipedia.org/wiki/Associative_array) یا [آرایه انجمنی](https://fa.wikipedia.org/wiki/%D8%A2%D8%B1%D8%A7%DB%8C%D9%87_%D8%A7%D9%86%D8%AC%D9%85%D9%86%DB%8C) استفاده کنید. می‌توانید [این لینک](https://en.wikipedia.org/wiki/Comparison_of_programming_languages_%28associative_array%29#C++) را نیز برای پیدا کردن *Associative array* در زبان مورد نظرتان استفاده کنید. </details> <details class="blue"> <summary> راهنمایی ۲ </summary> سعید کنید *Associative array*‌ای بسازید که هر کاربر که اضافه شد، بتوان با استفاده از نام‌کاربری هر فرد، آی‌پی آن فرد را پیدا کرد. </details> <details class="blue"> <summary> راهنمایی ۳ </summary> حالا *Associative array* دیگری بسازید که با استفاده از آی‌پی هر فرد بتوان موجودی حساب آن فرد را پیدا کرد و یا تغییر داد. </details> <details class="blue"> <summary> راه حل </summary> حالا می‌توانید با استفاده از آی‌پی یا نام‌کاربری به موجودی حساب هر فرد دسترسی داشته باشید و درخواست‌ها را انجام بدهید. فرض کنید `sender_ip` برابر آی‌پی فردی است که پول واریز می‌کند و `receiver_user` برابر نام کاربری فردی است که پول دریافت می‌کند. می‌خواهیم دو مقدار `receiver_money` را که برابر پول حساب دریافت کننده است و همچنین `sender_user` و `sender_money` که نام کاربری و پول حساب واریز کننده است را پیدا کنیم. و دو *Associative array* به نام‌های `get_user` و `get_money` داریم که با اولی می‌توان با دادن آی‌پی فرد نام کاربری آن را به دست آورد و با استفاده از دومی، با دادن نام کاربری فرد، مقدار پول حسابش را به دست آورد. شبه کد الگوریتم برای اعمال کوئری‌های نوع اول: ``` ip = input ip address user = input username if user is valid : add {user, 0} to get_money add {ip, user} to get_user ``` شبه کد الگوریتم برای اعمال کوئری‌های نوع دوم: ``` sender_ip = sender ip address receiver_user = receiver username sender_user = get username from get_user reassign value of (money of sender_user) in get_money by specific value reassign value of (money of receiver_user) in get_money by specific value ``` </details>

هارمه کناب

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

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

1 ip:username

این درخواست یعنی کاربری با نام‌ کاربری username و آی‌پی ip به همراه‌بانک وصل شد و در صورتی که username معتبر نباشد باید عبارت ‍‍‍invalid username را چاپ کنید.
به یک نام‌ کاربری معتبر می‌گوییم اگر فقط از حروف کوچک و بزرگ انگلیسی و اعداد تشکیل شده باشد.
برای مثال 1aAB2 معتبر است ولی ab*2 معتبر نیست.

2 ip:username:money

این درخواست یعنی کاربری با آی‌پی ip به حسابی با نام‌ کاربری username به اندازه money پول ریخته‌ است. در واقع باید از حساب ip به اندازه money کم کنید و به حساب username اضافه کنید.

3 ip

با داده شدن این درخواست مقدار پول داخل حساب فرد با آی‌پی ip را نمایش دهید.

(دقت کنید که پول هر فرد می‌تواند منفی هم بشود و هرکس در ابتدا ۰ واحد پول دارد)

ورودی🔗

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

در هر درخواست ابتدا type داده می‌شود که برابر یکی از اعداد ۱ یا ۲ یا ۳ است و اگر $type$ برابر با ۱ باشد در ادامه دو رشته ip و username به شما داده می‌شود که توسط کاراکتر : از هم جدا شده‌اند. اگر $type$ مساوی ۲ باشد سه رشته ip و username و money داده می‌شود که با : از هم جدا شده‌اند و اگر هم $type$ مساوی ۳ باشد رشته ip داده می‌شود.

$0 \le q,money \le 100\ 000$

طول username و ip حداکثر ۱۵ است.

تضمین می‌شود که:

یک کاربر دوبار به همراه بانک وصل نمی‌شود و آی‌پی و نام‌ کاربری هیچ دو فردی یکسان نیست.
در صورتی که نام کاربری معتبر نباشد تنها ممکن است کاراکترهای _ یا * یا # یا $ در آن به کار رفته باشد.
همه‌ی ورودی‌های نوع ۲ و ۳ معتبر هستند؛ یعنی کاربری با آی‌پی یا نام کاربری مشخص شده‌، وجود دارد.
همه ipها به صورت ۴ عدد بین ۰ تا ۲۵۵ هستند که با نقطه از هم جدا شده‌اند.
حداکثر پولی که یک نفر می‌تواند داشته باشد $10^9$ است.

خروجی🔗

برای هر درخواست نوع ۱ در صورتی که username معتبر نیست باید عبارت invalid username را چاپ کنید و برای هر درخواست نوع ۳ باید مقدار پول حساب فرد خواسته شده را چاپ کنید. (پاسخ هر درخواست را در یک خط جدید چاپ کنید.)

مثال🔗

ورودی نمونه🔗

9
1 46.51.16.72:SmsS
1 192.168.10.13:#hacker$user
1 131.41.61.213:faeila
2 46.51.16.72:faeila:1000
3 46.51.16.72
3 131.41.61.213
2 131.41.61.213:SmsS:500
3 46.51.16.72
3 131.41.61.213

خروجی نمونه🔗

invalid username
-1000
1000
-500
500

توضیحات:

نام کاربری #hacker$user معتبر نیست برای همین باید invalid username خروجی بدهید.
از حساب SmsS هزار واحد پول کم می‌شود و به حساب faeila اضافه می‌شود و حالا SmsS منفی هزار و faeila هزار واحد پول دارد.
از حساب faeila پانصد واحد کم می‌شود و حالا پانصد واحد پول دارد و SmsS منفی پانصد.

راهنمایی ۱

برای پیاده‌سازی تمیز این سوال می‌توانید از Regex یا عبارت باقاعده و Associative array یا آرایه انجمنی استفاده کنید.
می‌توانید این لینک را نیز برای پیدا کردن Associative array در زبان مورد نظرتان استفاده کنید.

راهنمایی ۲

سعید کنید Associative array‌ای بسازید که هر کاربر که اضافه شد، بتوان با استفاده از نام‌کاربری هر فرد، آی‌پی آن فرد را پیدا کرد.

راهنمایی ۳

حالا Associative array دیگری بسازید که با استفاده از آی‌پی هر فرد بتوان موجودی حساب آن فرد را پیدا کرد و یا تغییر داد.

راه حل

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

فرض کنید sender_ip برابر آی‌پی فردی است که پول واریز می‌کند و receiver_user برابر نام کاربری فردی است که پول دریافت می‌کند. می‌خواهیم دو مقدار receiver_money را که برابر پول حساب دریافت کننده است و همچنین sender_user و sender_money که نام کاربری و پول حساب واریز کننده است را پیدا کنیم.

و دو Associative array به نام‌های get_user و get_money داریم که با اولی می‌توان با دادن آی‌پی فرد نام کاربری آن را به دست آورد و با استفاده از دومی، با دادن نام کاربری فرد، مقدار پول حسابش را به دست آورد.

شبه کد الگوریتم برای اعمال کوئری‌های نوع اول:

ip = input ip address
user = input username
if user is valid :
    add {user, 0} to get_money
    add {ip, user} to get_user

شبه کد الگوریتم برای اعمال کوئری‌های نوع دوم:

sender_ip = sender ip address
receiver_user = receiver username

sender_user = get username from get_user
reassign value of (money of sender_user) in get_money by specific value
reassign value of (money of receiver_user) in get_money by specific value

+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- در کشور(!) شلمرود، $n$ شهر وجود دارد که با $m$ جاده دوطرفه به هم وصل شده‌اند.‌ طول جاده $i$ام هم $w_i$ کیلومتر است. حسنی یک الاغ هم دارد که با استفاده از آن می‌تواند با سرعت یک کیلومتر بر ساعت جاده‌ها را طی کند. حسنی جدیدا یک قابلیت جدید پیدا کرده که با استفاده از آن می‌تواند طول همه جاده‌ها را یک کیلومتر کم کند. حسنی فقط می‌تواند این قابلیت را وقتی درون یک شهر هست استفاده کند و $t_i$ ساعت طول می‌کشد که از این قابلیت در راس $i$-ام استفاده کند. هم‌چنین اگر با استفاده از این قابلیت طول یک جاده صفر بشود آن جاده از شلمرود حذف می‌شود و نمی‌توان از آن عبور کرد. حالا حسنی از شما می‌پرسد که کم‌ترین زمانی که طول می‌کشد تا از شهر شماره $1$ به شهر شماره $n$ برسه چه قدر هست و از آن‌جا که شما هم حسنی را خیلی دوست دارید باید جوابش را بدهید. # ورودی در خط اول ورودی $n$ و $m$ آمده‌ است. سپس در خط بعدی $n$ عدد آمده که عدد $i$-ام $t_i$ را نشان می‌دهد. در هر یک از $m$ خط بعدی هم سه عدد آمده که دو سر جاده و وزن آن جاده را مشخص می‌کند. $$1 \le n, m, t_i, w_i \le 1\ 000$$ # خروجی در تنها خط خروجی کمترین زمان برای رسیدن از شهر شماره $1$ به شهر شماره $n$ را چاپ کنید. در صورتی هم که مسیری از شهر $1$ به شهر $n$ وجود نداشته باشد `-1` چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 3 2 1 1000 1000 1 2 100 2 3 100 ``` ## خروجی نمونه ۱ ``` 101 ``` در این نمونه وقتی که در شهر یک هستیم $99$ بار از قابلیت استفاده می‌کنیم و بعد از آن طول هر دو جاده یک می‌شود. بعد از آن می‌توان بعد از دو ساعت به شهر شماره سه رسید. ## ورودی نمونه ۲ ``` 3 2 3 1 1000 1 2 100 2 3 100 ``` ## خروجی نمونه ۲ ``` 200 ``` در این مثال بدون استفاده از قابلیت می‌توان بعد از $200$ ساعت به شهر $3$ رسید. ## ورودی نمونه ۳ ``` 4 2 1 2 3 4 1 2 5 2 3 10 ``` ## خروجی نمونه ۳ ``` -1 ``` در این نمونه مسیری از شهر $1$ به شهر $4$ وجود ندارد. --------------- <details class="blue"> <summary> راهنمایی ۱ </summary> برای حل این سوال باید الگوریتم [Dijkstra](https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm) را بلد باشید. </details> <details class="blue"> <summary> راهنمایی ۲ </summary> به مجموعه‌ای از شهر‌ها و جاده‌ها گراف می‌گوییم و منظور از راس همان شهر و از یال همان جاده است. اگر فرض کنید گراف اولیه برابر $G$ باشد. گراف $G_i$ را به این صورت تعریف کنید که راس‌ها و یال‌های آن متنظار با راس‌ها و یال‌های $G$ است ولی طول هر یال آن منهای *i* شده و اگر منفی می‌شد، حذف شده است. می‌توانید مشاهده کنید که $G$ همان $G_0$ است. </details> <details class="blue"> <summary> راهنمایی ۳ </summary> با استفاده از $G_i$‌ها گرافی بسازید که مسئله شما صرفا به مسئله کوتاه ترین مسیر تبدیل شود و پیچیدگی دیگری نداشته باشد. دقت کنید که اگر روی راس *v* در گراف $G_i$‌ باشید می‌توانید در مدت زمان $t_v$ به راس متناظر *v* در گراف $G_{i+1}$ بروید. </details> <details class="blue"> <summary> راهنمایی ۴ </summary> می‌توانید مشاهده کنید که $G_{1001}$ هیچ یالی ندارد چون $w_i \le1\ 000$ </details> <details class="blue"> <summary> راه حل </summary> می‌خواهیم گراف جدیدی بسازیم که از اتصال $G_i$های مخلتف است. به این صورت این گراف را می‌سازیم که برای هر i ($0 \le i \lt 1000$) و هر راس مثل *v* در $G_i$، آن را توسط یک یال یک طرفه با وزن $t_v$ به شهر متناظرش در $G_{i+1}$ وصل می‌کنیم. می‌توانید مشاهده کنید که جواب معادل کوتاه ترین مسیر از شهر 1 در$G_0$ به یکی از شهر‌های *n* در یکی از $G_i$ها است که طول مسیر کمینه شود از طرفی $G_{1001}$ به بعد چون هیچ یالی ندارند نیازی بهشون نداریم پس تعداد راس‌های ما برابر $1001 \times n$ و تعداد یال‌ها حداکثر $1001 \times m$ است که الگوریتم *Dijkstra* می‌تواند جواب مسئله را پیدا کند. </details>

مسیر عجیب

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

در کشور(!) شلمرود، $n$ شهر وجود دارد که با $m$ جاده دوطرفه به هم وصل شده‌اند.‌ طول جاده $i$ ام هم $w_i$ کیلومتر است. حسنی یک الاغ هم دارد که با استفاده از آن می‌تواند با سرعت یک کیلومتر بر ساعت جاده‌ها را طی کند.

حسنی جدیدا یک قابلیت جدید پیدا کرده که با استفاده از آن می‌تواند طول همه جاده‌ها را یک کیلومتر کم کند. حسنی فقط می‌تواند این قابلیت را وقتی درون یک شهر هست استفاده کند و $t_i$ ساعت طول می‌کشد که از این قابلیت در راس $i$ -ام استفاده کند. هم‌چنین اگر با استفاده از این قابلیت طول یک جاده صفر بشود آن جاده از شلمرود حذف می‌شود و نمی‌توان از آن عبور کرد.

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

ورودی🔗

در خط اول ورودی $n$ و $m$ آمده‌ است. سپس در خط بعدی $n$ عدد آمده که عدد $i$ -ام $t_i$ را نشان می‌دهد. در هر یک از $m$ خط بعدی هم سه عدد آمده که دو سر جاده و وزن آن جاده را مشخص می‌کند.

$1 \le n, m, t_i, w_i \le 1\ 000$

خروجی🔗

در تنها خط خروجی کمترین زمان برای رسیدن از شهر شماره $1$ به شهر شماره $n$ را چاپ کنید. در صورتی هم که مسیری از شهر $1$ به شهر $n$ وجود نداشته باشد -1 چاپ کنید.

مثال🔗

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

3 2
1 1000 1000
1 2 100
2 3 100

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

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

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

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

در این مثال بدون استفاده از قابلیت می‌توان بعد از $200$ ساعت به شهر $3$ رسید.

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

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

-1

در این نمونه مسیری از شهر $1$ به شهر $4$ وجود ندارد.

راهنمایی ۱

برای حل این سوال باید الگوریتم Dijkstra را بلد باشید.

راهنمایی ۲

به مجموعه‌ای از شهر‌ها و جاده‌ها گراف می‌گوییم و منظور از راس همان شهر و از یال همان جاده است.

اگر فرض کنید گراف اولیه برابر $G$ باشد. گراف $G_i$ را به این صورت تعریف کنید که راس‌ها و یال‌های آن متنظار با راس‌ها و یال‌های $G$ است ولی طول هر یال آن منهای i شده و اگر منفی می‌شد، حذف شده است.

می‌توانید مشاهده کنید که $G$ همان $G_0$ است.

راهنمایی ۳

با استفاده از $G_i$ ‌ها گرافی بسازید که مسئله شما صرفا به مسئله کوتاه ترین مسیر تبدیل شود و پیچیدگی دیگری نداشته باشد.

دقت کنید که اگر روی راس v در گراف $G_i$ ‌ باشید می‌توانید در مدت زمان $t_v$ به راس متناظر v در گراف $G_{i+1}$ بروید.

راهنمایی ۴

می‌توانید مشاهده کنید که $G_{1001}$ هیچ یالی ندارد چون $w_i \le1\ 000$

راه حل

می‌خواهیم گراف جدیدی بسازیم که از اتصال $G_i$ های مخلتف است.

به این صورت این گراف را می‌سازیم که برای هر i ( $0 \le i \lt 1000$ ) و هر راس مثل v در $G_i$ ، آن را توسط یک یال یک طرفه با وزن $t_v$ به شهر متناظرش در $G_{i+1}$ وصل می‌کنیم.

می‌توانید مشاهده کنید که جواب معادل کوتاه ترین مسیر از شهر 1 در $G_0$ به یکی از شهر‌های n در یکی از $G_i$ ها است که طول مسیر کمینه شود از طرفی $G_{1001}$ به بعد چون هیچ یالی ندارند نیازی بهشون نداریم پس تعداد راس‌های ما برابر $1001 \times n$ و تعداد یال‌ها حداکثر $1001 \times m$ است که الگوریتم Dijkstra می‌تواند جواب مسئله را پیدا کند.

* محدودیت زمان:‌ ۱ ثانیه * محدودیت حافظه: ۲۵۶ مگابایت ------------------------------ بابای حسنی به حسنی سوالی را داده و به او گفته تا این سوال را حل کند. اما چون حسنی زیاد علاقه‌ای به حل سوال ندارد، از شما خواسته تا این سوال را برای او حل کنید. آرایه‌ای به نام $a$ به طول $ n $ داریم. می‌خواهیم بلندترین زیردنباله‌ای از آرایه را پیدا کنیم که *صعودی-نزولی* باشد. حسنی به دنباله $b_0, b_1, ... , b_{k-1\ }$ *صعودی-نزولی* می‌گوید اگر سه شرط زیر برای آن برقرار باشد: + به ازای برای هر $i$ فرد که $ 0 \lt i \lt k-1 $ داشته باشیم : $ b_{i-1} \lt b_{i} \gt b_{i+1} \ $ + به ازای برای هر $i$ زوج که $ 0 \lt i \lt k-1 $ داشته باشیم : $ b_{i-1} \gt b_{i} \lt b_{i+1} \ $ + برای $i$ برابر با صفر هم داشته باشیم: $b_0 \lt b_1$ حال شما باید طول بلندترین زیردنباله‌ای از آرایه $a$ که *صعودی-نزولی* است را پیدا کنید و آن را چاپ کنید. **نکته:** به آرایه $b$ یک زیردنباله از آرایه $a$ می‌گوییم اگر بتوان با حذف تعدادی عضو از آرایه $a$ به آرایه $b$ رسید. # ورودی در اولین خط ورودی عدد $n$ و در خط بعدی $n$ عدد امده است که عدد $i$ ام مقدار خانه $i$ ام آرایه است. $$ 1 \le n \le 100\ 000$$ $$ |a_i| \le 10^9$$ # خروجی در تنها خط خروجی طول بلندترین زیردنباله *صعودی-نزولی* را بگویید. # مثال # ورودی نمونه ۱ ``` 7 5 1 9 2 3 6 2 ``` # خروجی نمونه ۱ ``` 5 ``` برای مثال دنباله $<1, 9, 2, 3, 2>$ یکی از جواب‌های ممکن است. # ورودی نمونه ۲ ``` 4 1 2 1 2 ``` # خروجی نمونه ۲ ``` 4 ``` در این حالت کل آرایه $a$ *صعودی-نزولی* است. # وروی نمونه ۳ ``` 4 2 1 2 1 ``` # خروجی نمونه ۳ ``` 3 ``` ------------------------- <details class="blue"> <summary> راهنمایی ۱ </summary> اگر دو عنصر متوالی و مساوی وجود داشت، می‌توانیم یکی را به دلخواه حذف کنیم چون در جواب مسئله تاثیری ندارد. اگر سه عنصر متوالی وجود داشته باشد که صعودی باشند یعنی اولی کمتر از دومی و دومی کمتر از سومی باشد می‌توانیم عنصر دوم را حذف کنیم. (چرا؟) </details> <details class="blue"> <summary> اثبات راهنمایی ۱ </summary> اگر دنبال بهینه‌ای وجود داشته باشد که عنصر وسط (یعنی دوم) در این دنباله باشد طبق تعریف دنباله صعودی-نزولی، ممکن نیست هر سه عنصر در این دنباله باشند. پس می‌توان جای عنصر دوم یکی از دو عنصر که استفاده نشده را قرار داد. (در صورتی که این عنصر، اندیس فرد داشت جای آن عنصر بعدی که بزرگ‌تر است (و در نتیجه بهتر است) را قرار می‌دهیم و در غیر این صورت عنصر دیگر) </details> <details class="blue"> <summary> راهنمایی ۲ </summary> اگر *k* عنصر متوالی صعودی وجود داشت طبق راهنمایی قبل فقط اولی و اخری را نگه می‌داریم و بقیه را حذف می‌کنیم. همینطوری اگر *k* عنصر متوالی نزولی وجود داشت اولی و اخری را نگه می‌داریم و بقیه را حذف می‌کنیم. </details> <details class="blue"> <summary> راه حل </summary> بعد از حذف عنصر‌های اضافه که در راهنمایی ۲ گفته شد، می‌توانید مشاهده کنید که دنباله باقی‌مانده، یک دنباله صعودی-نزولی است. البته ممکن است نیاز باشد اولین عنصر را نیز حذف کنید در صورتی که عنصر اولی بزرگتر از عنصر بعدی باشد. دنباله جدید صعودی - نزولی است چون عضو دوم بزرگتر از عضو اول است و اگر عنصر سوم بزرگتر از دومی باشد سه عنصر متوالی صعودی پیدا شده که تناقض دارد. پس عنصر سوم کوچک‌تر از عنصر دومی است. حالا اگر عنصر چهارم کوچک‌تر از عنصر سوم باشد دوباره سه عنصر متوالی نزولی پیدا شده که تناقض دارد پس عنصر چهارم بزرگ‌تر از عنصر سوم است. اگر همین روال را ادامه بدهیم می‌بینیم که دنباله صعودی-نزولی است. از طرفی این دنباله بلندترین است چون دنبال بهینه‌ای وجود داشته باشد که عنصر وسط (یعنی دوم) در این دنباله باشد طبق تعریف دنباله صعودی-نزولی ممکن نیست هر سه عنصر در این دنباله باشند پس می‌توان جای عنصر دوم یکی از دو عنصر که استفاده نشده را قرار داد (در صورتی که این عنصر، اندیس فرد داشت جای آن عنصر بعدی که بزرگ‌تر است (و در نتیجه بهتر است) را قرار می‌دهیم و در غیر این صورت عنصر دیگر) </details>

جدی

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

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

آرایه‌ای به نام $a$ به طول $n$ داریم. می‌خواهیم بلندترین زیردنباله‌ای از آرایه را پیدا کنیم که صعودی-نزولی باشد.

حسنی به دنباله $b_0, b_1, ... , b_{k-1\ }$ صعودی-نزولی می‌گوید اگر سه شرط زیر برای آن برقرار باشد:

به ازای برای هر $i$ فرد که $0 \lt i \lt k-1$ داشته باشیم : $b_{i-1} \lt b_{i} \gt b_{i+1} \$
به ازای برای هر $i$ زوج که $0 \lt i \lt k-1$ داشته باشیم : $b_{i-1} \gt b_{i} \lt b_{i+1} \$
برای $i$ برابر با صفر هم داشته باشیم: $b_0 \lt b_1$

حال شما باید طول بلندترین زیردنباله‌ای از آرایه $a$ که صعودی-نزولی است را پیدا کنید و آن را چاپ کنید.

نکته: به آرایه $b$ یک زیردنباله از آرایه $a$ می‌گوییم اگر بتوان با حذف تعدادی عضو از آرایه $a$ به آرایه $b$ رسید.

ورودی🔗

در اولین خط ورودی عدد $n$ و در خط بعدی $n$ عدد امده است که عدد $i$ ام مقدار خانه $i$ ام آرایه است. $1 \le n \le 100\ 000$ $|a_i| \le 10^9$

خروجی🔗

در تنها خط خروجی طول بلندترین زیردنباله صعودی-نزولی را بگویید.

مثال🔗

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

7
5 1 9 2 3 6 2

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

برای مثال دنباله $<1, 9, 2, 3, 2>$ یکی از جواب‌های ممکن است.

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

4
1 2 1 2

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

در این حالت کل آرایه $a$ صعودی-نزولی است.

وروی نمونه ۳🔗

4
2 1 2 1

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

راهنمایی ۱

اگر دو عنصر متوالی و مساوی وجود داشت، می‌توانیم یکی را به دلخواه حذف کنیم چون در جواب مسئله تاثیری ندارد.

اگر سه عنصر متوالی وجود داشته باشد که صعودی باشند یعنی اولی کمتر از دومی و دومی کمتر از سومی باشد می‌توانیم عنصر دوم را حذف کنیم. (چرا؟)

اثبات راهنمایی ۱

اگر دنبال بهینه‌ای وجود داشته باشد که عنصر وسط (یعنی دوم) در این دنباله باشد طبق تعریف دنباله صعودی-نزولی، ممکن نیست هر سه عنصر در این دنباله باشند. پس می‌توان جای عنصر دوم یکی از دو عنصر که استفاده نشده را قرار داد. (در صورتی که این عنصر، اندیس فرد داشت جای آن عنصر بعدی که بزرگ‌تر است (و در نتیجه بهتر است) را قرار می‌دهیم و در غیر این صورت عنصر دیگر)

راهنمایی ۲

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

راه حل

بعد از حذف عنصر‌های اضافه که در راهنمایی ۲ گفته شد، می‌توانید مشاهده کنید که دنباله باقی‌مانده، یک دنباله صعودی-نزولی است. البته ممکن است نیاز باشد اولین عنصر را نیز حذف کنید در صورتی که عنصر اولی بزرگتر از عنصر بعدی باشد.

دنباله جدید صعودی - نزولی است چون عضو دوم بزرگتر از عضو اول است و اگر عنصر سوم بزرگتر از دومی باشد سه عنصر متوالی صعودی پیدا شده که تناقض دارد. پس عنصر سوم کوچک‌تر از عنصر دومی است. حالا اگر عنصر چهارم کوچک‌تر از عنصر سوم باشد دوباره سه عنصر متوالی نزولی پیدا شده که تناقض دارد پس عنصر چهارم بزرگ‌تر از عنصر سوم است.
اگر همین روال را ادامه بدهیم می‌بینیم که دنباله صعودی-نزولی است.

از طرفی این دنباله بلندترین است چون دنبال بهینه‌ای وجود داشته باشد که عنصر وسط (یعنی دوم) در این دنباله باشد طبق تعریف دنباله صعودی-نزولی ممکن نیست هر سه عنصر در این دنباله باشند پس می‌توان جای عنصر دوم یکی از دو عنصر که استفاده نشده را قرار داد (در صورتی که این عنصر، اندیس فرد داشت جای آن عنصر بعدی که بزرگ‌تر است (و در نتیجه بهتر است) را قرار می‌دهیم و در غیر این صورت عنصر دیگر)

+ محدودیت زمان: ۳ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- آرایه $a$، شامل اعداد $a_1, a_2, ..., a_n\ $ روی تخته نوشته شده است. در هر گام می‌توانیم یکی از دو عملیات زیر را انجام دهیم. + یک عدد $x$ از روی تخته در نظر بگیریم و **تمام** اعداد $x$ روی تخته را با $\left \lfloor{ \frac {x}{2}}\right \rfloor$ جایگزین کنیم. (یعنی به جای هر $x$ روی تخته، $\left \lfloor{ \frac {x}{2}}\right \rfloor$ قرار می‌دهیم.‌) + یک عدد $x$ از روی تخته در نظر بگیریم و **تمام** اعداد $x$ روی تخته را پاک کنیم. از عملیات نوع دوم **حداکثر $k$ بار** می‌توانیم استفاده کنیم. کم‌ترین تعداد مرحله برای این که در انتها کلا عددی روی تخته باقی نماند، یا تمامی اعداد باقی مانده برابر با $0$ باشد، چه‌قدر است؟ # ورودی ورودی شامل دو خط است که خط اول آن شامل دو عدد $n, k$ است. در خط دوم $n$ عدد $a_1, a_2, .., a_n\ $ می‌آید که اعداد اولیه روی تخته را مشخص می‌کند. $$1 \le n \le 100\ 000$$ $$0 \le k \le 10$$ $$1 \le a_i \le 10^9$$ # خروجی در تنها خط خروجی کمترین مراحل مورد نیاز برای رسیدن به شرایط مطلوب را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 5 2 1 2 3 4 5 ``` ## خروجی نمونه ۱ ``` 5 ``` یکی از روش‌ها این است که ابتدا اعداد $5$ و $4$ را با عملیات نوع اول به $2$ تبدیل کنیم. سپس عدد $3$ را به $1$ تبدیل کنیم، اعداد روی تخته $<1, 2, 1, 2, 2>$ خواهند بود. در نهایت عدد $1, 2$ را پاک کنیم و دنباله تهی می‌شود. در مجموع $5$ عملیات انجام شده است. ## ورودی نمونه ۲ ``` 4 1 1 1 2 3 ``` ## خروجی نمونه ۲ ``` 3 ``` در یکی از روش‌های بهینه ابتدا عدد $3$ را حذف می‌کنیم،‌ سپس $2$ را با عملیات اول به $1$ تبدیل می‌کنیم و نهایتا همه اعداد $1$ را با عملیات اول به صفر تبدیل می‌کنیم. ## ورودی نمونه ۳ ``` 10 3 10 20 30 40 50 60 70 80 90 100 ``` ## خروجی نمونه ۳ ``` 16 ``` ------------- <details class="blue"> <summary> راهنمایی ۱ </summary> در این بخش فرض کنید $k=0$ است. نمایش باینری اعداد را در نظر بگیرید، با عملیات اول آخرین رقم نمایش دودویی حذف می‌شود. اکنون [درخت ترای](https://fa.wikipedia.org/wiki/%D8%AF%D8%B1%D8%AE%D8%AA_%D9%BE%DB%8C%D8%B4%D9%88%D9%86%D8%AF%DB%8C) اعداد آرایه را در نظر بگیرید، هدف این است که با حذف آخرین رقم همه اعداد را به صفر تبدیل کنیم که یعنی درخت ترای اعدادمان را تک راسی کنیم، پس می‌توان دریافت که به حداقل به اندازه تعداد راس‌های ترای منهای یک، عملیات نیاز داریم، چون در هر عملیات حداکثر یک راس حذف می‌شود. همین‌طور می‌توان روشی ارائه داد تا با دقیقا همین تعداد عملیات، همه اعداد را به صفر تبدیل کنیم. پس مساله در حالت $k=0$، حل شد. سعی کنید با همین ایده مساله را برای $k>0$ حل کنید. </details> <details class="blue"> <summary> راهنمایی ۲ </summary> در این بخش به بیان ایده حالت کلی مساله می‌پردازیم. با استفاده از برنامه‌نویسی پویا روی درخت ترای مساله را حل می‌کنیم. فرض کنید بخواهیم برای هر راس در درخت ترای مثل $v$ (که متناظر با یک عدد است) ، مساله را برای اعداد درون زیردرخت آن راس حل کنیم، یعنی بخواهیم با $j$ عملیات حذف $1 \le j \le k$ ، اعداد درون زیردرخت $v$ را به $v$ تبدیل کنیم. برای محاسبه این مقادیر به این نتیجه می‌رسیم که لازم است روی این که آیا همه اعداد زیردرخت حذف شده‌اند یا خیر حالت‌بندی کنیم در نتیجه لازم است آرایه $dp$ای‌داشته باشیم که $$dp[v][j][t]$$ کمترین تعداد عملیات‌های نوع اول لازم برای اینکه اعداد درون زیردرخت $v$ را به $v$ تبدیل کنیم و حداکثر $j$ بار ار عملیات حذف استفاده کنیم. هم‌چنین اگر $t=0$ تضمین می‌شود که همه اعداد درون این زیردرخت حذف شده‌اند و هیچ عددی باقی نمانده است و درحالت $t=1$، ممکن است تعدادی از اعداد (طبیعتا همگی $v$ هستند)، باقی بمانند. </details> <details class="blue"> <summary> راه حل </summary> در این بخش شیوه پرکردن آرایه $dp$ را شرح می‌دهیم. فرض کنید بخواهیم $dp[v][j][t]$ را محاسبه کنیم. فرزند چپ $v$ را $v_l$ و فرزند راست آن‌ را $v_r$ بنامید. حالت بندی کنید که چه تعداد عملیات حذف را در زیردرخت $v_l$ و چه تعداد را در زیر درخت $v_r$ استفاده کنیم، هم‌چنین با حالت بندی روی اینکه در هر کدام از زیردرخت‌ها کل اعداد حذف شده‌اند یا خیر، می‌توان دریافت که یک عملیات اضافه برای تبدیل $v_l$ و یا $v_r$ به $v$ نیاز داریم یا خیر. هم‌چنین یک حالت این است که روی $v$ عملیات حذف را انجام دهیم که نباید آن را فراموش کنید. در نهایت پیچیدگی نهایی حل این مساله $\theta (n k^2 \log_2 A_i)$ خواهد بود. </details>

دریچه

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

آرایه $a$ ، شامل اعداد $a_1, a_2, ..., a_n\$ روی تخته نوشته شده است. در هر گام می‌توانیم یکی از دو عملیات زیر را انجام دهیم.

یک عدد $x$ از روی تخته در نظر بگیریم و تمام اعداد $x$ روی تخته را با $\left \lfloor{ \frac {x}{2}}\right \rfloor$ جایگزین کنیم. (یعنی به جای هر $x$ روی تخته، $\left \lfloor{ \frac {x}{2}}\right \rfloor$ قرار می‌دهیم.‌)
یک عدد $x$ از روی تخته در نظر بگیریم و تمام اعداد $x$ روی تخته را پاک کنیم.

از عملیات نوع دوم حداکثر $k$ بار می‌توانیم استفاده کنیم.

کم‌ترین تعداد مرحله برای این که در انتها کلا عددی روی تخته باقی نماند، یا تمامی اعداد باقی مانده برابر با $0$ باشد، چه‌قدر است؟

ورودی🔗

ورودی شامل دو خط است که خط اول آن شامل دو عدد $n, k$ است.

در خط دوم $n$ عدد $a_1, a_2, .., a_n\$ می‌آید که اعداد اولیه روی تخته را مشخص می‌کند.

$1 \le n \le 100\ 000$ $0 \le k \le 10$ $1 \le a_i \le 10^9$

خروجی🔗

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

مثال🔗

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

5 2
1 2 3 4 5

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

یکی از روش‌ها این است که ابتدا اعداد $5$ و $4$ را با عملیات نوع اول به $2$ تبدیل کنیم. سپس عدد $3$ را به $1$ تبدیل کنیم، اعداد روی تخته $<1, 2, 1, 2, 2>$ خواهند بود. در نهایت عدد $1, 2$ را پاک کنیم و دنباله تهی می‌شود. در مجموع $5$ عملیات انجام شده است.

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

4 1
1 1 2 3

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

در یکی از روش‌های بهینه ابتدا عدد $3$ را حذف می‌کنیم،‌ سپس $2$ را با عملیات اول به $1$ تبدیل می‌کنیم و نهایتا همه اعداد $1$ را با عملیات اول به صفر تبدیل می‌کنیم.

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

10 3
10 20 30 40 50 60 70 80 90 100

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

راهنمایی ۱

در این بخش فرض کنید $k=0$ است.

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

همین‌طور می‌توان روشی ارائه داد تا با دقیقا همین تعداد عملیات، همه اعداد را به صفر تبدیل کنیم.

پس مساله در حالت $k=0$ ، حل شد. سعی کنید با همین ایده مساله را برای $k>0$ حل کنید.

راهنمایی ۲

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

با استفاده از برنامه‌نویسی پویا روی درخت ترای مساله را حل می‌کنیم. فرض کنید بخواهیم برای هر راس در درخت ترای مثل $v$ (که متناظر با یک عدد است) ، مساله را برای اعداد درون زیردرخت آن راس حل کنیم، یعنی بخواهیم با $j$ عملیات حذف $1 \le j \le k$ ، اعداد درون زیردرخت $v$ را به $v$ تبدیل کنیم.

برای محاسبه این مقادیر به این نتیجه می‌رسیم که لازم است روی این که آیا همه اعداد زیردرخت حذف شده‌اند یا خیر حالت‌بندی کنیم در نتیجه لازم است آرایه $dp$ ای‌داشته باشیم که $dp[v][j][t]$ کمترین تعداد عملیات‌های نوع اول لازم برای اینکه اعداد درون زیردرخت $v$ را به $v$ تبدیل کنیم و حداکثر $j$ بار ار عملیات حذف استفاده کنیم. هم‌چنین اگر $t=0$ تضمین می‌شود که همه اعداد درون این زیردرخت حذف شده‌اند و هیچ عددی باقی نمانده است و درحالت $t=1$ ، ممکن است تعدادی از اعداد (طبیعتا همگی $v$ هستند)، باقی بمانند.

راه حل

در این بخش شیوه پرکردن آرایه $dp$ را شرح می‌دهیم.

فرض کنید بخواهیم $dp[v][j][t]$ را محاسبه کنیم.

فرزند چپ $v$ را $v_l$ و فرزند راست آن‌ را $v_r$ بنامید.

حالت بندی کنید که چه تعداد عملیات حذف را در زیردرخت $v_l$ و چه تعداد را در زیر درخت $v_r$ استفاده کنیم، هم‌چنین با حالت بندی روی اینکه در هر کدام از زیردرخت‌ها کل اعداد حذف شده‌اند یا خیر، می‌توان دریافت که یک عملیات اضافه برای تبدیل $v_l$ و یا $v_r$ به $v$ نیاز داریم یا خیر.

هم‌چنین یک حالت این است که روی $v$ عملیات حذف را انجام دهیم که نباید آن را فراموش کنید.

در نهایت پیچیدگی نهایی حل این مساله $\theta (n k^2 \log_2 A_i)$ خواهد بود.

+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- اگر دنباله‌ای از اعداد داشته باشید به اولین عدد طبیعی‌ای که در آن ظاهر نشده _Mex_ آن دنباله می‌گوییم. برای مثال _Mex_ دنباله $(1, 2, 5, 9)$ برابر $3$ و _Mex_ دنباله $(2, 5)$ برابر $1$ است. دنباله $a_1, a_2, a_3,...,a_n\ $ به شما داده شده است و باید جمع _Mex_ تمام زیربازه‌های آن را به دست بیاورید. (در مجموع $\frac{n(n+1)}{2}$ زیربازه داریم.) در واقع اگر $\ Mex_{i,j}$‌را برابر _Mex_ زیر دنباله $(a_i,a_{i+1},...,a_j)\ $ تعریف کنیم، شما باید مقدار زیر را چاپ کنید. $$\sum_{i=1}^{n}\ \sum_{j=i}^{n} Mex_{i,j}$$ # ورودی در سطر اول ورودی عدد $n$ و در سطر دوم $n$ عدد به شما داده می‌شود که عدد $i$-ام برابر عضو $i$ ام دنباله است. $$1 \le n, a_i \le 100\ 000$$ # خروجی در تنها خط خروجی مقدار خواسته شده را نمایش دهید. # مثال ## ورودی نمونه ۱ ``` 5 1 2 3 4 5 ``` ## خروجی نمونه ۱ ``` 30 ``` توضیح: $Mex_{1,1} = 2$ $Mex_{1,2} = 3$ $Mex_{1,3} = 4$ $Mex_{1,4} = 5$ $Mex_{1,5} = 6$ و _Mex_ زیربازه‌هایی که ۱ را ندارند برابر ۱ است. ## ورودی نمونه ۲ ``` 8 2 1 4 2 1 3 2 1 ``` ## خروجی نمونه ۲ ``` 113 ``` -------------- <details class="blue"> <summary> راهنمایی ۱ </summary> فرض کنید برای هر پیشوند از ارایه *Mex* را به دست آوردید. حالا عنصر اول را حذف کنید و *Mex* هر پیشوند را حساب کنید. </details> <details class="blue"> <summary> راهنمایی ۲ </summary> بعد از حذف عنصر اول، پیشنود‌هایی که *Mex* آن کمتر از $a_1$ بودند تغییری نمی‌کنند. </details> <details class="blue"> <summary> راهنمایی ۳ </summary> بعد از حذف عنصر اول در صورتی که _Mex_ پیشنوندی قرار باشد تغییر کند، مقدار آن برابر $a_1$ می‌شود. </details> <details class="blue"> <summary> راه حل </summary> اگر $m_i$ برابر *Mex* پیشوندی باشد که به *i* ختم می شود. می‌توانید مشاهده کنید که دنباله زیر صعودی است: $$ m_1 \le m_2 \le m_3 \le ... \le m_n$$ و وقتی عنصر اول را حذف می‌کنید، اگر دومین تکرار این عنصر در اندیس *x* باشد. (یعنی $a_1= a_x$) برای هر $1 \le i \lt x$ مقدار $m_i$ ممکن است عوض شود و بقیه تغییری نمی‌کنند چون قبلا در خانه اول $a_1$ وجود داشته و تمام پیشوند‌هایی که از خانه *x* رد می‌شودند هنوز $a_1$ را دارند. و از طرفی برای هر کدام از آن *i*ها مقدار $m_i$ مینیمم گرفته می‌شود با $a_1$ چون ممکن است این عنصر اولین کسی باشد که دیگر در بازه نیست. پیاده سازی الگوریتم با درخت سگمنت یا *BST* امکان پذیر است. </details>

جهمه

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

اگر دنباله‌ای از اعداد داشته باشید به اولین عدد طبیعی‌ای که در آن ظاهر نشده Mex آن دنباله می‌گوییم.
برای مثال Mex دنباله $(1, 2, 5, 9)$ برابر $3$ و Mex دنباله $(2, 5)$ برابر $1$ است.

دنباله $a_1, a_2, a_3,...,a_n\$ به شما داده شده است و باید جمع Mex تمام زیربازه‌های آن را به دست بیاورید. (در مجموع $\frac{n(n+1)}{2}$ زیربازه داریم.)

در واقع اگر $\ Mex_{i,j}$ ‌را برابر Mex زیر دنباله $(a_i,a_{i+1},...,a_j)\$ تعریف کنیم، شما باید مقدار زیر را چاپ کنید. $\sum_{i=1}^{n}\ \sum_{j=i}^{n} Mex_{i,j}$

ورودی🔗

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

$1 \le n, a_i \le 100\ 000$

خروجی🔗

در تنها خط خروجی مقدار خواسته شده را نمایش دهید.

مثال🔗

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

5
1 2 3 4 5

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

توضیح:

$Mex_{1,1} = 2$
$Mex_{1,2} = 3$
$Mex_{1,3} = 4$
$Mex_{1,4} = 5$
$Mex_{1,5} = 6$

و Mex زیربازه‌هایی که ۱ را ندارند برابر ۱ است.

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

8
2 1 4 2 1 3 2 1

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

راهنمایی ۱

فرض کنید برای هر پیشوند از ارایه Mex را به دست آوردید. حالا عنصر اول را حذف کنید و Mex هر پیشوند را حساب کنید.

راهنمایی ۲

بعد از حذف عنصر اول، پیشنود‌هایی که Mex آن کمتر از $a_1$ بودند تغییری نمی‌کنند.

راهنمایی ۳

بعد از حذف عنصر اول در صورتی که Mex پیشنوندی قرار باشد تغییر کند، مقدار آن برابر $a_1$ می‌شود.

راه حل

اگر $m_i$ برابر Mex پیشوندی باشد که به i ختم می شود. می‌توانید مشاهده کنید که دنباله زیر صعودی است:

$m_1 \le m_2 \le m_3 \le ... \le m_n$

و وقتی عنصر اول را حذف می‌کنید، اگر دومین تکرار این عنصر در اندیس x باشد. (یعنی $a_1= a_x$ ) برای هر $1 \le i \lt x$ مقدار $m_i$ ممکن است عوض شود و بقیه تغییری نمی‌کنند چون قبلا در خانه اول $a_1$ وجود داشته و تمام پیشوند‌هایی که از خانه x رد می‌شودند هنوز $a_1$ را دارند. و از طرفی برای هر کدام از آن iها مقدار $m_i$ مینیمم گرفته می‌شود با $a_1$ چون ممکن است این عنصر اولین کسی باشد که دیگر در بازه نیست.

پیاده سازی الگوریتم با درخت سگمنت یا BST امکان پذیر است.