Submission

Score: 100

User: syndrxme

Problemset: กองไฟ

Language: cpp

Time: 0.011 second

Submitted On: 2026-03-14 12:31:02

#include <iostream>
#include <vector>
#include <cstring> // สำหรับ memset

using namespace std;

const int MOD = 1000000007;

// ตาราง DP: [เหลือ A][เหลือ B][เหลือ C][รสคนแรก][รสคนล่าสุด]
int memo[51][51][51][4][4];

int solve(int a, int b, int c, int first, int last) {
    // Base Case: แจกคัพเค้กหมดแล้ว!
    if (a == 0 && b == 0 && c == 0) {
        // เช็กวงกลม: คนสุดท้าย ต้องไม่ซ้ำกับ คนแรกสุด
        if (first != last) {
            return 1; // นับเป็น 1 วิธีที่ถูกต้อง
        } else {
            return 0; // ผิดกฎวงกลม นำไปใช้ไม่ได้
        }
    }

    // ถ้าเคยคำนวณ state นี้แล้ว ให้ดึงคำตอบมาใช้ได้เลย (หัวใจของ DP)
    if (memo[a][b][c][first][last] != -1) {
        return memo[a][b][c][first][last];
    }

    long long ways = 0;

    // กรณีลองวางรส A (0)
    // เงื่อนไข: ต้องมี A เหลือ และ คนก่อนหน้าต้องไม่ใช่ A
    if (a > 0 && last != 0) {
        int next_first = (first == 3) ? 0 : first; // ถ้าเพิ่งวางชิ้นแรก ให้จำไว้ว่าเริ่มด้วย 0
        ways = (ways + solve(a - 1, b, c, next_first, 0)) % MOD;
    }

    // กรณีลองวางรส B (1)
    if (b > 0 && last != 1) {
        int next_first = (first == 3) ? 1 : first;
        ways = (ways + solve(a, b - 1, c, next_first, 1)) % MOD;
    }

    // กรณีลองวางรส C (2)
    if (c > 0 && last != 2) {
        int next_first = (first == 3) ? 2 : first;
        ways = (ways + solve(a, b, c - 1, next_first, 2)) % MOD;
    }

    // บันทึกคำตอบลงตารางก่อน return
    return memo[a][b][c][first][last] = ways;
}

int main() {
    // ปรับความเร็ว I/O
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, a, b, c;
    if (!(cin >> n >> a >> b >> c)) return 0;

    // เคลียร์ตาราง DP ให้เป็น -1 ทั้งหมด (หมายถึงยังไม่เคยคำนวณ)
    memset(memo, -1, sizeof(memo));

    // เริ่มต้นแจก: โยนจำนวนคัพเค้กเข้าไป และกำหนดสถานะเริ่มต้น (first=3, last=3 คือยังไม่มีใคร)
    cout << solve(a, b, c, 3, 3) << "\n";

    return 0;
}