Tìm vị trí hộp chứa quả bóng cho trước trong Python

Cho hai mảng A và B. Kích thước A là số hàng, A[i] là số hộp ở hàng thứ i. B là mảng các quả bóng, B[i] là số thứ tự của quả bóng. Quả bóng i (giá trị B[i]) sẽ được đặt vào hộp có vị trí từ đầu là B[i]. Ta cần tìm hàng và cột của hộp tương ứng với mỗi B[i].

Ví dụ, A = [3, 4, 5, 6], B = [1, 3, 5, 2], kết quả: [(1,1), (1,3), (2,2), (1,2)].

Thuật toán giải quyết

• Tính mảng tiền tố của A: A[i] += A[i-1].
• Với mỗi B[i]:
  • Dùng bisect_left tìm chỉ số row trong mảng tiền tố.
  • Nếu row >= 1: box_num = B[i] - A[row-1].
  • Ngược lại: box_num = B[i].
  • Trả về cặp (row + 1, box_num).

Ví dụ minh họa

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)
# Output: (1, 1) (1, 3) (2, 2) (1, 2)

Đầu vào

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

Đầu ra

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