چرخونه (گاوصندوق چرخان)

⏱️ محدودیت زمان

۲ ثانیه

💾 محدودیت حافظه

۲۵۶ مگابایت

فرض کنید یک گاوصندوق با k قفل چرخان دارید که روی هر کدام از آن‌ها، ترتیبی متفاوت از اعداد ۱ تا ۹ قرار دارد. زیر هر قفل، یک نشانگر وجود دارد که به یکی از اعداد آن قفل اشاره می‌کند. با چرخاندن قفل، عدد نشانگر تغییر می‌کند. حال، یک رمز kرقمی به شما داده می‌شود و وظیفه‌ی شما این است که حداقل تعداد چرخش‌های لازم برای باز کردن گاوصندوق را با توجه به رمز داده‌شده، محاسبه کنید.

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

📥 ورودی

• در خط اول، عدد k آمده‌است.
• در خط دوم، رمز گاوصندوق آمده‌است که یک رشته‌ی kرقمی متشکل از ارقام ۱ تا ۹ است.
• در هر خط iـُم از k خط بعدی، ترتیب ارقام روی قفل چرخان iـُم به ترتیب ساعت‌گرد آمده است. اولین رقم هر خط، رقمی است که نشانگرِ آن قفل چرخان به آن اشاره می‌کند.

1 ≤ k ≤ 300``000

📤 خروجی

حداقل تعداد چرخاندن قفل‌های چرخان را برای این که ارقامی که در هر قفل چرخان به آن‌ها اشاره شده، برابر با ارقام رمز باشد، چاپ کنید.

🎯 نمونه

ورودی نمونه

3
123
241356789
987546231
956874231

خروجی نمونه

7

• ۲ بار چرخاندن قفل چرخان اول در جهت پادساعتگرد برای رسیدن به رقم ۱
• ۳ بار چرخاندن قفل چرخان دوم در جهت ساعتگرد برای رسیدن به رقم ۲
• ۲ بار چرخاندن قفل چرخان سوم در جهت ساعتگرد برای رسیدن به رقم ۳

مجموع: ۲ + ۳ + ۲ = ۷

💡 چالش‌های حل تمرین

چگونه رقم iـُم رمز را در قفل چرخان iـُم پیدا کنم؟

با استفاده از تابع find() می‌توانید اندیس یک کاراکتر را در یک رشته پیدا کنید.

password = input()
for i in range(k):
    roller = input()
    ind = roller.find(password[i])

چرا خطای محدودیت زمان (Time Limit) دریافت می‌کنم؟

تست‌کیس‌های این تمرین، حجم زیادی دارند (عدد k بزرگ بوده و تعداد چرخانه‌ها زیاد است). برای آن‌که تست‌ها در زمان بهینه‌ای اجرا شوند، باید تعداد حلقه‌های for را در کد خود کاهش دهید تا زمان اجرای کد کاهش یابد.

💡 راهنمایی نهایی

برای پیدا کردن حداقل تعداد چرخش‌ها:

• اندیس رقم فعلی (نشانگر) را پیدا کنید → current_idx
• اندیس رقم هدف (رمز) را پیدا کنید → target_idx
• فاصله‌ی ساعتگرد = (target_idx - current_idx) % 9
• فاصله‌ی پادساعتگرد = 9 - (target_idx - current_idx) % 9
• حداقل = min(فاصله‌ی ساعتگرد, فاصله‌ی پادساعتگرد)

import sys

k = int(input())
password = input().strip()
total = 0

for i in range(k):
    roller = sys.stdin.readline().strip()
    current_idx = 0  # اولین رقم، رقم فعلی است
    target_idx = roller.find(password[i])
    clockwise = (target_idx - current_idx) % 9
    counter_clockwise = 9 - clockwise
    if clockwise < counter_clockwise:
        total += clockwise
    else:
        total += counter_clockwise

print(total)

• از sys.stdin.readline() به‌جای input() برای سرعت بیشتر استفاده کنید.
• از find() به‌جای in برای پیدا کردن اندیس استفاده کنید.
• از min() برای محاسبه‌ی حداقل استفاده کنید.
• به‌جای % می‌توانید از محاسبه‌ی مستقیم استفاده کنید.

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