حل تمرین پاکسازی کوئرا با پایتون

حل تمرین پاکسازی کوئرا با پایتون

در این نوشته به روش حل یکی از سوالات برنامه نویسی وب‌سایت کوئرا می‌پردازیم.

حل تمرین پاکسازی کوئرا با پایتون

حنا قهرمان مسابقات هندونه‌خوری شده و مقدار زیادی پول جایزه گرفته‌ است. حال حنا می‌خواهد به خانه‌اش برگردد و با پول مسابقات مهمانی بگیرد. شهر محل زندگی حنا، یک خیابان با n خانه است که حنا در خانه‌ی sام زندگی می‌کند و مسابقات هندونه‌خوری در خانه tام برگزار می‌شود. او می‌داند در تعدادی از خانه‌ها زورگیر زندگی می‌کند و اگر از آن‌ها رد شود، زورگیر پول حنا را از او می‌گیرند و حنا نمی‌تواند مهمانی بگیرد. حنا از پلیس کمک می‌خواهد. پلیس‌ها در روز برنامه‌نویس می‌توانند در هر عملیات، یک بازه به طول 2^k ($k$ یک عدد حسابی است) را که همه اعضای آن زورگیر هستند را انتخاب کنند و آن خانه‌ها را پاکسازی کنند. پلیس‌ها وقت زیادی ندارند. برای همین از شما می‌خواهند کمترین تعداد عملیات برای پاکسازی مسیر بین حنا و مسابقه هندونه‌خوری را بگویید.

ورودی

در سطر اول عدد n آمده که نشان‌دهنده‌ی طول خیابان است. در سطر دوم یک رشته به طول n آمده‌است. خانه‌هایی که در آن زورگیر وجود دارد حرف H و بقیه خانه‌ها حرف P هستند. تضمین می‌شود که در خانه‌های s و $t$ زورگیر وجود ندارد. در سطر سوم s و $t$ به ترتیب آمده‌اند.

خروجی

در تنها سطر خروجی، کمترین تعداد عملیات برای پاکسازی مسیر حنا از زورگیرها را بگویید.

مثال

ورودی نمونه 1

3
PHP
1 3

خروجی نمونه 1

1

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

ورودی نمونه 2

9
HPPHHPHPH
8 3

خروجی نمونه 2

2

در مسیر خانه هشتم به سوم تنها در خانه‌های 4 و 5 و 7 زورگیر وجود دارد که پلیس‌ها طی یک مرحله زورگیر خانه‌ی 4 و 5 و در مرحله‌ی بعد زورگیر خانه‌ی 7 را دستگیر می‌کنند. در حرکت اول یک بازه به طول 2 و در حرکت دوم یک بازه به طول 1 پاک‌سازی شد که طول هر دو بازه توانی از 2 بود.

کد پایتون سوال تمرین پاکسازی

n = int(input())
s = input()

path = [int(i) for i in input().split(" ")]

if path[0] == path[1]:
    print(0)

else:
    def func(zurgir, count):
        for i in range(10):
            if pow(2, i) == zurgir:
                count += 1
                return count

            elif pow(2, i) > zurgir:
                zurgir -= pow(2, i - 1)
                count += 1
                return func(zurgir, count)


    zurgir = 0
    ls = list()

    if path[1] > path[0]:
        for i in s[path[0] - 1:path[1]]:
            if i == "H":
                zurgir += 1

            elif zurgir != 0:
                ls.append(zurgir)
                zurgir = 0

    else:
        for i in s[path[1] - 1:path[0]]:
            if i == "H":
                zurgir += 1

            elif zurgir != 0:
                ls.append(zurgir)
                zurgir = 0

    ans = 0
    for i in ls:
        ans += func(i, 0)

    print(ans)

منبع سوال: کوئرا

اگر نیاز به حل تمرین‌های دیگری از کوئرا دارید در بخش نظرات همین نوشته برای ما بنویسید.