पायथन में दिए गए बॉल पर कब्जा करने वाले बॉक्स की स्थिति खोजें

मान लीजिए हमारे पास दो ऐरे A और B हैं। A का आकार पंक्तियों की संख्या है और A[i] आईवीं पंक्ति में बॉक्स की संख्या है। और B गेंदों का ऐरे है जहां B[i] गेंद पर एक संख्या दर्शाता है। दिया गया है कि गेंद i (मान B[i]) को उस बॉक्स में रखा जाएगा जिसकी शुरुआत से स्थिति B[i] है। हमें प्रत्येक B[i] के अनुरूप बॉक्स की पंक्ति और स्तंभ ढूंढनी है।

इसलिए, यदि इनपुट A = [3, 4, 5, 6], B = [1, 3, 5, 2] है, तो आउटपुट [(1, 1), (1, 3), (2, 2), (1, 2)] होगा क्योंकि:

• B[0] = 1, तो बॉक्स स्थिति पहली पंक्ति, पहला स्तंभ होगी।
• B[1] = 3, तो बॉक्स स्थिति पहली पंक्ति, तीसरा स्तंभ होगी।
• B[2] = 5, तो बॉक्स स्थिति दूसरी पंक्ति, दूसरा स्तंभ होगी।
• B[3] = 2, तो बॉक्स स्थिति पहली पंक्ति, दूसरा स्तंभ होगी।

समाधान दृष्टिकोण

इसे हल करने के लिए हम निम्न चरणों का पालन करेंगे:

• len_a := len(A)
• len_b := len(B)
• i को 1 से len_a-1 तक: A[i] := A[i] + A[i-1] (प्रीफिक्स योग)
• i को 0 से len_b-1 तक के लिए:
  • row := bisect_left(A, B[i]) (वह सूचकांक जहां B[i] डाला जा सकता है ताकि A सॉर्टेड रहे)
  • यदि row >= 1, तो box_num := B[i] - A[row - 1]
  • अन्यथा, box_num := B[i]
  • युग्म (row + 1, box_num) प्रदर्शित करें।

उदाहरण

बेहतर समझ के लिए निम्न कार्यान्वयन देखें:

import bisect

def get_position(A, B):
    len_a = len(A)
    len_b = len(B)
    for i in range(1, len_a):
        A[i] += A[i - 1]
    for i in range(len_b):
        row = bisect.bisect_left(A, B[i])
        if row >= 1:
            box_num = B[i] - A[row - 1]
        else:
            box_num = B[i]
        print((row + 1, box_num))

A = [3, 4, 5, 6]
B = [1, 3, 5, 2]
get_position(A, B)

इनपुट

[3, 4, 5, 6], [1, 3, 5, 2]

आउटपुट

(1, 1) (1, 3) (2, 2) (1, 2)