دایره عجیب

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

حسنی و $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$ تا بعدی حسنی خود حسنی است!

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- **می‌توانید شعر زیر را نخوانید و تاثیری در فهم سوال ندارد.** توی ده [شلمرود](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 ```

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

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

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

توی ده شلمرود

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

دمت مثال جارو

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

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

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

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

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

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

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

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

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

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

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

«نه جانم»

«چرا نمیای؟»

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

صبح تا غروب

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

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

اما تو چی؟

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

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

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

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

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

گردش‌زنان

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

«جوجه کوچولو

کوچول موچولو

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

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

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

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

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

اما تو چی؟

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

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

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

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

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

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

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

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

فلفلی گفت:

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

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

اما تو چی؟

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

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

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

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

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

«میام، میام»

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

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

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

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

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

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

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

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

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

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

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

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

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

مرغه می‌گفت:

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

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

غازه می‌گفت:

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

توی ده شلمرود

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

بعد از این که حسنی تمیز شد و با همه بازی کرد، همه دور هم جمع شدند و از بابای حسنی خواستند که ازشون عکس بگیره. ولی وقتی بابای حسنی اومد، فهمیدند که حداکثر $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

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

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- حسنی برای این که در تابستان وقتش را تلف نکند به کسب و کار روی آورده و به تازگی بانکی به نام **کناب** تاسیس کرده است. از آن‌جایی که دوست دارد شما نیز عضو کناب باشید به شما یک پروژه داده و خواسته تا همراه‌بانکی بنویسید که درخواست‌های زیر را اجرا کند. ``` 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` منفی پانصد.

هارمه کناب

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

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

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 منفی پانصد.

+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- در کشور(!) شلمرود، $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$ وجود ندارد.

مسیر عجیب

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

در کشور(!) شلمرود، $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$ وجود ندارد.

* محدودیت زمان:‌ ۱ ثانیه * محدودیت حافظه: ۲۵۶ مگابایت ------------------------------ بابای حسنی به حسنی سوالی را داده و به او گفته تا این سوال را حل کند. اما چون حسنی زیاد علاقه‌ای به حل سوال ندارد، از شما خواسته تا این سوال را برای او حل کنید. آرایه‌ای به نام $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 ```

جدی

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

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

آرایه‌ای به نام $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

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

+ محدودیت زمان: ۳ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- آرایه $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 ```

دریچه

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

آرایه $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

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

جهمه

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

اگر دنباله‌ای از اعداد داشته باشید به اولین عدد طبیعی‌ای که در آن ظاهر نشده 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