#include <iostream>
#include <vector>
#include <climits>
using namespace std;

// Function to implement First Fit
void firstFit(vector<int>& block, vector<int>& process) {
    cout << "First Fit Allocation:" << endl;
    vector<int> allocation(process.size(), -1); // To store the allocated block for each process

    // Traverse through each process
    for (int i = 0; i < process.size(); i++) {
        for (int j = 0; j < block.size(); j++) {
            if (block[j] >= process[i]) {
                allocation[i] = j;
                block[j] -= process[i]; // Reduce the block size
                break;
            }
        }
    }

    // Output the allocation result
    for (int i = 0; i < allocation.size(); i++) {
        if (allocation[i] != -1)
            cout << "Process " << i + 1 << " allocated to block " << allocation[i] + 1 << endl;
        else
            cout << "Process " << i + 1 << " not allocated" << endl;
    }

    // Show remaining space in each block
    cout << "Remaining Space in blocks: ";
    for (int i = 0; i < block.size(); i++) {
        cout << block[i] << " ";
    }
    cout << endl;
}

// Function to implement Best Fit
void bestFit(vector<int>& block, vector<int>& process) {
    cout << "Best Fit Allocation:" << endl;
    vector<int> allocation(process.size(), -1); // To store the allocated block for each process

    // Traverse through each process
    for (int i = 0; i < process.size(); i++) {
        int bestIndex = -1;
        int minDifference = INT_MAX;
        for (int j = 0; j < block.size(); j++) {
            if (block[j] >= process[i] && block[j] - process[i] < minDifference) {
                minDifference = block[j] - process[i];
                bestIndex = j;
            }
        }

        if (bestIndex != -1) {
            allocation[i] = bestIndex;
            block[bestIndex] -= process[i]; // Reduce the block size
        }
    }

    // Output the allocation result
    for (int i = 0; i < allocation.size(); i++) {
        if (allocation[i] != -1)
            cout << "Process " << i + 1 << " allocated to block " << allocation[i] + 1 << endl;
        else
            cout << "Process " << i + 1 << " not allocated" << endl;
    }

    // Show remaining space in each block
    cout << "Remaining Space in blocks: ";
    for (int i = 0; i < block.size(); i++) {
        cout << block[i] << " ";
    }
    cout << endl;
}

// Function to implement Worst Fit
void worstFit(vector<int>& block, vector<int>& process) {
    cout << "Worst Fit Allocation:" << endl;
    vector<int> allocation(process.size(), -1); // To store the allocated block for each process

    // Traverse through each process
    for (int i = 0; i < process.size(); i++) {
        int worstIndex = -1;
        int maxDifference = -1;
        for (int j = 0; j < block.size(); j++) {
            if (block[j] >= process[i] && block[j] - process[i] > maxDifference) {
                maxDifference = block[j] - process[i];
                worstIndex = j;
            }
        }

        if (worstIndex != -1) {
            allocation[i] = worstIndex;
            block[worstIndex] -= process[i]; // Reduce the block size
        }
    }

    // Output the allocation result
    for (int i = 0; i < allocation.size(); i++) {
        if (allocation[i] != -1)
            cout << "Process " << i + 1 << " allocated to block " << allocation[i] + 1 << endl;
        else
            cout << "Process " << i + 1 << " not allocated" << endl;
    }

    // Show remaining space in each block
    cout << "Remaining Space in blocks: ";
    for (int i = 0; i < block.size(); i++) {
        cout << block[i] << " ";
    }
    cout << endl;
}

int main() {
    // Number of partitions and processes
    int n, m;
    
    // Input number of partitions and processes
    cout << "Enter number of partitions: ";
    cin >> n;
    cout << "Enter number of processes: ";
    cin >> m;

    vector<int> block(n); // Memory blocks
    vector<int> process(m); // Processes to be allocated

    cout << "Enter memory partitions sizes: ";
    for (int i = 0; i < n; i++) {
        cin >> block[i];
    }

    cout << "Enter process sizes: ";
    for (int i = 0; i < m; i++) {include <iostream>
#include <vector>
#include <climits>
using namespace std;

// Function to implement First Fit
void firstFit(vector<int>& block, vector<int>& process) {
    cout << "First Fit Allocation:" << endl;
    vector<int> allocation(process.size(), -1); // To store the allocated block for each process

    // Traverse through each process
    for (int i = 0; i < process.size(); i++) {
        for (int j = 0; j < block.size(); j++) {
            if (block[j] >= process[i]) {
                allocation[i] = j;
                block[j] -= process[i]; // Reduce the block size
                break;
            }
        }
    }

    // Output the allocation result
    for (int i = 0; i < allocation.size(); i++) {
        if (allocation[i] != -1)
            cout << "Process " << i + 1 << " allocated to block " << allocation[i] + 1 << endl;
        else
            cout << "Process " << i + 1 << " not allocated" << endl;
    }

    // Show remaining space in each block
    cout << "Remaining Space in blocks: ";
    for (int i = 0; i < block.size(); i++) {
        cout << block[i] << " ";
    }
    cout << endl;
}

// Function to implement Best Fit
void bestFit(vector<int>& block, vector<int>& process) {
    cout << "Best Fit Allocation:" << endl;
    vector<int> allocation(process.size(), -1); // To store the allocated block for each process

    // Traverse through each process
    for (int i = 0; i < process.size(); i++) {
        int bestIndex = -1;
        int minDifference = INT_MAX;
        for (int j = 0; j < block.size(); j++) {
            if (block[j] >= process[i] && block[j] - process[i] < minDifference) {
                minDifference = block[j] - process[i];
                bestIndex = j;
            }
        }

        if (bestIndex != -1) {
            allocation[i] = bestIndex;
            block[bestIndex] -= process[i]; // Reduce the block size
        }
    }

    // Output the allocation result
    for (int i = 0; i < allocation.size(); i++) {
        if (allocation[i] != -1)
            cout << "Process " << i + 1 << " allocated to block " << allocation[i] + 1 << endl;
        else
            cout << "Process " << i + 1 << " not allocated" << endl;
    }

    // Show remaining space in each block
    cout << "Remaining Space in blocks: ";
    for (int i = 0; i < block.size(); i++) {
        cout << block[i] << " ";
    }
    cout << endl;
}

// Function to implement Worst Fit
void worstFit(vector<int>& block, vector<int>& process) {
    cout << "Worst Fit Allocation:" << endl;
    vector<int> allocation(process.size(), -1); // To store the allocated block for each process

    // Traverse through each process
    for (int i = 0; i < process.size(); i++) {
        int worstIndex = -1;
        int maxDifference = -1;
        for (int j = 0; j < block.size(); j++) {
            if (block[j] >= process[i] && block[j] - process[i] > maxDifference) {
                maxDifference = block[j] - process[i];
                worstIndex = j;
            }
        }

        if (worstIndex != -1) {
            allocation[i] = worstIndex;
            block[worstIndex] -= process[i]; // Reduce the block size
        }
    }

    // Output the allocation result
    for (int i = 0; i < allocation.size(); i++) {
        if (allocation[i] != -1)
            cout << "Process " << i + 1 << " allocated to block " << allocation[i] + 1 << endl;
        else
            cout << "Process " << i + 1 << " not allocated" << endl;
    }

    // Show remaining space in each block
    cout << "Remaining Space in blocks: ";
    for (int i = 0; i < block.size(); i++) {
        cout << block[i] << " ";
    }
    cout << endl;
}

int main() {
    // Number of partitions and processes
    int n, m;
    
    // Input number of partitions and processes
    cout << "Enter number of partitions: ";
    cin >> n;
    cout << "Enter number of processes: ";
    cin >> m;

    vector<int> block(n); // Memory blocks
    vector<int> process(m); // Processes to be allocated

    cout << "Enter memory partitions sizes: ";
    for (int i = 0; i < n; i++) {
        cin >> block[i];
    }

    cout << "Enter process sizes: ";
    for (int i = 0; i < m; i++) {
        cin >> process[i];
    }

    // Apply the First Fit, Best Fit, and Worst Fit algorithms
    firstFit(block, process);
    cout << endl;

    // Reset blocks for next allocation
    block = {100, 500, 200, 300, 600}; // Reset blocks to original values
    bestFit(block, process);
    cout << endl;

    // Reset blocks for next allocation
    block = {100, 500, 200, 300, 600}; // Reset blocks to original values
    worstFit(block, process);

    return 0;
}

        cin >> process[i];
    }

    // Apply the First Fit, Best Fit, and Worst Fit algorithms
    firstFit(block, process);
    cout << endl;

    // Reset blocks for next allocation
    block = {100, 500, 200, 300, 600}; // Reset blocks to original values
    bestFit(block, process);
    cout << endl;

    // Reset blocks for next allocation
    block = {100, 500, 200, 300, 600}; // Reset blocks to original values
    worstFit(block, process);

    return 0;
}