#include <iostream>
#include <vector>
#include <limits>

using namespace std;

void firstFit(vector<int> partitions, vector<int> processes) {
    vector<int> allocation(processes.size(), -1);
    for (int i = 0; i < processes.size(); i++) {
        for (int j = 0; j < partitions.size(); j++) {
            if (partitions[j] >= processes[i]) {
                allocation[i] = j;
                partitions[j] -= processes[i];
                break;
            }
        }
    }

    cout << "\nFirst Fit Allocation:\n";
    for (int i = 0; i < processes.size(); i++) {
        if (allocation[i] != -1) {
            cout << "Process " << i + 1 << " -> Partition " << allocation[i] + 1
                 << " (Remaining: " << partitions[allocation[i]] << ")\n";
        } else {
            cout << "Process " << i + 1 << " -> Not Allocated\n";
        }
    }
}

void bestFit(vector<int> partitions, vector<int> processes) {
    vector<int> allocation(processes.size(), -1);
    for (int i = 0; i < processes.size(); i++) {
        int bestIdx = -1;
        for (int j = 0; j < partitions.size(); j++) {
            if (partitions[j] >= processes[i]) {
                if (bestIdx == -1 || partitions[j] < partitions[bestIdx]) {
                    bestIdx = j;
                }
            }
        }
        if (bestIdx != -1) {
            allocation[i] = bestIdx;
            partitions[bestIdx] -= processes[i];
        }
    }

    cout << "\nBest Fit Allocation:\n";
    for (int i = 0; i < processes.size(); i++) {
        if (allocation[i] != -1) {
            cout << "Process " << i + 1 << " -> Partition " << allocation[i] + 1
                 << " (Remaining: " << partitions[allocation[i]] << ")\n";
        } else {
            cout << "Process " << i + 1 << " -> Not Allocated\n";
        }
    }
}

void worstFit(vector<int> partitions, vector<int> processes) {
    vector<int> allocation(processes.size(), -1);
    for (int i = 0; i < processes.size(); i++) {
        int worstIdx = -1;
        for (int j = 0; j < partitions.size(); j++) {
            if (partitions[j] >= processes[i]) {
                if (worstIdx == -1 || partitions[j] > partitions[worstIdx]) {
                    worstIdx = j;
                }
            }
        }
        if (worstIdx != -1) {
            allocation[i] = worstIdx;
            partitions[worstIdx] -= processes[i];
        }
    }

    cout << "\nWorst Fit Allocation:\n";
    for (int i = 0; i < processes.size(); i++) {
        if (allocation[i] != -1) {
            cout << "Process " << i + 1 << " -> Partition " << allocation[i] + 1
                 << " (Remaining: " << partitions[allocation[i]] << ")\n";
        } else {
            cout << "Process " << i + 1 << " -> Not Allocated\n";
        }
    }
}

int main() {
    int numPartitions, numProcesses;

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

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


    vector<int> originalPartitions = partitions;

    firstFit(partitions, processes);
    partitions = originalPartitions;
    bestFit(partitions, processes);
    partitions = originalPartitions;
    worstFit(partitions, processes);

    return 0;
}