#include<stdio.h>
int main()
{
        int a[30],b[100],i,j,k,n,p,cout=0,flag=0,l=0,m,sw;
        int max,c[20],d[20],f=0;
        printf("Enter the total no of refernce string :");
        scanf("%d",&n);
        printf("\nEnter the page refence string :");
        for(i=0;i<n;i++)
        scanf("%d",&b[i]);
        printf("\nEnter the no of page frame :");
        scanf("%d",&p);
        printf("\nEnter ur choice for page Replacement :\n\n\n");
        printf("\n\t.......MENU........\n\n");
        printf("\n\t1. FIFO\n");
        printf("\n\t2. LRU\n");
        printf("\n\t3. OPTIMAL\n");
        printf("\nEnter ur choice....:");
        scanf("%d",&sw);
        switch(sw)
        {
                case 1:
                        a[0]=b[0];
                        cout=1;
                        printf("\n\nPage fault : %d ",a[0]);
                        for(i=1;i<n;i++)
                        {
                                if(cout==p)
                                break;
                                flag=0;
                                for(k=0;k<cout;k++)
                                {
                                        if(a[k]==b[i])
                                        {
                                                flag=1;
                                        }
                                }
                                if(flag==0)
                                {
                                        a[cout]=b[i];
                                        printf("\n\nPage fault :");
                                        for(m=0;m<=cout;m++)
                                        printf(" %d ",a[m]);
                                        cout++;
                                }

                        }
                        for(j=i;j<n;j++)
                        {
                                flag=0;
                                if(l==p)
                                l=0;
                                for(k=0;k<p;k++)
                                {
                                if(a[k]==b[j])
                                {
                                        flag=1;
                                }
                        }
                        if(flag==0)
                        {
                                a[l]=b[j];
                                cout++;
                                l++;
                                printf("\n\nPage fault :");
                                for(m=0;m<p;m++)
                                printf(" %d ",a[m]);
                        }

                        }
                        printf("\n\nTotal page fault is %d \n\n",cout);
                        break;
                case 2:
                        a[0]=b[0];
                        cout=1;
                        printf("\n\nPage fault : %d ",a[0]);
                        for(i=1;i<n;i++)
                        {
                                if(cout==p)
                                break;
                                flag=0;
                                for(k=0;k<cout;k++)
                                {
                                        if(a[k]==b[i])
                                        {
                                                flag=1;
                                        }
                                }
                                if(flag==0)
                                {
                                        a[cout]=b[i];
                                        printf("\n\nPage fault :");
                                        for(m=0;m<=cout;m++)
                                        printf(" %d ",a[m]);
                                        cout++;
                                }
                        }
                                for(j=i;j<n;j++)
                                {
                                        flag=0;
                                        if(l==p)
                                        l=0;
                                        for(k=0;k<p;k++)
                                        {
                                                if(a[k]==b[j])
                                                {
                                                        flag=1;
                                                }
                                        }
                                        if(flag==0)
                                        {
                                        for(k=0;k<p;k++)
                                        {
                                        if((a[k]!=b[j-1])&&(a[k]!=b[j-2]))
                                        l=k;
                                        }
                                        a[l]=b[j];
                                        cout++;
                                        printf("\n\nPage fault :");
                                        for(m=0;m<p;m++)
                                        printf(" %d ",a[m]);
                                        }

                                }
                        printf("\n\nTotal page fault is %d \n\n",cout);
                        break;
                case 3:
                        a[0]=b[0];
                        cout=1;
                        printf("\n\nPage fault : %d ",a[0]);
                        for(i=1;i<n;i++)
                        {
                                if(cout==p)
                                break;
                                flag=0;
                                for(k=0;k<cout;k++)
                                {
                                        if(a[k]==b[i])
                                        {
                                                flag=1;
                                        }
                                }
                                if(flag==0)
                                {
                                        a[cout]=b[i];
                                        printf("\n\nPage fault :");
                                        for(m=0;m<=cout;m++)
                                        printf(" %d ",a[m]);
                                        cout++;
                                }

                        }
                        for(j=i;j<n;j++)
                        {
                                flag=0;
                                for(k=0;k<p;k++)
                                {
                                        if(a[k]==b[j])
                                        {
                                        flag=1;
                                        }
                                }
                                if(flag==0)
                                {
                                        for(m=0;m<p;m++)
                                        {
                                        f=0;
                                        for(k=j;k<n;k++)
                                        {
                                                if(b[k]==a[m])
                                                {
                                                c[m]=k;
                                                d[m]=m;
                                                break;
                                                }
                                                else
                                                {
                                                c[m]=0;
                                                f=1;
                                                }
                                        }
                                }
                                if(f!=1)
                                {
                                        max=c[0];
                                        l=d[0];
                                        for(m=0;m<p;m++)
                                        {
                                                if(max>c[m])
                                                l=d[m];
                                        }
                                }


                                a[l]=b[j];
                                cout++;
                                printf("\n\nPage fault :");
                                for(m=0;m<p;m++)
                                printf(" %d ",a[m]);
                                }

                }
                printf("\n\nTotal page fault is %d\n\n",cout);
        }
        return 0;
}