Untitled

#include <iostream>

using namespace std;

int N; // Số lượng người trong dãy
int people[1001], door[4], kc[4][1001], check[5], visit[1001]; // Mảng lưu thông tin về người, cửa, khoảng cách, kiểm tra và viếng thăm
int Max; // Biến lưu trữ kết quả tối ưu

// Hàm in mảng khoảng cách
void print(int kc[]) {
    for (int i = 1; i <= N; i++) {
        cout << kc[i] << " ";
    }
    cout << endl;
}

// Hàm backtrack để thực hiện quay lui
void backtrack(int indext, int sum) {
    // Nếu đã duyệt hết 4 cửa
    if (indext == 4) {
        // Lưu kết quả tối ưu
        Max = min(Max, sum);
        return;
    }
    // Duyệt qua từng cửa
    for (int s = 1; s <= 3; s++) {
        // Nếu chưa kiểm tra cửa này
        if (check[s] == 0) {
            // Duyệt qua 2 trường hợp: mở cửa hoặc không mở
            for (int k = 0; k < 2; k++) {
                int dor = door[s]; // Cửa hiện tại
                int guse = people[dor]; // Số người ở cửa đó
                int cout = 0; // Biến đếm số lần di chuyển
                int value = 0; // Biến lưu tổng khoảng cách
                // Trường hợp mở cửa
                if (k == 0) {
                    check[s] = 1;
                    while (guse > 0) {
                        int l = dor - cout; // Cửa bên trái
                        int r = dor + cout; // Cửa bên phải
                        // Nếu cửa bên trái hợp lệ và chưa được viếng thăm
                        if (l >= 1 && visit[l] == 0) {
                            visit[l] = dor;
                            value = value + cout + 1; // Cập nhật tổng khoảng cách
                            guse--; // Giảm số người cần di chuyển
                        }
                        // Nếu cửa bên phải hợp lệ và chưa được viếng thăm
                        else if (r <= N && visit[r] == 0) {
                            visit[r] = dor;
                            value = value + cout + 1; // Cập nhật tổng khoảng cách
                            guse--; // Giảm số người cần di chuyển
                        }
                        // Nếu cửa đã được viếng thăm hoặc vượt quá phạm vi
                        else if ((r <= N && visit[r] != 0) || (l >= 1 && visit[l] != 0)) {
                            cout++; // Tăng biến đếm
                        }
                    }
                    // Gọi đệ quy cho cửa tiếp theo
                    backtrack(indext + 1, sum + value);
                    check[s] = 0; // Đánh dấu cửa đã được kiểm tra
                    // Đặt lại các cửa đã được viếng thăm
                    for (int i = 1; i <= N; i++) {
                        if (visit[i] == dor)
                            visit[i] = 0;
                    }
                } 
                // Trường hợp không mở cửa
                else {
                    check[s] = 1;
                    while (guse > 0) {
                        int l = dor - cout;
                        int r = dor + cout;
                        if (r <= N && visit[r] == 0) {
                            visit[r] = dor;
                            value = value + cout + 1;
                            guse--;
                        }
                        else if (l >= 1 && visit[l] == 0) {
                            visit[l] = dor;
                            value = value + cout + 1;
                            guse--;
                        } else {
                            cout++;
                        }
                    }
                    backtrack(indext + 1, sum + value);
                    check[s] = 0;
                    for (int i = 1; i <= N; i++) {
                        if (visit[i] == dor)
                            visit[i] = 0;
                    }
                }
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int T;
    cin >> T; // Nhập số lượng bộ test
    for (int t = 1; t <= T; t++) {
        cin >> N; // Nhập số lượng người trong dãy
        // Nhập thông tin về cửa và số người ở mỗi cửa
        for (int i = 1; i <= 3; i++) {
            int x;
            cin >> x;
            door[i] = x;
            cin >> people[x];
        }
        // Tính toán khoảng cách từ mỗi cửa đến từng người
        for (int i = 1; i <= 3; i++) {
            int k = door[i];
            for (int j = 1; j <= N; j++) {
                kc[i][j] = abs(k - j) + 1;
            }
        }
        Max = 10000; // Khởi tạo kết quả tối ưu
        backtrack(1, 0); // Gọi hàm backtrack để tìm kết quả tối ưu
        // In kết quả
        cout << "Case #" << t << endl;
        cout << Max << endl;
    }

    return 0;
}