#include <iostream>
#include <climits>

using namespace std;

// Function to perform First Fit Allocation
void firstFit(int partitions[], bool allocated[], int numPartitions, int processes[], int numProcesses) {
    cout << "\nFirst Fit Allocation:\n";
    for (int i = 0; i < numProcesses; i++) {
        bool allocatedProcess = false;
        for (int j = 0; j < numPartitions; j++) {
            if (!allocated[j] && partitions[j] >= processes[i]) {  // Check if partition is not allocated yet
                cout << processes[i] << "KB in " << partitions[j] << "KB partition, free space - " << partitions[j] - processes[i] << "KB\n";
                partitions[j] -= processes[i];  // Reduce partition size after allocation
                allocated[j] = true;  // Mark partition as allocated
                allocatedProcess = true;
                break;
            }
        }
        if (!allocatedProcess) {
            cout << "Process " << i + 1 << " could not be allocated due to insufficient space.\n";
        }
    }
}

// Function to perform Best Fit Allocation
void bestFit(int partitions[], bool allocated[], int numPartitions, int processes[], int numProcesses) {
    cout << "\nBest Fit Allocation:\n";
    for (int i = 0; i < numProcesses; i++) {
        int bestIdx = -1;
        int minWaste = INT_MAX;
        for (int j = 0; j < numPartitions; j++) {
            if (!allocated[j] && partitions[j] >= processes[i] && partitions[j] - processes[i] < minWaste) {
                bestIdx = j;
                minWaste = partitions[j] - processes[i];
            }
        }
        if (bestIdx != -1) {
            cout << processes[i] << "KB in " << partitions[bestIdx] << "KB partition, free space - " << partitions[bestIdx] - processes[i] << "KB\n";
            partitions[bestIdx] -= processes[i];  // Reduce partition size after allocation
            allocated[bestIdx] = true;  // Mark partition as allocated
        } else {
            cout << "Process " << i + 1 << " could not be allocated due to insufficient space.\n";
        }
    }
}

// Function to perform Worst Fit Allocation
void worstFit(int partitions[], bool allocated[], int numPartitions, int processes[], int numProcesses) {
    cout << "\nWorst Fit Allocation:\n";
    for (int i = 0; i < numProcesses; i++) {
        int worstIdx = -1;
        int maxWaste = -1;
        for (int j = 0; j < numPartitions; j++) {
            if (!allocated[j] && partitions[j] >= processes[i] && partitions[j] - processes[i] > maxWaste) {
                worstIdx = j;
                maxWaste = partitions[j] - processes[i];
            }
        }
        if (worstIdx != -1) {
            cout << processes[i] << "KB in " << partitions[worstIdx] << "KB partition, free space - " << partitions[worstIdx] - processes[i] << "KB\n";
            partitions[worstIdx] -= processes[i];  // Reduce partition size after allocation
            allocated[worstIdx] = true;  // Mark partition as allocated
        } else {
            cout << "Process " << i + 1 << " could not be allocated due to insufficient space.\n";
        }
    }
}

int main() {
    int numPartitions, numProcesses;

    // Take input for number of partitions and processes
    cout << "Enter number of partitions: ";
    cin >> numPartitions;
    int partitions[numPartitions]; // Array of partitions
    int originalPartitions[numPartitions]; // To store original partition sizes
    bool allocated[numPartitions]; // To track which partitions are allocated

    cout << "Enter the sizes of the partitions:\n";
    for (int i = 0; i < numPartitions; i++) {
        cin >> partitions[i];
        originalPartitions[i] = partitions[i]; // Store original partition sizes
        allocated[i] = false; // Initially, no partition is allocated
    }

    cout << "Enter number of processes: ";
    cin >> numProcesses;
    int processes[numProcesses]; // Array of processes

    cout << "Enter the sizes of the processes:\n";
    for (int i = 0; i < numProcesses; i++) {
        cin >> processes[i];
    }

    // Run First Fit Allocation
    firstFit(partitions, allocated, numPartitions, processes, numProcesses);

    // Reset partitions for next algorithm using the original partition sizes
    for (int i = 0; i < numPartitions; i++) {
        partitions[i] = originalPartitions[i];
        allocated[i] = false;  // Reset allocation status
    }

    // Run Best Fit Allocation
    bestFit(partitions, allocated, numPartitions, processes, numProcesses);

    // Reset partitions for next algorithm using the original partition sizes
    for (int i = 0; i < numPartitions; i++) {
        partitions[i] = originalPartitions[i];
        allocated[i] = false;  // Reset allocation status
    }

    // Run Worst Fit Allocation
    worstFit(partitions, allocated, numPartitions, processes, numProcesses);

    return 0;
}