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

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

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

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

دیجیکالا در پروموشن نوروز خودش یک تخفیف ویژه برای برنامه‌نویسان در نظر گرفته است. کاربران با وارد شدن به صفحه‌ی این پروموشن، لیستی از کالاها و تخفیف‌های عمومی را می‌بینند، اما دیجی‌کالا اعلام کرده است که هرکسی که بتواند به ازای هر سریالی که در این لیست هست، کوچیک‌ترین سریال بزرگتر با کاراکترهای همون سریال را پیدا کند، می‌تواند یک تخفیف 90٪ی روی تمام محصولات بگیرد. سریال‌های کالاهای دیجی‌کالا رشته‌هایی از حروف انگلیسی a-z (همه‌ی حروف کوچک) هستند و برای مقایسه‌ی کوچیک‌تر/بزرگ‌تر آن‌ها از ترتیب حروف الفبا استفاده می‌شود. برای مثال کلمه‌ی ba از کلمه‌ی ab بزرگ‌تر است و کلمه‌ی zas از کلمه‌ی zsa کوچک‌تر است.

ورودی

در خط اول ورودی n که تعداد سریال‌های پروموشون هست و در n خط بعدی در هر خط w به عنوان یک سریال داده می‌شوند.

خروجی

خروجی شامل n خط است که در هر خط در صورتی که رشته‌ی مورد نظر وجود دارد، رشته‌ و در غیر این صورت عبارت ‍no answer چاپ می‌شود.

مثال

ورودی نمونه 1

4
acs
lgeuvf
dqwrmse
zwsked

خروجی نمونه 1

asc
lgevfu
dqwrsem
no answer

در این نمونه، ترکیب بعد از acs برابر asc است. تنها با جابجایی همین دو حرف کلمه‌ی بعدی تشکیل می‌شود. در کلمه‌ی lgeuvf تنها با تبدیل uvf به vfu، رشته‌ی بعدی به دست می‌آید. در کلمه‌ی zwsked، چون حروف به صورت کامل‍ا نزولی مرتب شده‌اند، ترکیب کلمات در بزرگ‌ترین حالت خود قرار دارد.

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

def reverse(str, l, r):
    while l < r:
        str[l], str[r] = str[r], str[l]
        l += 1
        r -= 1

def binarySearch(str, l, r, val):
    index = -1
    while l <= r:
        mid = (l + r) // 2
        if str[mid] <= val:
            r = mid - 1
        else:
            l = mid + 1
            if index == -1 or str[index] >= str[mid]:
                index = mid
    return index

def nextPermutation(str):
    length = len(str)
    i = length - 2

    while i >= 0 and str[i] >= str[i + 1]:
        i -= 1

    if i < 0:
        return False
    else:
        index = binarySearch(str, i + 1, length - 1, str[i])
        str[i], str[index] = str[index], str[i]
        reverse(str, i + 1, length - 1)
        return True

def main():
    n = int(input())
    v = [input().strip() for _ in range(n)]

    for i in range(n):
        str_list = list(v[i])
        if not nextPermutation(str_list):
            print("no answer")
        else:
            print("".join(str_list))

if __name__ == "__main__":
    main()

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

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