ทำให้เลข 3 ตัวเป็นศูนย์ใน C++

โจทย์

กำหนด 3 จำนวนเต็มบวก a, b, c แต่ละขั้นตอนเลือก 2 ตัวที่ผลรวม > ตัวที่เหลือ ลบ 1 จากทั้งคู่ หาจำนวนขั้นตอนน้อยที่สุดทำให้ทั้ง 3 ตัวเป็น 0

ตัวอย่าง

a=4, b=4, c=6

(4,4,6) → ลบ a,b: (3,3,6)
       → ลบ a,c: (2,3,5)
       → ลบ a,c: (1,3,4)
       → ลบ a,c: (0,3,3)
       → ลบ b,c: (0,2,2)
       → ลบ b,c: (0,1,1)
       → ลบ b,c: (0,0,0)
Steps: 7

แนวคิด: Greedy + Math

เพื่อลดขั้นตอนให้น้อยที่สุด ควรลดตัวเลขใหญ่ๆ ก่อน กลยุทธ์:

1. เรียง a ≤ b ≤ c
2. ถ้า a + b > c: ลด a,b พร้อมกันจนกว่า a=0 หรือ a+b=c
3. เหลือ 0, b', c' โดย c' = b' → ลด b',c' พร้อมกัน b' ครั้ง
4. รวม Steps = min(a, b) (จากขั้นตอน 2) + b' (จากขั้นตอน 3)

สูตรทางคณิตศาสตร์

หลังเรียง a ≤ b ≤ c:

• ถ้า a + b ≤ c: ตอบ = a + b (ลด a,b จน a=0 แล้วลด b,c)
• ถ้า a + b > c: ตอบ = (a + b + c) / 2 (Integer division)

โค้ด C++

#include <bits/stdc++.h>
using namespace std;

int maxSteps(int a, int b, int c) {
    // เรียง a ≤ b ≤ c
    if (a > b) swap(a, b);
    if (b > c) swap(b, c);
    if (a > b) swap(a, b);
    
    if (a + b <= c) {
        return a + b;
    } else {
        return (a + b + c) / 2;
    }
}

// วิธี Simulation (ช้ากว่า แต่เข้าใจง่าย)
int maxStepsSim(int a, int b, int c) {
    int steps = 0;
    while (true) {
        // เรียงใหม่ทุกรอบ
        if (a > b) swap(a, b);
        if (b > c) swap(b, c);
        if (a > b) swap(a, b);
        
        if (a == 0 && b == 0) break;
        if (a == 0) {
            // เหลือ b,c → ลดคู่กัน
            steps += b;
            break;
        }
        // a > 0, b > 0
        a--; b--; steps++;
    }
    return steps;
}

int main() {
    cout << maxSteps(4, 4, 6) << endl;    // 7
    cout << maxSteps(2, 3, 10) << endl;   // 5 (2+3=5 ≤ 10)
    cout << maxSteps(5, 5, 5) << endl;    // 7 ((5+5+5)/2 = 7)
    cout << maxSteps(1, 1, 1) << endl;    // 1
    cout << maxSteps(10, 1, 1) << endl;   // 2
    
    // ทดสอบกับ Simulation
    cout << "--- Simulation ---" << endl;
    cout << maxStepsSim(4, 4, 6) << endl;
    
    return 0;
}

การพิสูจน์สูตร

แต่ละขั้นตอนลดผลรวมรวม a+b+c ลง 2 (ลบ 1 จาก 2 ตัว)

• ถ้า a+b ≤ c: ตัว c ใหญ่เกินกว่า ลด a,b จนหมด → Steps = a+b
• ถ้า a+b > c: สามารถลดจนหมดทั้ง 3 ได้ → Steps = floor((a+b+c)/2)

ผลลัพธ์

7
5
7
1
2
--- Simulation ---
7

สรุป

โจทย์นี้คือ LeetCode 1753 (Maximum Score From Removing Stones) ใช้ Greedy + Math ได้ O(1) ไม่ต้อง Simulation