حل تمرین اکبر در درخت کبیر کوئرا با پایتون

حل تمرین اکبر در درخت کبیر کوئرا با پایتون

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

حل تمرین اکبر در درخت کبیر کوئرا با پایتون

کاراکتر “من” که دید اکبر بدون اجازه از اسمش در سوال ها استفاده کرده است، تصمیم گرفت انتقام بگیرد.

در سرزمین “اکبراینا” درختی کبیر وجود داشت، درخت کبیر درختی ریشه‌دار بی نهایت راس است که هر راس آن دارای 26 فرزند است. امیرمحمد که به نام‌گذاری رئوس درخت علاقه زیادی دارد، به هر راسی از این درخت رشته‌ای از حروف کوچک انگلیسی را متناظر کرد، می‌دانیم نام‌گذاری امیرمحمد خاصیت‌های زیر را دارد:

• به راس ریشه رشته تهی متناظر شده است.
• به هیچ دو راسی رشته یکسان متناظر نشده است.
• به ازای هر راسی به جز ریشه اگر رشته متناظر این راس s1s2s3…sk​ است، رشته متناظر پدر این راس s1s2s3…sk−1​ است.

بعد از نام‌گذاری امیرمحمد، امید به وجد آمد و رفت که از راس‌های این درخت بازدید کنه، ولی بعد از مدتی کوتاه فهمید که تو راسی به نام O با یک رشته m حرفی قرار داره و گم شده. برای همین به اکبر (مالک سرزمین و همچنین مالک درخت کبیر) زنگ زد و گفت: “اکبرر بیا منو پیدا کن گم شدم”. اکبر که در آن لحظه در راسی به نام A با n حرف قرار داشت، امید خود را از دست نداد و به سمت امید دوید، او می‌توانست در هر ثانیه از یک راس به یکی از راس‌های مجاورش برود، و چون خیلی نگران از بین رفتن امیدش بود، در کوتاه‌ترین زمان ممکن امید خود را به دست آورد. حال شما به عنوان شنونده این داستان پندآموز به ما اعلام کنید که اکبر چند ثانیه پس از حرکت، امید خود را بدست می‌آورد.

ورودی

در خط اول ورودی عدد n آمده است. در خط دوم ورودی رشته ی A دارای n حرف از حروف کوچک الفبای انگلیسی آمده است. در خط سوم ورودی عدد m آمده است. در خط چهارم ورودی رشته‌ی O دارای m حرف از حروف کوچک الفبای انگلیسی آمده است.

خروجی

در تنها خط خروجی یک عدد که نشان دهنده پاسخ مسئله است را چاپ کنید.

مثال

ورودی نمونه 1

2
ab
2
ac

خروجی نمونه 1

2

اکبر در ثانیه اول از ab به a می‌رود، و در ثانیه دوم از a به ac می‌رود و امیدش با بدست می‌آورد.

ورودی نمونه 2

3
aab
3
aba

خروجی نمونه 2

4

اکبر در ثانیه اول از aab به aa می‌رود، در ثانیه دوم از aa به a می‌رود، در ثانیه سوم از a به ab می‌رود، در ثانیه چهارم از ab به aba می‌رود و امیدش با بدست می‌آورد.

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

def longest_common_prefix_length(A, O):
    min_length = min(len(A), len(O))
    for i in range(min_length):
        if A[i] != O[i]:
            return i
    return min_length

n = int(input().strip())
A = input().strip()
m = int(input().strip())
O = input().strip()

L = longest_common_prefix_length(A, O)

moves = n + m - 2 * L

print(moves)

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

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