#include <stdio.h>
#include <stdlib.h> // For malloc, free

// C program for LRU Page Replacement Simulation
// Optimized for minimal code size (e.g., for writing on paper)

int main() {
    int nf, np, i, j, pg, idx, lru, pf = 0, time = 0, min_t;
    // nf=num frames, np=num pages, pf=page faults, time=logical clock
    // idx=found index, lru=least recently used index, pg=current page

    // Input frame count (nf) and page reference string length (np)
    printf("Frames Pages:"); scanf("%d%d", &nf, &np);

    // Dynamic Allocation
    int *f = malloc(nf * sizeof(int)); // f: frames array
    int *c = malloc(nf * sizeof(int)); // c: counter/lru time array
    int *p = malloc(np * sizeof(int)); // p: page reference string array

    // Input page reference string
    printf("Pages:");
    for(i=0; i<np; ) scanf("%d", p+i++); // Read pages into p

    // Initialize frames to -1 (empty)
    for(i=0; i<nf; i++) f[i]=-1; // Can also use for(i=nf;i--;)f[i]=-1;

    // --- LRU Algorithm ---
    for(i=0; i<np; i++) { // Iterate through page reference string
        pg = p[i]; // Current page
        idx = -1; // Reset found index

        // 1. Search if page 'pg' is already in frames 'f'
        for(j=0; j<nf; j++) {
            if(f[j] == pg) {
                idx = j; // Page found at index j
                break;
            }
        }

        if(idx != -1) { // 2a. Page Hit
            c[idx] = ++time; // Update last used time for the hit page
        } else { // 2b. Page Fault
            pf++; // Increment page fault counter
            lru = 0; // Index to replace (default to 0)
            min_t = 0x7FFFFFFF; // Initialize minimum time to max int

            // 3. Find replacement slot: first empty (-1) or LRU
            for(j=0; j<nf; j++) {
                if(f[j] == -1) { // Found an empty frame
                    lru = j;
                    break; // Use the first empty frame
                }
                if(c[j] < min_t) { // Track frame with the smallest time (LRU)
                    min_t = c[j];
                    lru = j;
                }
            }
            // 'lru' now holds index of empty slot or the least recently used page

            // 4. Replace frame and update its time
            f[lru] = pg;
            c[lru] = ++time;
        }
         // Optional: print frame state after each step (for debugging)
         // printf(" (%d):",pg); for(j=0; j<nf; j++)printf(" %d", f[j]==-1?-1:f[j]); puts("");
    }
    // --- End Algorithm ---

    // Output total page faults
    printf("Faults: %d\n", pf);

    // Free dynamically allocated memory
    free(f);
    free(c);
    free(p);

    return 0; // End of program
}