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

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

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

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

می‌دانیم یه قل دو قل جایگاه ویژه‌ای در میان اهالی برره دارد. این بازی در برره به شکل عجیبی انجام می‌شود. بر روی یک خط n سنگ قرار می‌گیرد که روی سنگ iاُم عدد a_i​ نوشته شده و در موقعیت x_i​ قرار دارد. به ازای هر بازه‌ای از خط (بازه‌ای از xها)، تعداد اعداد متمایزی که روی سنگ‌های داخل این بازه نوشته شده‌است را درجه‌ی الدنگی آن بازه می‌نامیم. شما باید بین همه‌ی بازه‌هایی که درجه‌ی الدنگی آنها بیشینه است کوتاه‌ترین (یعنی بازه‌ای که انتها منهای ابتدایش کمینه است) آنها را پیدا کنید و طول آن را چاپ کنید.

ورودی

در خط اول n، تعداد سنگ‌ها آمده است. در هر یک از n خط بعد در خط i به ترتیب x_i​ و a_i​ آمده است. همه‌ی xi​ها متمایزند.

خروجی

طول کوتاه‌ترین بازه با درجه الدنگی بیشینه را چاپ کنید.

مثال

ورودی نمونه 1

6
25 7
26 1
15 1
22 3
20 1
30 1

خروجی نمونه 1

4

بازه‌ی 22 تا 26 (با طول 4) جواب است. درجه‌ی الدنگی این بازه 3 است و طول آن برابر 4. درجه‌ی الدنگی آن بیشینه است و طول آن بین تمام بازه‌هایی که درجه‌ی الدنگی آنها بیشینه است کمینه است.

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

import sys

x = {}
n = int(input())
for _ in range(n):
    inp = input().split(' ')
    x[int(inp[0])] = int(inp[1])

dic = sorted(x.items())
mald = len(set(x.values()))
dic2 = set()
for i in range(len(dic) - 1):
    if dic[i][1] != dic[i + 1][1]:
        dic2.add(dic[i])
        dic2.add(dic[i + 1])

dic = sorted(dic2)
le = len(dic)

minim = sys.maxsize
i = 0

while i < le:
    dic2 = set()
    if i + mald <= le:
        for j in range(i, i + mald - 1):
            dic2.add(dic[j][1])

        for j in range(i + mald - 1, le):

            dic2.add(dic[j][1])

            if len(dic2) == mald:

                minim = min([dic[j][0] - dic[i][0], minim])
                break

    if not len(dic2) == mald:
        break

    dic2 = set()

    for k in range(mald - 1):
        dic2.add(dic[j - k][1])

    for k in range(mald - 1, j - i + 1):

        dic2.add(dic[j - k][1])

        if len(dic2) == mald:

            minim = min([dic[j][0] - dic[j - k][0], minim])
            i = j - k + 1

            break

print(minim)

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

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