گورخر


  • محدودیت زمان: ۱ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت
  • آزمون عملی اول فاینال سی و دومین دوره المپیاد کامپیوتر ایران

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

علی‌جان بدن گورخر را به یک گراف بدون‌جهت و همبند شبیه‌سازی کرد که هر راس آن سیاه یا سفید است. گورخر این قابلیت را دارد که یکی از رئوسش مانند vv را انتخاب کنیم و رنگ تمام رئوس مولفه همبندی همرنگ با vv عوض شود. به بیانی دیگر، رنگ راس uu عوض می‌شود اگر مسیری از vv به uu وجود داشته باشد که تمام رئوس آن همرنگ هستند.

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

برای درک بهتر سوال، به توضیحات نمونه‌های ورودی توجه کنید.

ورودی🔗

در خط اول ورودی دو عدد طبیعی nn تعداد رئوس و mm عداد یال‌ها به‌ترتیب می‌آیند.

1n20001 \leq n \leq 2000 1m50001 \leq m \leq 5000

در خط دوم ورودی c1,c2,cnc_1, c_2, \cdots c_n به‌ترتیب می‌آیند. cic_i مربوط به رنگ راس ii ام می‌باشد. مقدار 00 بیانگر رنگ سفید و مقدار 11 بیانگر راس سیاه است. 0ci10 \leq c_i \leq 1 در هر یک از mm خط بعدی، دو سر هر یال viv_i و uiu_i می‌آید. 1vi,uin1 \leq v_i, u_i \leq n

خروجی🔗

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

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

زیرمسئله نمره محدودیت
۱ ۱۰ n20n \le 20
۲ ۱۰ m=n1m = n-1 و به ازای هر 1in11 \leq i \leq n - 1 یک یال بین رئوس ii و i+1i+1 وجود دارد.
۳ ۴۰ m=n1m = n-1
۴ ۴۰ بدون محدودیت اضافی

مثال🔗

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

7 8
1 0 0 1 1 0 1
1 2
1 3
2 4
3 4
4 5
4 6
5 7
6 7
Plain text

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

2
Plain text

علی‌جان می‌تواند در دو مرحله با انتخاب رئوس ۴ و ۱ همه رئوس گراف را سفید کند.

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

9 8
1 0 1 0 1 0 1 0 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
Plain text

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

4
Plain text

سیانه


  • محدودیت زمان: ۱ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت
  • آزمون عملی اول فاینال سی و دومین دوره المپیاد کامپیوتر ایران

اگر p=p1,p2,,p3np = \langle p_1, p_2, \cdots, p_{3n} \rangle جایگشتی از اعداد 11 تا 3n3n باشد، سیانه‌ی آن را دنباله‌ی q=q1,q2,,qnq = \langle q_1, q_2, \cdots, q_n \rangle تعریف می‌کنیم که qiq_i در این دنباله برابر با میانه‌ی p3i2,p3i1,p3i\langle p_{3i - 2}, p_{3i - 1}, p_{3i} \rangle می‌باشد.

برای مثال سیانه‌ی دنباله‌ی p=4,8,9,7,1,3,2,6,5p = \langle 4, 8, 9, 7, 1, 3, 2, 6, 5 \rangle برابر با q=8,3,5q = \langle 8, 3, 5 \rangle است.

باقی‌مانده‌ی تعداد سیانه‌های متفاوت بین تمام جایگشت‌های اعداد 11 تا 3n3n بر 109+710^9+7 را پیدا کنید.

ورودی🔗

در خط اول ورودی عدد طبیعی nn می‌آید. 1n1061 \le n \le 10^6

خروجی🔗

در تنها خط خروجی باقی‌مانده تقسیم تعداد سیانه‌های متفاوت را بر 109+710^9+7 خروجی دهید.

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

زیرمسئله نمره محدودیت
۱ ۴ n4n \le 4
۲ ۱۶ n300n \le 300
۳ ۳۱ n3000n \le 3000
۴ ۴۹ بدون محدودیت اضافی

مثال🔗

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

1
Plain text

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

1
Plain text

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

2
Plain text

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

8
Plain text

در این نمونه، سیانه‌هایی که ساخته می شود این دنباله‌ها می‌باشد: 2,4\langle 2, 4 \rangle, 2,5\langle 2, 5 \rangle, 3,4\langle 3, 4 \rangle, 3,5\langle 3, 5 \rangle, 4,2\langle 4, 2 \rangle, 5,2\langle 5, 2 \rangle, 4,3\langle 4, 3 \rangle, 5,3\langle 5, 3 \rangle

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

7
Plain text

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

141629040
Plain text

دلاکس


  • محدودیت زمان: ۱.۵ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت
  • آزمون عملی اول فاینال سی و دومین دوره المپیاد کامپیوتر ایران

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

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

برای مثال اگر در جایگشت p=1,3,4,2,5p = \langle 1, 3, 4, 2, 5 \rangle با دنباله b=1,2,3,4,5b = \langle 1, 2, 3, 4, 5 \rangle عدد p2=3p_2 = 3 را انتخاب کنیم و تمام اعداد کوچکتر سمت راست آن را پاک کنیم، به جایگشت p=1,4,5p = \langle 1, 4, 5 \rangle با دنباله b=1,3,5b = \langle 1, 3, 5 \rangle می‌رسیم.

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

مقدارهای bib_i در جایگشت جمشید qq بار تغییر می‌کنند و در هر بار تغییر یکی از مقادیر bib_i عوض می‌شود.

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

ورودی🔗

در خط اول ورودی دو عدد طبیعی nn و qq به‌ترتیب می‌آیند. 1n3×1051 \leq n \leq 3 \times 10^5 0q3×1050 \leq q \leq 3 \times 10^5 در خط دوم ورودی nn عدد می‌آید که به ترتیب مقادیر pip_i را مشخص می‌کنند.

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

در qq خط بعدی در هر خط دو عدد xix_i و ‌ yiy_i می آیند که تغییر ii ام را نشان می‌دهند و باید تغییر bxi=yib_{x_i} = y_i باید صورت بگیرد. 1pi,xin1 \leq p_i , x_i \leq n 1bi,yi1091 \leq b_i , y_i \leq 10^9

خروجی🔗

در q+1q+1 خط ، در خط اول کمترین میزان خستگی جمشید برای پاک کردن جایگشت قبل از اعمال تغییرات و به ترتیب در خط i+1i+1 ام ، کمترین میزان خستگی جمشید برای پاک کردن جایگشت پس از اعمال ii تغییر اول را خروجی دهید.

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

زیرمسئله نمره محدودیت
۱ ۵ bi=1b_i=1 و q=0q=0
۲ ۱۰ q=0q=0 و n=20n=20
۳ ۲۵ q=0q=0
۴ ۲۵ 1bi101 \le b_i \le 10 و 1yi101 \le y_i \le 10
۵ ۳۵ بدون محدودیت اضافی

مثال🔗

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

4 1
1 2 4 3
2 5 3 4
2 3
Plain text

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

7
6
Plain text

در این مثال قبل از تغییرات کافی است عدد 33 و اعداد کوچکتر سمت چپ آن را پاک کنیم و به مقدار 44 واحد خسته می‌شویم و سپس تنها عدد باقی‌مانده عدد 44 است که آن را حذف می‌کنیم و به مقدار 33 خسته می‌شویم که در کل 77 واحد خسته می‌شویم.

پس از تغییر b2=3b_2 = 3 ابتدا عدد 22 و اعداد کوچکتر چپ آن را حذف می‌کنیم و سپس عدد 44 و اعداد کوچکتر سمت راست آن که در انتها کل جایگشت حذف می‌شود و میزان کل خستگی 66 خواهد بود.

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

5 2
4 5 1 3 2
6 8 1 3 2
1 3
4 1
Plain text

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

12
11
10
Plain text