ধরুন আমাদের হাঁটা এবং টার্গেট নামক দুটি তালিকা আছে। শুরুতে আমরা এক-মাত্রিক লাইনে 0 অবস্থানে আছি। এখন |হাঁটে[i]| পদ হাঁটা হয়েছে সংখ্যা প্রতিনিধিত্ব করে. এবং যখন হাঁটা [i] ইতিবাচক হয় তখন ডানদিকে হাঁটা নির্দেশ করে এবং বাম দিকে নেতিবাচক হয়। আমরা যখন হাঁটছি, তখন আমরা একটি ব্লক সরাই, সেটি হল পরবর্তী বা আগের পূর্ণসংখ্যার অবস্থান। আমাদের অন্তত লক্ষ্য সংখ্যার উপর হেঁটে যাওয়া ব্লকের সংখ্যা খুঁজে বের করতে হবে।
সুতরাং, ইনপুট যদি walks =[3, -7, 2] টার্গেট =2 এর মত হয়, তাহলে আউটপুট হবে 5, নিচের চিত্র থেকে, আমরা দেখতে পাচ্ছি [0, 1], [1, 2], [2] , 3], [-4, -3], [-3, -2] আচ্ছাদিত k =2 বার।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- pos :=0
- জাম্পস :=একটি হ্যাশ ম্যাপ, যেখানে কী উপস্থিত না থাকলে ডিফল্ট মান 0 হয়
- হাঁটার প্রতিটি দূরত্বের জন্য, করুন
- জাম্প[pos] :=jumps[pos] + 1 যদি dist> 0 অন্যথায় -1
- জাম্প[pos + dist] :=jumps[pos + dist] - 1 যদি dist> 0 অন্যথায় -1
- pos :=pos + dist
- লাস্টপোস :=0
- স্তর :=0
- মোট :=0
- প্রতিটি পজিশনের জন্য, এবং বাছাই করা কী-ভ্যালু জোড়া জাম্পে মান ভ্যাল করুন, করুন
- যদি স্তর>=টার্গেট, তারপর
- মোট :=মোট + pos - লাস্টপোস
- স্তর :=স্তর + ভাল
- lastpos :=pos
- যদি স্তর>=টার্গেট, তারপর
- মোট রিটার্ন
উদাহরণ
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
from collections import defaultdict def solve(walks, target): pos = 0 jumps = defaultdict(int) for dist in walks: jumps[pos] += 1 if dist > 0 else -1 jumps[pos + dist] -= 1 if dist > 0 else -1 pos += dist lastpos = level = total = 0 for pos, val in sorted(jumps.items()): if level >= target: total += pos - lastpos level += val lastpos = pos return total walks = [3, -7, 2] target = 2 print(solve(walks, target))
ইনপুট
[3, -7, 2], 2
আউটপুট
5
