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

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

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

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

ویتی برای تحلیل اطلاعات مربوط به یکی از پروژه‌هایش نیاز دارد گراف زیر را بکشد: گراف ما از $n$ راس تشکیل شده است. روی هر یک از این راس‌ها یک عدد a_i​ که یک عدد حسابی کوچک‌تر مساوی 100000 است نوشته شده است. دو راس v و u به هم وصل‌اند اگر و تنها اگر اختلاف a_u ​و a_v​ دقیقا برابر 1 شود. با گرفتن اعداد روی راس‌ها به ویتی کمک کنید تا بفهمد برای کشیدن گرافش به چند یال نیاز دارد.

ورودی

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

خروجی

خروجی برنامه‌ی شما شامل یک عدد است که تعداد یال‌های لازم برای کشیدن این گراف را نشان می‌دهد.

مثال

ورودی نمونه 1

3
1 2 1

خروجی نمونه 1

2

بین راس شماره 1 و 2 و همچنین بین راس شماره ی 2 و 3 یال وجود دارد چون اختلاف عدد های روی آن ها (1 و 2) برابر 1 است.

ورودی نمونه 2

12
1 2 4 5 4 5 5 6 7 7 7 7

خروجی نمونه 2

14

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

n = int(input()) 
a = list(map(int, input().split())) 

count = {} 

for number in a: 
    if number in count: 
        count[number] += 1 
    else: 
        count[number] = 1 

edges = 0 

for key in count: 
    if key + 1 in count: 
        edges += count[key] * count[key + 1] 

print(edges)

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

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