Untitled

mail@pastecode.io avatar
unknown
plain_text
8 days ago
3.1 kB
2
Indexable
Never
#include <iostream>

using namespace std;

// Hàm để tính tổng khoảng cách di chuyển của hành khách từ một cửa
int calculateDistance(int N, int startPos, int numPassengers, bool seats[]) {
    int totalDistance = 0;
    for (int i = 0; i < numPassengers; ++i) {
        int distance = 1;
        while (true) {
            // Kiểm tra vị trí ngồi bên trái và phải của cửa
            if ((startPos - distance >= 0 && !seats[startPos - distance]) || (startPos + distance < N && !seats[startPos + distance])) {
                if (startPos - distance >= 0 && !seats[startPos - distance]) {
                    totalDistance += distance;
                    seats[startPos - distance] = true;
                } else if (startPos + distance < N && !seats[startPos + distance]) {
                    totalDistance += distance;
                    seats[startPos + distance] = true;
                }
                break;
            }
            distance++;
        }
    }
    return totalDistance;
}

// Hàm để sắp xếp một mảng có 3 phần tử
void sortOrder(int arr[], int size) {
    for (int i = 0; i < size - 1; ++i) {
        for (int j = 0; j < size - 1 - i; ++j) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

// Hàm để tìm tất cả các hoán vị của mảng
void nextPermutation(int arr[], int size) {
    int i = size - 2;
    while (i >= 0 && arr[i] >= arr[i + 1]) {
        i--;
    }
    if (i >= 0) {
        int j = size - 1;
        while (arr[j] <= arr[i]) {
            j--;
        }
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    for (int k = i + 1, l = size - 1; k < l; k++, l--) {
        int temp = arr[k];
        arr[k] = arr[l];
        arr[l] = temp;
    }
}

int main() {
    int T;
    cin >> T;
    
    for (int caseNum = 1; caseNum <= T; ++caseNum) {
        int N;
        cin >> N;
        
        int positions[3], passengers[3];
        for (int i = 0; i < 3; ++i) {
            cin >> positions[i] >> passengers[i];
            positions[i]--; // Để vị trí bắt đầu từ 0
        }
        
        int minDistance = 999999; // Giá trị lớn ban đầu
        int order[3] = {0, 1, 2};
        
        // Duyệt tất cả các thứ tự mở cửa
        do {
            bool seats[60] = {false}; // Mảng trạng thái ghế trống
            
            int currentDistance = 0;
            for (int i = 0; i < 3; ++i) {
                currentDistance += calculateDistance(N, positions[order[i]], passengers[order[i]], seats);
            }
            
            if (currentDistance < minDistance) {
                minDistance = currentDistance;
            }
            
            // Tìm hoán vị kế tiếp
            nextPermutation(order, 3);
        } while (!(order[0] == 0 && order[1] == 1 && order[2] == 2));
        
        cout << "Case #" << caseNum << "\n" << minDistance << "\n";
    }
    
    return 0;
}
Leave a Comment