بعد از دیدن فیلم ماداگاسکار، علیجان عاشق شخصیت گورخر شد و تحقیقات خودش را روی این گونه از جانوران آغاز کرد. او جدیدا متوجه شده در یکی از پارکهای ملی، گورخری وجود دارد که رنگ بدن او بسیار جالب است.
علیجان بدن گورخر را به یک گراف بدونجهت و همبند شبیهسازی کرد که هر راس آن سیاه یا سفید است. گورخر این قابلیت را دارد که یکی از رئوسش مانند را انتخاب کنیم و رنگ تمام رئوس مولفه همبندی همرنگ با عوض شود. به بیانی دیگر، رنگ راس عوض میشود اگر مسیری از به وجود داشته باشد که تمام رئوس آن همرنگ هستند.
علیجان عاشق گورخرها است و دوست ندارد که تمام رئوس مربوط به بدن گورخر همرنگ شود. برای اینکه بتواند از گورخر محافظت کند، نیاز دارد تا کمترین عملیات ممکن برای همرنگ شدن تمامی رئوس را پیدا کند. به او در پیدا کردن این مقدار کمک کنید.
برای درک بهتر سوال، به توضیحات نمونههای ورودی توجه کنید.
در خط اول ورودی دو عدد طبیعی تعداد رئوس و عداد یالها بهترتیب میآیند.
در خط دوم ورودی بهترتیب میآیند. مربوط به رنگ راس ام میباشد. مقدار بیانگر رنگ سفید و مقدار بیانگر راس سیاه است. در هر یک از خط بعدی، دو سر هر یال و میآید.
در تنها خط خروجی، کمترین عملیات ممکن برای اینکه گورخر تکرنگ شود را چاپ کنید.
زیرمسئله | نمره | محدودیت |
---|---|---|
۱ | ۱۰ | |
۲ | ۱۰ | و به ازای هر یک یال بین رئوس و وجود دارد. |
۳ | ۴۰ | |
۴ | ۴۰ | بدون محدودیت اضافی |
علیجان میتواند در دو مرحله با انتخاب رئوس ۴ و ۱ همه رئوس گراف را سفید کند.
اگر جایگشتی از اعداد تا باشد، سیانهی آن را دنبالهی تعریف میکنیم که در این دنباله برابر با میانهی میباشد.
برای مثال سیانهی دنبالهی برابر با است.
باقیماندهی تعداد سیانههای متفاوت بین تمام جایگشتهای اعداد تا بر را پیدا کنید.
در خط اول ورودی عدد طبیعی میآید.
در تنها خط خروجی باقیمانده تقسیم تعداد سیانههای متفاوت را بر خروجی دهید.
زیرمسئله | نمره | محدودیت |
---|---|---|
۱ | ۴ | |
۲ | ۱۶ | |
۳ | ۳۱ | |
۴ | ۴۹ | بدون محدودیت اضافی |
در این نمونه، سیانههایی که ساخته می شود این دنبالهها میباشد: , , , , , , ,
جمشید از جایگشتها بدش میآید و یک جایگشت به طول دارد که میخواهد طی تعدادی مرحله آن را پاک کند.
جمشید در هر مرحله میتواند یکی از اعداد جایگشت مانند که هنوز پاک نشده را انتخاب و خود آن عدد و تمام اعداد کوچکتر سمت راست و یا تمام اعداد کوچکتر سمت چپ آن عدد را پاک کند. با انجام این کار جمشید به میزان خسته میشود. دقت کنید که اعدادی که پاک نشدهاند به یکدیگر میچسبند.
برای مثال اگر در جایگشت با دنباله عدد را انتخاب کنیم و تمام اعداد کوچکتر سمت راست آن را پاک کنیم، به جایگشت با دنباله میرسیم.
جمشید میخواهد پس از پاک کردن جایگشت فوتبال بازی کند پس میخواهد با کمترین میزان خستگی ممکن کل جایگشت را پاک کند.
مقدارهای در جایگشت جمشید بار تغییر میکنند و در هر بار تغییر یکی از مقادیر عوض میشود.
به جمشید کمک کنید تا کمترین میزان خستگی ممکن برای حذف کل جایگشت قبل از تمام تغییرات و پس از هر تغییر را محاسبه کند.
در خط اول ورودی دو عدد طبیعی و بهترتیب میآیند. در خط دوم ورودی عدد میآید که به ترتیب مقادیر را مشخص میکنند.
در خط سوم ورودی عدد میآید که به ترتیب مقادیر اولیه را مشخص میکنند.
در خط بعدی در هر خط دو عدد و می آیند که تغییر ام را نشان میدهند و باید تغییر باید صورت بگیرد.
در خط ، در خط اول کمترین میزان خستگی جمشید برای پاک کردن جایگشت قبل از اعمال تغییرات و به ترتیب در خط ام ، کمترین میزان خستگی جمشید برای پاک کردن جایگشت پس از اعمال تغییر اول را خروجی دهید.
زیرمسئله | نمره | محدودیت |
---|---|---|
۱ | ۵ | و |
۲ | ۱۰ | و |
۳ | ۲۵ | |
۴ | ۲۵ | و |
۵ | ۳۵ | بدون محدودیت اضافی |
در این مثال قبل از تغییرات کافی است عدد و اعداد کوچکتر سمت چپ آن را پاک کنیم و به مقدار واحد خسته میشویم و سپس تنها عدد باقیمانده عدد است که آن را حذف میکنیم و به مقدار خسته میشویم که در کل واحد خسته میشویم.
پس از تغییر ابتدا عدد و اعداد کوچکتر چپ آن را حذف میکنیم و سپس عدد و اعداد کوچکتر سمت راست آن که در انتها کل جایگشت حذف میشود و میزان کل خستگی خواهد بود.