C++: Số lần chia sẻ đá (không lặp số lượng liên tiếp)

Bài toán: Có n viên đá. Mỗi lần cho một số đá >0, không được cho cùng số lượng 2 lần liên tiếp. Tối đa hóa số lần cho.

Kết quả: (2n + 1) / 3 (chia nguyên).

Chiến lược tối ưu: luân phiên 1, 2, 1, 2,... (chu kỳ 3 đá cho 2 lần).

Code C++

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

int solve(int n) {
    return (2 * n + 1) / 3;
}

int main() {
    cout << solve(4) << endl; // 3 (1,2,1)
    return 0;
}

Kết quả

3