- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
حنا قهرمان مسابقات هندونهخوری شده و مقدار زیادی پول جایزه گرفته است. حال حنا میخواهد به خانهاش برگردد و با پول مسابقات مهمانی بگیرد.
شهر محل زندگی حنا، یک خیابان با $n$ خانه است که حنا در خانهی $s$ام زندگی میکند و مسابقات هندونهخوری در خانه $t$ ام برگزار میشود. او میداند در تعدادی از خانهها زورگیر زندگی میکند و اگر از آنها رد شود، زورگیر پول حنا را از او میگیرند و حنا نمیتواند مهمانی بگیرد.
حنا از پلیس کمک میخواهد. پلیسها در روز برنامهنویس میتوانند در هر عملیات، یک بازه به طول $2^k$ ($k$ یک عدد حسابی است) را که همه اعضای آن زورگیر هستند را انتخاب کنند و آن خانهها را پاکسازی کنند.
پلیسها وقت زیادی ندارند. برای همین از شما میخواهند کمترین تعداد عملیات برای پاکسازی مسیر بین حنا و مسابقه هندونهخوری را بگویید.
ورودی
در سطر اول عدد $n$ آمده که نشاندهندهی طول خیابان است.
در سطر دوم یک رشته به طول $n$ آمدهاست. خانههایی که در آن زورگیر وجود دارد حرف H
و بقیه خانهها حرف P
هستند. تضمین میشود که در خانههای $s$ و $t$ زورگیر وجود ندارد.
در سطر سوم $s$ و $t$ به ترتیب آمدهاند. $$ 1 \leq n \leq 1\ 000 $$ $$ 1 \leq s, t \leq n $$
خروجی
در تنها سطر خروجی، کمترین تعداد عملیات برای پاکسازی مسیر حنا از زورگیرها را بگویید.
مثال
ورودی نمونه ۱
3
PHP
1 3
خروجی نمونه ۱
1
در مسیر خانه اول به سوم، تنها در خانه دوم زورگیر وجود دارد که پلیسها طی یک مرحله او را دستگیر میکنند.
ورودی نمونه ۲
9
HPPHHPHPH
8 3
خروجی نمونه ۲
2
در مسیر خانه هشتم به سوم تنها در خانههای ۴ و ۵ و ۷ زورگیر وجود دارد که پلیسها طی یک مرحله زورگیر خانهی ۴ و ۵ و در مرحلهی بعد زورگیر خانهی ۷ را دستگیر میکنند. در حرکت اول یک بازه به طول ۲ و در حرکت دوم یک بازه به طول ۱ پاکسازی شد که طول هر دو بازه توانی از ۲ بود.
ارسال پاسخ برای این سؤال