โจทย์
มีคลาส TestArray ที่มี Private Array (ค่า 0 หรือ 1 เท่านั้น) และ Public Methods สองตัว:
length()- คืนความยาวอาร์เรย์query(p, q, r, s)- เปรียบเทียบค่าที่ดัชนี 4 ตัว คืนค่า:- 4: ทั้ง 4 ตัวเหมือนกัน (0 หรือ 1)
- 2: 3 ตัวเหมือน 1 ตัวต่าง
- 0: 2 ตัวเป็น 0 และ 2 ตัวเป็น 1
ต้องหา Index ของค่าที่พบมากที่สุด (0 หรือ 1) โดยใช้เฉพาะ Methods นี้ ถ้าเท่ากันคืน -1
อัลกอริธึม
- ใช้
query(0,1,2,3)และquery(0,1,2,4)เป็น Baseline - จัดกลุ่ม Index เป็น Group A (ค่าเดียวกับ Baseline) และ Group B (ค่าต่าง)
- นับจำนวนในแต่ละกลุ่ม คืน Index ของกลุ่มที่มากกว่า
โค้ด Python
class TestArray:
def __init__(self, array) -> None:
self.__arr = array
def length(self):
return len(self.__arr)
def query(self, p, q, r, s):
val = self.__arr[p] + self.__arr[q] + self.__arr[r] + self.__arr[s]
if val == 4 or val == 0:
return 4
elif val == 1 or val == 3:
return 2
elif val == 2:
return 0
def solve(reader):
n, groupA, groupB, aIdx, bIdx = reader.length(), 1, 0, None, None
first, second = reader.query(0,1,2,3), reader.query(0,1,2,4)
for i in range(4, n):
if reader.query(0,1,2,i) == first:
groupA, aIdx = groupA + 1, i
else:
groupB, bIdx = groupB + 1, i
for i in range(3):
nxt = [v for v in [0,1,2,3,4] if v != i]
if reader.query(*nxt) == second:
groupA, aIdx = groupA + 1, i
else:
groupB, bIdx = groupB + 1, i
return aIdx if groupA > groupB else bIdx if groupB > groupA else -1
arr_ob = TestArray([0, 1, 1, 0, 1, 1, 1, 0])
print(solve(arr_ob)) # Output: 2
Input / Output
Input: [0, 1, 1, 0, 1, 1, 1, 0]
Output: 2
