#include <stdio.h>
#include <string.h>

#define MAX 25

void firstFit(int blocks[], int m, int process[], int n) {
    int alloc[MAX];
    memset(alloc, -1, sizeof(alloc));

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (blocks[j] >= process[i]) {
                alloc[i] = j;
                blocks[j] -= process[i];
                break;  // first block that fits, stop
            }
        }
    }

    printf("\n--- First Fit ---\n");
    printf("Process\tSize\tBlock\n");
    for (int i = 0; i < n; i++) {
        if (alloc[i] == -1)
            printf("P%d\t%d\tNot Allocated\n", i+1, process[i]);
        else
            printf("P%d\t%d\tBlock %d\n", i+1, process[i], alloc[i]+1);
    }
}

void bestFit(int blocks[], int m, int process[], int n) {
    int alloc[MAX];
    memset(alloc, -1, sizeof(alloc));

    for (int i = 0; i < n; i++) {
        int bestIdx = -1;
        for (int j = 0; j < m; j++) {
            if (blocks[j] >= process[i]) {
                // pick the smallest block that still fits
                if (bestIdx == -1 || blocks[j] < blocks[bestIdx])
                    bestIdx = j;
            }
        }
        if (bestIdx != -1) {
            alloc[i] = bestIdx;
            blocks[bestIdx] -= process[i];
        }
    }

    printf("\n--- Best Fit ---\n");
    printf("Process\tSize\tBlock\n");
    for (int i = 0; i < n; i++) {
        if (alloc[i] == -1)
            printf("P%d\t%d\tNot Allocated\n", i+1, process[i]);
        else
            printf("P%d\t%d\tBlock %d\n", i+1, process[i], alloc[i]+1);
    }
}

void worstFit(int blocks[], int m, int process[], int n) {
    int alloc[MAX];
    memset(alloc, -1, sizeof(alloc));

    for (int i = 0; i < n; i++) {
        int worstIdx = -1;
        for (int j = 0; j < m; j++) {
            if (blocks[j] >= process[i]) {
                // pick the largest block
                if (worstIdx == -1 || blocks[j] > blocks[worstIdx])
                    worstIdx = j;
            }
        }
        if (worstIdx != -1) {
            alloc[i] = worstIdx;
            blocks[worstIdx] -= process[i];
        }
    }

    printf("\n--- Worst Fit ---\n");
    printf("Process\tSize\tBlock\n");
    for (int i = 0; i < n; i++) {
        if (alloc[i] == -1)
            printf("P%d\t%d\tNot Allocated\n", i+1, process[i]);
        else
            printf("P%d\t%d\tBlock %d\n", i+1, process[i], alloc[i]+1);
    }
}

int main() {
    int m, n;
    int blocks[MAX], process[MAX];
    int b1[MAX], b2[MAX], b3[MAX];

    printf("Enter number of memory blocks: ");
    scanf("%d", &m);
    printf("Enter block sizes: ");
    for (int i = 0; i < m; i++) {
        scanf("%d", &blocks[i]);
        b1[i] = b2[i] = b3[i] = blocks[i];  // each strategy gets a fresh copy
    }

    printf("Enter number of processes: ");
    scanf("%d", &n);
    printf("Enter process sizes: ");
    for (int i = 0; i < n; i++)
        scanf("%d", &process[i]);

    firstFit(b1, m, process, n);
    bestFit (b2, m, process, n);
    worstFit(b3, m, process, n);

    return 0;
}