โปรแกรมหาคะแนนสูงสุดจากการลบก้อนหินใน Python

สมมติว่าเรามีสามค่า a, b และ c เรากำลังเล่นเกมโซลิแทร์ที่มีหินสามกองซึ่งมีขนาด a, b และ c ตามลำดับ แต่ละเทิร์นผู้เล่นจะเลือกกองที่ไม่ว่างเปล่าสองกอง หยิบหินหนึ่งก้อนจากแต่ละกอง และเพิ่ม 1 คะแนนให้กับคะแนนของเขา เกมจะจบลงเมื่อมีกองที่ไม่ว่างน้อยกว่าสองกอง ดังนั้นเราต้องหาคะแนนสูงสุดที่คุณจะได้รับ

ดังนั้น หากอินพุตเป็น a =4, b =4, c =6 เอาต์พุตจะเป็น 7 เนื่องจากสถานะเริ่มต้นคือ (4, 4, 6) เราสามารถทำตามขั้นตอนเหล่านี้ได้ –

• เลือกจากกองที่ 1 และ 2 เพื่อให้สถานะปัจจุบันคือ (3, 3, 6)

• เลือกจากกองที่ 1 และ 3 เพื่อให้สถานะปัจจุบันคือ (2, 3, 5)

• เลือกจากกองที่ 1 และ 3 เพื่อให้สถานะปัจจุบันคือ (1, 3, 4)

• เลือกจากกองที่ 1 และ 3 เพื่อให้สถานะปัจจุบันคือ (0, 3, 3)

• เลือกจากกองที่ 2 และ 3 เพื่อให้สถานะปัจจุบันคือ (0, 2, 2)

• เลือกจากกองที่ 2 และ 3 เพื่อให้สถานะปัจจุบันคือ (0, 1, 1)

• เลือกจากกองที่ 2 และ 3 เพื่อให้สถานะปัจจุบันคือ (0, 0, 0)

และในที่สุดก็มีกองที่ไม่ว่างน้อยกว่าสองกอง ดังนั้นเกมจะจบลง

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• ขั้นต่ำ :=ขั้นต่ำของ a, b และ c

• สูงสุด :=สูงสุดของ a, b และ c

• ซ้าย :=a + b + c - สูงสุด - ต่ำสุด

• ถ้าสูงสุด-ซ้าย <=ต่ำสุด แล้ว

  • คืนค่าต่ำสุด + ซ้าย - ผลหารของ (1 + ต่ำสุด - (ซ้ายสูงสุด))/2

• คืนค่าขั้นต่ำ + (ขั้นต่ำของ (สูงสุด-ขั้นต่ำ) และซ้าย)

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

def solve(a, b, c):
   minimum = min(a,b,c)
   maximum = max(a,b,c)
   left = a+b+c-maximum-minimum
   if maximum-left<=minimum:
      return minimum + left-(1+minimum-(maximum-left))//2
   return minimum + min(maximum-minimum,left)

a = 4
b = 4
c = 6
print(solve(a, b, c))

อินพุต

4, 4, 6

ผลลัพธ์

7