পাইথনে যেকোনো শহর এবং স্টেশনের মধ্যে সর্বোচ্চ দূরত্ব খুঁজুন

ধরুন আমাদের কাছে N নম্বর শহর আছে, এবং সেগুলিকে 0 থেকে N-1 পর্যন্ত নম্বর দেওয়া হয়েছে এবং আমাদের কাছে সেই শহরগুলিও রয়েছে যেখানে স্টেশনগুলি অবস্থিত, আমাদের যে কোনওটির মধ্যে সর্বাধিক দূরত্ব খুঁজে বের করতে হবে শহর এবং তার নিকটতম স্টেশন। আমাদের মনে রাখতে হবে যে স্টেশন সহ শহরগুলি যে কোনও ক্রমে দেওয়া যেতে পারে।

সুতরাং, যদি ইনপুট হয় N =6 এবং স্টেশনগুলি =[2,4], তাহলে আউটপুট হবে 2

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• station_present :=N আকারের একটি তালিকা, এবং False দিয়ে পূরণ করুন

• স্টেশনে প্রতিটি শহরের জন্য, করুন

  • স্টেশন_বর্তমান [শহর] :=সত্য

• dist :=0, সর্বাধিক_dist :=ন্যূনতম স্টেশন

• 0 থেকে N রেঞ্জের শহরের জন্য, করুন

  • যদি station_present[শহর] সত্য হয়, তাহলে

    • Max_dist :=সর্বাধিক (dist + 1) / 2, সর্বাধিক_dist

    • dist :=0

  • অন্যথায়,

    • dist :=dist + 1

• সর্বাধিক_dist, dist

  -এর সর্বোচ্চ রিটার্ন করুন

উদাহরণ (পাইথন)

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

def get_max_dist(N, station):
   station_present = [False] * N
   for city in station:
      station_present[city] = True
   dist, maximum_dist = 0, min(station)
   for city in range(N):
      if station_present[city] == True:
         maximum_dist = max((dist + 1) // 2, maximum_dist)
         dist = 0
      else:
         dist += 1
   return max(maximum_dist, dist)
N = 6
station = [2, 4]
print(get_max_dist(N, station))

ইনপুট

6, [2,4]

আউটপুট

2