สมมติว่าเรามีเด็ก n คนยืนเป็นวงกลม และพวกเขากำลังรอบอลลูน การกระจายจะดำเนินการโดยเริ่มจากลูกที่ k (อันดับแรกที่ดัชนี 0) และให้บอลลูนที่พวกเขาออกจากวงกลม ตอนนี้เด็กทุกคนที่ k จะได้รับบอลลูนตามเข็มนาฬิกาจนเหลือเด็กเพียงคนเดียวที่ได้รับบอลลูน ดังนั้นถ้าเรามี n และ k เราต้องหาดัชนีเริ่มต้นของเด็กที่ได้รับบอลลูนสุดท้าย
ดังนั้น ถ้าอินพุตเป็น n =3 k =2 ผลลัพธ์จะเป็น 1 ในรอบแรก เด็ก 2 ได้บอลลูนแล้วปล่อยวงกลมจะเป็น [0, 1] รอบที่ 2 ลูก 0 ได้ลูกโป่ง วงกลมจะเป็น [1]
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้:
-
arr :=รายการใหม่จากช่วง 0 ถึง n
-
init :=0
-
ในขณะที่ขนาดของ arr> 1 ทำ
-
ลบ :=(init + k) ขนาด mod ของ arr
-
ลบ arr[ลบ]
-
init :=ลบ
-
-
กลับ arr[0]
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น:
ตัวอย่าง
class Solution: def solve(self, n, k): arr = list(range(0, n)) init = 0 while len(arr) > 1: remove = (init + k) % len(arr) del arr[remove] init = remove return arr[0] ob = Solution() n = 3 k = 2 print(ob.solve(n, k))
อินพุต
3,2
ผลลัพธ์
1
