หาตำแหน่งกล่องที่ลูกบอลแต่ละลูกวางได้จากอาร์เรย์แถวและลำดับลูกบอลใน Python

หาแถวและคอลัมน์ของกล่องสำหรับแต่ละลูกบอล

กำหนดอาร์เรย์ A ขนาด = จำนวนแถว A[i] = จำนวนกล่องในแถว i, อาร์เรย์ B = หมายเลขลูกบอล (ลำดับการวางตั้งแต่ 1) หาตำแหน่ง (แถว, คอลัมน์) ของแต่ละลูกบอล

ตัวอย่าง: A=[3,4,5,6], B=[1,3,5,2] → [(1,1),(1,3),(2,2),(1,2)]

วิธีแก้

1. คำนวณ Prefix Sum ของ A → A[i] = จำนวนกล่องสะสมถึงแถว i
2. สำหรับแต่ละ B[i] หา row = bisect_left(A, B[i]) (แถวแรกที่มีกล่องสะสม ≥ B[i])
3. col = B[i] - A[row-1] (ถ้า row>0) มิฉะนั้น col = B[i]

โค้ดตัวอย่าง Python

import bisect

def get_position(A, B):
    for i in range(1, len(A)):
        A[i] += A[i-1]  # prefix sum
    for ball in B:
        row = bisect.bisect_left(A, ball)
        col = ball - (A[row-1] if row > 0 else 0)
        print((row+1, col))

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