পাইথনে স্টার্ট থেকে ডেস্টিনেশন পর্যন্ত যাওয়ার জন্য লেক্সিকোগ্রাফিক্যালি সবচেয়ে ছোট স্ট্রিং খুঁজে বের করার প্রোগ্রাম

কার্টেসিয়ান প্লেনে (0, 0) পজিশন থেকে (x, y) পয়েন্টে শুধুমাত্র হরিজন্টাল (H) এবং ভার্টিক্যাল (V) মuvements ব্যবহার করে যেতে হবে, প্রতিটি মuvements একক ইউনিটের। ডেস্টিনেশনে পৌঁছানোর একাধিক সম্ভাব্য পথ রয়েছে। প্রতিটি পথে কিছু H এবং কিছু V মuvements থাকে। (উদাহরণস্বরূপ, (0,0) থেকে (2,2) পয়েন্টে যেতে হলে HVVH সম্ভাব্য পথों में से একটি।) যদি আমাদের একটি k মান থাকে, তবে ডেস্টিনেশনে যাওয়ার লেক্সিকোগ্রাফিক্যালি k-তম সবচেয়ে ছোট পথটি খুঁজে বের করতে হবে।

উদাহরণ

ইনপুট: (x, y) = (3, 3), k = 3

আউটপুট: "HHVVVH"

সমাধান পদ্ধতি

1. paths() ফাংশন ডিফাইন করুন যা x, y প্যারামিটার নেয়।
2. যদি min(x, y) < 0 হয়, তবে 0 রিটার্ন করুন।
3. অন্যথায় factorial(x+y) / factorial(x) / factorial(y) রিটার্ন করুন।
4. মূল মেথড থেকে:
   • res নামে একটি খালি লিস্ট তৈরি করুন।
   • (p, q) := (0, 0) সেট করুন।
   • while (p, q) != (x, y) লুপ চালান:
     • n := paths(x - p - 1, y - q) হিসাব করুন।
     • যদি p + 1 <= x এবং k < n হয়, তবে:
       • res-এর শেষে 'H' যোগ করুন।
       • p := p + 1 করুন।
     • অন্যথায়:
       • k := k - n করুন।
       • res-এর শেষে 'V' যোগ করুন।
       • q := q + 1 করুন।
   • res-এর ক্যারেক্টারগুলো জয়েন করে রিটার্ন করুন।

পাইথন ইমপ্লিমেন্টেশন

from math import factorial

def paths(x, y):
    if min(x, y) < 0:
        return 0
    return factorial(x + y) // factorial(x) // factorial(y)

def solve(x, y, k):
    res = []
    p, q = 0, 0
    while (p, q) != (x, y):
        n = paths(x - p - 1, y - q)
        if p + 1 <= x and k < n:
            res.append('H')
            p += 1
        else:
            k -= n
            res.append('V')
            q += 1
    return ''.join(res)

# টেস্ট
x, y = 3, 3
k = 3
print(solve(x, y, k))  # আউটপুট: HHVVVH

ইনপুট

(3, 3), 3

আউটপুট

HHVVVH