+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ----- پس از تنش‌های بسیار میان راک (رادین کمونیست)‌ و کاکا (کاوه کاپیتالیست)، این دو فرد با هم وارد جنگ شده‌اند. کاهو یکی از سربازهای ارتش کاکا است و از آنجایی که روحیه جنگجویی ندارد می‌خواهد از میدان جنگ فرار کند. میدان جنگ به شکل یک جدول $n \times n$ است که در تعدادی از خانه های آن مین وجود دارد. کاهو در خانه‌ی گوشه **پایین-چپ** جدول قرار دارد و می‌خواهد به خانه‌ی گوشه **بالا-راست** جدول برود تا از میدان جنگ فرار کند. او در هر لحظه به سمت یکی از چهار جهت بالا، پایین، چپ و راست قرار دارد. کاهو می‌خواهد **پیش از شروع** دنباله‌ای از حرکات را برای خود یادداشت کند تا در هنگام فرار از آن پیروی کند. هر حرکت دنباله به یکی از سه حالت زیر است: + یک واحد در همین جهت به جلو برو. + ۹۰ درجه به سمت راست بچرخ. + ۹۰ درجه به سمت چپ بچرخ. همچنین کاهو آدم عاقلی است بنابراین اگر با پیروی از دستوری از جدول خارج شود، پا بر روی مین بگذارد یا اگر پیش از این دستور به نقطه‌ی پایان رسیده باشد این دستور را اجرا نمی‌کند و سراغ دستور بعدی میرود. **یعنی در هر لحظه ای که کاهو به گوشه بالا-راست جدول رسیده باشد حرکت خود را متوقف می‌کند و دیگر به حرکت ادامه نمی‌دهد.** کاهو میداند پیش از نوشتن یادداشت خود به یکی از دو جهت بالا یا راست بوده، **اما نمی‌داند کدام یک.** او می‌خواهد یادداشت خود را طوری بنویسد که در هر دو حالت جهت اولیه با اجرای دستورات مطابق آن از خانه **پایین-چپ** به خانه **بالا-راست** جدول برسد. منطقا میخواهد تعداد دستوراتی که برای خود می‌نویسد کمینه باشد. شما باید عدد کمینه تعداد دستوراتی که او نیاز دارد بنویسد را بدست بیاورید. # ورودی در خط اول یک عدد $n$ داده می‌شود. سپس در $n$ خط بعدی در خط $i$ ام یک رشته به طول $n$ داده می‌شود که کاراکتر $j$ ام آن وضعیت وجود/عدم‌وجود مین در خانه محل تقاطع سطر $i$ ام از بالا و ستون $j$ از چپ است. کاراکتر `M` نشان‌دهنده وجود مین در این خانه و `K` نشان‌دهنده خالی بودن این خانه است. $$ n \le 20 $$ تضمین شده است مسیری بدون مین از گوشه پایین-چپ به گوشه بالا-راست جدول وجود دارد. # خروجی طول کوتاه‌ترین دستورالعمل که کاهو را به مقصد می‌رساند را خروجی دهید. ## ورودی نمونه ۱ ``` 3 KMK KKK KKK ``` ## خروجی نمونه ۱ ``` 9 ``` یکی از دستورالعمل‌های نمونه «جلو، راست، جلو، جلو، چپ، جلو، چپ، جلو، جلو» است.

الفرار

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

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

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

میدان جنگ به شکل یک جدول $n \times n$ است که در تعدادی از خانه های آن مین وجود دارد. کاهو در خانه‌ی گوشه پایین-چپ جدول قرار دارد و می‌خواهد به خانه‌ی گوشه بالا-راست جدول برود تا از میدان جنگ فرار کند. او در هر لحظه به سمت یکی از چهار جهت بالا، پایین، چپ و راست قرار دارد.

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

یک واحد در همین جهت به جلو برو.
۹۰ درجه به سمت راست بچرخ.
۹۰ درجه به سمت چپ بچرخ.

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

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

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

شما باید عدد کمینه تعداد دستوراتی که او نیاز دارد بنویسد را بدست بیاورید.

ورودی🔗

در خط اول یک عدد $n$ داده می‌شود. سپس در $n$ خط بعدی در خط $i$ ام یک رشته به طول $n$ داده می‌شود که کاراکتر $j$ ام آن وضعیت وجود/عدم‌وجود مین در خانه محل تقاطع سطر $i$ ام از بالا و ستون $j$ از چپ است. کاراکتر M نشان‌دهنده وجود مین در این خانه و K نشان‌دهنده خالی بودن این خانه است.

$n \le 20$

تضمین شده است مسیری بدون مین از گوشه پایین-چپ به گوشه بالا-راست جدول وجود دارد.

خروجی🔗

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

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

3
KMK
KKK
KKK

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

یکی از دستورالعمل‌های نمونه «جلو، راست، جلو، جلو، چپ، جلو، چپ، جلو، جلو» است.

+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ------ بعد از به قدرت رسیدن کاکا در سرزمین غااززز، جدل و جدال بین کاکا و راک بیشتر و بیشتر شد... کاکا از طریق جاسوس‌هایش خبردار شده که راک در پروژه‌ای جدید قصد دارد $n$ تانک متمایز طراحی کند. همچنین میداند راک برای پروژه $m$ مهندس در اختیار دارد. پروسه طراحی تانک به این شکل است که هر مهندس در ساخت حداکثر یک تانک می‌تواند دخیل باشد (به دلایل فوق امنیتی)، و طراحی تانک $i$ ام به به اندازه $t_i$ تقسیم بر تعداد مهندس‌هایی که آن را طراحی می‌کنند زمان می‌برد. یعنی اگر $k$ مهندس در طراحی تانک $i$ شرکت داشته باشند، طراحی این تانک $\frac{t_i}{k}$ ساعت زمان می‌برد (این مقدار لزوماً صحیح نیست). از آنجایی که منابع محدود است، طراحی تانک‌ها نمی‌تواند به صورت موازی انجام شود. یعنی در هر لحظه فقط یک تانک می‌تواند در حال ساخت باشد. حال کاکا می‌خواهد بداند اگر راک به بهینه‌ترین روش عمل کند، پروسه ساخت تانک‌ها چند ساعت زمان می‌برد. **دقت کنید پاسخ لزوماً عددی صحیح نیست و شما باید گرد شده عدد پاسخ را به عنوان جواب خروجی دهید.** # ورودی در خط اول $n, m$ به ترتیب تعداد تانک‌ها و تعداد مهندس‌ها داده می‌شود. در $n$ خط بعد $t_i$ زمان ساخت تانک $i$ ام داده می‌شود. $$t_i, m \le 10 ^ {12}$$$$ n \le 10 ^ {5}$$ $$n \le m$$ # خروجی نزدیک‌ترین عدد صحیح به کمینه زمان ساخت تانک‌ها را خروجی دهید. # زیرمسئله‌‌ها | زیرمسئه | نمره | محدودیت |:------------------:|:----------:|:------------------:| | ۱ | ۵ | $m \le 200 , n \le 30 $ | | ۲ | ۵۵ | $ m \le 3 * 10 ^ 6 $ | | ۳ | ۴۰ | بدون محدودیت بیشتر | # مثال ## ورودی نمونه ۱ ``` 2 5 10 4 ``` ## خروجی نمونه ۱ ``` 5 ```

تانک سازی

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

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

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

همچنین میداند راک برای پروژه $m$ مهندس در اختیار دارد. پروسه طراحی تانک به این شکل است که هر مهندس در ساخت حداکثر یک تانک می‌تواند دخیل باشد (به دلایل فوق امنیتی)، و طراحی تانک $i$ ام به به اندازه $t_i$ تقسیم بر تعداد مهندس‌هایی که آن را طراحی می‌کنند زمان می‌برد.

یعنی اگر $k$ مهندس در طراحی تانک $i$ شرکت داشته باشند، طراحی این تانک $\frac{t_i}{k}$ ساعت زمان می‌برد (این مقدار لزوماً صحیح نیست).

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

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

ورودی🔗

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

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

$t_i, m \le 10 ^ {12}$ $n \le 10 ^ {5}$ $n \le m$

خروجی🔗

نزدیک‌ترین عدد صحیح به کمینه زمان ساخت تانک‌ها را خروجی دهید.

زیرمسئله‌‌ها🔗

زیرمسئه	نمره	محدودیت
۱	۵	$m \le 200 , n \le 30$
۲	۵۵	$m \le 3 * 10 ^ 6$
۳	۴۰	بدون محدودیت بیشتر

مثال🔗

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

2 5
10
4

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

+ محدودیت زمان: ۲.۵ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- راک پس از ساخت تانک‌ها قرار است به قلعه‌ی کاکا حمله کند. قلعه توسط دیواری دفاعی محافظت میشود. کاکا می‌داند تانک $i$ ام بازه $[l_i, r_i]$ دیوار دفاعی سرزمینش را هدف گرفته. با شلیک زیرمجموعه‌ای از تانک‌های راک، تمامی قسمت‌های دیوار که حداقل یک تانک به آن شلیک کند تخریب میشود. برای بازسازی دیوار کاکا باید به تعداد مولفه‌های قسمت‌های تخریب شده به توان $k$ هزینه کند (یعنی اگر تعداد مولفه‌های خراب شده $x$ باشد، باید $x ^ k$ هزینه کند). برای فهم بیشتر به توضیحات ورودی نمونه مراجعه کنید. مجموع هزینه بازسازی دیوار به‌ازای تمامی زیرمجموعه‌های ناتهی از تانک‌هایی که شلیک می‌کنند را محاسبه کنید و مقدار حساب شده را باقیمانده بر $10 ^ 9 + 7$ به کاکا بگویید. # ورودی در خط اول ورودی $n$ و $k$ به شما داده میشود. در هر یک از $n$ خط بعد دو عدد $l_i$ و $r_i$ داده میشود. $(l_i < r_i)$ **نکته: تمامی $l_i, r_i$ ها $2n$ عدد متمایز عضو $\{1, 2, \dots, 2n\}$ هستند.** $n \le 10 ^ {5}, 2 \le k \le 10$ # خروجی پاسخ مسئله را باقیمانده بر $10 ^ 9 + 7$ چاپ کنید. # زیر مسئله‌ها | زیرمسئله | نمره | محدودیت |:------------------:|:----------:|:------------------:| | ۱ | ۶ | $ n \le 16 $ | | ۲ | ۲۰ | $ n \le 1000 , k = 2 $ | | ۳ | ۲۰ | $ n \le 1000 $ | | ۴ | ۵۴ | بدون محدودیت بیشتر| ## ورودی نمونه ۱ ``` 3 2 1 6 2 3 4 5 ``` ## خروجی نمونه ۱ ``` 10 ``` هزینه بازسازی برای هر زیرمجموعه از تانک‌هایی که شلیک می‌کنند در پایین نوشته شده: $$\{[1, 6]\} : 1$$ $$\{[2, 3]\} : 1$$ $$\{[4, 5]\} : 1$$$$\{[4, 5], [1, 6]\} : 1$$ $$\{[1, 6], [2, 3]\} : 1$$ $$\{[4, 5], [2, 3]\} : 4$$ $$\{[2, 3], [1, 6], [4, 5]\} : 1$$

بازسازی

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

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

کاکا می‌داند تانک $i$ ام بازه $[l_i, r_i]$ دیوار دفاعی سرزمینش را هدف گرفته. با شلیک زیرمجموعه‌ای از تانک‌های راک، تمامی قسمت‌های دیوار که حداقل یک تانک به آن شلیک کند تخریب میشود.

برای بازسازی دیوار کاکا باید به تعداد مولفه‌های قسمت‌های تخریب شده به توان $k$ هزینه کند (یعنی اگر تعداد مولفه‌های خراب شده $x$ باشد، باید $x ^ k$ هزینه کند). برای فهم بیشتر به توضیحات ورودی نمونه مراجعه کنید.

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

ورودی🔗

در خط اول ورودی $n$ و $k$ به شما داده میشود.

در هر یک از $n$ خط بعد دو عدد $l_i$ و $r_i$ داده میشود. $(l_i < r_i)$

نکته: تمامی $l_i, r_i$ ها $2n$ عدد متمایز عضو $\{1, 2, \dots, 2n\}$ هستند.

$n \le 10 ^ {5}, 2 \le k \le 10$

خروجی🔗

پاسخ مسئله را باقیمانده بر $10 ^ 9 + 7$ چاپ کنید.

زیر مسئله‌ها🔗

زیرمسئله	نمره	محدودیت
۱	۶	$n \le 16$
۲	۲۰	$n \le 1000 , k = 2$
۳	۲۰	$n \le 1000$
۴	۵۴	بدون محدودیت بیشتر

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

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

هزینه بازسازی برای هر زیرمجموعه از تانک‌هایی که شلیک می‌کنند در پایین نوشته شده:

$\{[1, 6]\} : 1$ $\{[2, 3]\} : 1$ $\{[4, 5]\} : 1$ $\{[4, 5], [1, 6]\} : 1$ $\{[1, 6], [2, 3]\} : 1$ $\{[4, 5], [2, 3]\} : 4$ $\{[2, 3], [1, 6], [4, 5]\} : 1$

+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ------ کاکا پس از تلاش های ناموفق برای کشتن راک تصمیم گرفت با کمک افراد دیگر او را ترور کند. او در شهری زندگی می‌کند که $n$ میدان و $n - 1$ خیابان دوطرفه دارد که هریک دو میدان متفاوت را به هم متصل می‌کند. از هر میدان می‌توان به میدان‌های دیگر رفت (به عبارت دیگر یک درخت است). میدان‌هایی که دقیقاً یک خیابان به آن‌ها متصل است (برگ های درخت) به خارج شهر راه دارند. می‌دانیم راک در ابتدا در میدان $k$ است و می‌خواهد به یک برگ برسد تا از شهر خارج شود و کاکا می‌خواهد از خارج شهر تعدادی از افرادش را در تعدادی از برگ‌ها مستقر کند. راک و افراد کاکا در هر ساعت می‌توانند یک خیابان (متصل به میدان کنونی‌شان) را طی کنند یا در جای خود بمانند و اگر راک و یکی از افراد کاکا در یک لحظه در یک نقطه (درون یک میدان یا یک خیابان) باشند آنگاه راک توسط افراد کاکا ترور می‌شود. **دقت کنید راک و افراد کاکا همیشه موقعیت همدیگر را میدانند.** چون افراد بیشتر برای کاکا هزینه بالاتری دارد می‌خواهد حداقل تعداد افرادی را پیدا کند که راک را بتواند ترور کند. شما باید به کاکا در پیدا کردن این عدد کمک کنید. دقت کنید که اگر پاسخ شما عدد $x$ باشد، یعنی: 1. کاکا روشی برای مستقر کردن $x$ نفر در برگ‌ها دارد که راک به هر روشی عمل کند افراد کاکا بتوانند او را ترور کنند. 2. به ازای هر عدد $y < x$، اگر تعداد افراد کاکا $y$ باشد، همواره راک روشی برای فرار از دست افراد کاکا دارد (مستقل از نحوه کار افراد کاکا). # ورودی در خط اول اعداد $n$ و $k$ تعداد میدان‌ها و میدانی که راک قرار گرفته، به ترتیب داده شده‌اند. $$ 1 \le k \le n \le 10^5 $$ سپس در هر کدام از $n-1$ خط بعدی دو عدد $u$ و $v$ آمده است که نشان دهنده وجود خیابان بین دو میدان $u$ و $v$ است. تضمین می‌شود گراف میدان‌ها و خیابان‌های بینشان یک درخت است. میدان k حداقل 2 همسایه دارد و برگ نیست. # خروجی در تنها خط خروجی کمینه تعداد افرار مورد نیاز برای ترور راک را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 7 1 1 2 1 3 3 4 3 5 4 6 5 7 ``` ## خروجی نمونه ۱ ``` 3 ```

ترور

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

کاکا پس از تلاش های ناموفق برای کشتن راک تصمیم گرفت با کمک افراد دیگر او را ترور کند. او در شهری زندگی می‌کند که $n$ میدان و $n - 1$ خیابان دوطرفه دارد که هریک دو میدان متفاوت را به هم متصل می‌کند. از هر میدان می‌توان به میدان‌های دیگر رفت (به عبارت دیگر یک درخت است).

میدان‌هایی که دقیقاً یک خیابان به آن‌ها متصل است (برگ های درخت) به خارج شهر راه دارند.

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

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

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

دقت کنید که اگر پاسخ شما عدد $x$ باشد، یعنی:

کاکا روشی برای مستقر کردن $x$ نفر در برگ‌ها دارد که راک به هر روشی عمل کند افراد کاکا بتوانند او را ترور کنند.
به ازای هر عدد $y < x$ ، اگر تعداد افراد کاکا $y$ باشد، همواره راک روشی برای فرار از دست افراد کاکا دارد (مستقل از نحوه کار افراد کاکا).

ورودی🔗

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

$1 \le k \le n \le 10^5$

سپس در هر کدام از $n-1$ خط بعدی دو عدد $u$ و $v$ آمده است که نشان دهنده وجود خیابان بین دو میدان $u$ و $v$ است.

تضمین می‌شود گراف میدان‌ها و خیابان‌های بینشان یک درخت است. میدان k حداقل 2 همسایه دارد و برگ نیست.

خروجی🔗

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

مثال🔗

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