+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- فردا تولد حیدریه! حیدری دوستانش را خیلی عجیب انتخاب می‌کند به همین دلیل دوستان او یا روس هستند (`A`) یا سفید (`B`) یا سیاه (`C`). دوستان حیدری به مناسبت تولدش به خانه او آمده‌اند و خودشان به دل‌خواه دور میز دایره‌ای شکل داخل آشپزخانه نشسته‌اند. از آن‌جایی که حیدری اعتقاد دارد سیاه‌ها باید کنار هم بنشینند و هم‌چنین سفیدها هم باید کنار هم بنشینند و از همه جالب تر این‌که روس‌ها هم باید کنار هم بنشینند، به او کمک کنید که از کم‌ترین تعداد مهمان‌ها بخواهد صندلیشان را با همدیگر عوض کنند به صورتی که به اعتقادات او لطمه‌ای نخورد. (روس‌ها کنار هم، سفیدها کنار هم، و سیاه‌ها کنار هم بنشینند.) تعویض صندلی به این صورت انجام می‌شود که ابتدا همه‌ی افراد منتخب می‌ایستند، صندلی‌شان را با یکدیگر تعویض کرده، و سپس همه می‌نشینند. # ورودی در خط اول ورودی $n$ تعداد دوستان حیدری آمده است. $$1 \le n \le 100\ 000$$ سپس در خط دوم ورودی یک رشته به طول $n$ آمده است متشکل از حروف `A`، `B` و `C` که ترتیب نشستن دوستان حیدری دور میز را نشان می‌دهد. (دقت کنید که میز دایره‌ایست!) # خروجی در تنها خط خروجی کمترین تعداد نفراتی را چاپ کنید که باید از آن‌ها بخواهیم تا صندلیشان را عوض کنند. # مثال ## ورودی نمونه ۱ ``` 5 ABABC ``` ## خروجی نمونه ۱ ``` 2 ``` ## ورودی نمونه ۲ ``` 12 ABCABCABCABC ``` ## خروجی نمونه ۲ ``` 6 ``` ## ورودی نمونه ۳ ``` 4 ACBA ``` ## خروجی نمونه ۳ ``` 0 ``` ## ورودی نمونه ۴ ``` 6 BABABA ``` ## خروجی نمونه ۴ ``` 2 ``` ## ورودی نمونه ۵ ``` 9 ABABCBCAC ``` ## خروجی نمونه ۵ ``` 3 ``` ---------- <details class="orange"> <summary> راهنمایی ۱ </summary> ابتدا فرض می‌کنیم میز دایره‌ای شکل نیست و مهمان ها می‌خواهند روی یک خط کنار هم بنشینند. کافیست مسئله را برای این حالت ساده حل کنیم، و سپس برای حالت دایره‌ای روشی بیابیم. در این حالت نشستن نهایی آن ها ۳! = ۶ حالت دارد. (جایگشت های حروف $A$ و $B$ و $C$) پس همه این ۶ حالت را می‌توانیم چک کنیم و جواب بهینه را بیابیم. با داشتن یک جایگشت، با توجه به این که تعداد $A$ و $B$ و $C$ها مشخص است، دنباله‌ی نهایی مشخص خواهد بود. با داشتن دنباله‌ی اولیه و دنباله‌ی نهایی، می‌توان با مشاهده‌ی محل‌های اختلافشان، افرادی که باید جابجا شوند را مشخص کنیم. در راهنمایی بعدی روشی برای حل مسئله برای دایره ارائه می‌کنیم، بصورتی که زمان اجرایش کم بماند. </details> <details class="orange"> <summary> راهنمایی ۲ </summary> برای حل سوال در حالت دایره‌ای در هر یک از ۶ حالتی که در بالا توضیح داده شد، تعیین می‌کنیم حرفی که در اول خط آمده است از آخر خط نیز تا کجا آمده است (تفاوت حالت دایره‌ای به حالت خطی این است که ممکن است یک حرف هم اول خط بیاید هم آخر خط؛ چون در حالت دایره‌ای ابتدا و انتهای خط کنار هم قرار می‌گیرد!) حال اگر برای هر بازه تعداد حروف $A$, $B$ و $C$ را داشته باشیم زمان حل کم می‌ماند. یک بازه روی دایره را می‌توان با شکاندن دایره و تبدیل آن به خط، به یک بازه و یا اجتماع دو بازه تبدیل کرد. پس ابتدا دایره را با اعداد ۱ تا $n$ شماره‌گذاری می‌کنیم. اگر تعداد این حروف را (برای مثال $A$) برای زیر رشته ۱ تا هر $i$ در $dp[i]$ داشته باشیم تعداد این حرف در بازه $l$ تا $r$ به وضوح از رابطه زیر به دست می‌آید: ```c dp[r] - dp[l - 1] ``` روش پر کردن آرایه $dp$ هم می‌تواند به صورت زیر باشد: ```c for i in 1 -> n: dp[i] = dp[i - 1] if s[i] == 'A': dp[i] = dp[i] + 1 ``` </details>

حل سؤال در بانک سؤالات