408571: GYM103192 B 页面置换

在地址映射过程中，若在页面中发现所要访问的页面不在内存中，则产生缺页中断。当发生缺页中断时，如果操作系统内存中没有空闲页面，则操作系统必须在内存选择一个页面将其移出内存，以便为即将调入的页面让出空间。而用来选择淘汰哪一页的规则叫做页面置换算法。

通俗的理解：现代计算机常采用页式存储，也就是把各种内容切分成固定大小的块进行存储。操作系统在使用某个页面的内容时，只能从内存中读取内容，所以当要使用某个页面时，如果其不在内存中，就需要将其先从外存调入内存中，但是显然内存的大小是有限的，当新的页面将要进入内存时，如果内存已满，就需要淘汰掉现有的页面，所以需要一些策略来对页面进行调度，这种策略就被叫做页面调度算法。

缺页中断：当调用某页面时，若其不在内存中，就发生缺页中断。

下面给出三种调度算法

1.FIFO调度算法 当需要淘汰一个页面时，总是选择驻留主存时间最长的页面进行淘汰，即先进入主存的页面先淘汰。

2.LRU调度算法 当需要淘汰一个页面时，总是选择在最近一段时间内最久不用的页面予以淘汰。 即淘汰最近最长时间未访问过的页面。

3.OPT调度算法 当需要淘汰一个页面时，从主存中移出永远不再需要的页面；如无这样的页面存在，则选择最长时间不需要访问的页面。

zyw想知道这三种调度算法的优劣，他会以缺页次数为指标，所以请你告诉他哪一种方法缺页中断次数最少，并且告诉他会发生多少次缺页中断。（假定一开始内存中没有任何页面）

第一行给定三个整数n, m, k，分别表示页面请求次数，外存中页面个数（从1开始编号），内存的大小。其中n ≤ 10⁵, m ≤ 10³, k ≤ 100。

第二行给出n个1到m之间的整数，表示页面调用请求的顺序。

第一行输出最优的方法，如果有两种或更多方法是最优的，输出任意一种都可以。

第二行输出缺页中断的次数。

12 8 4
6 2 4 1 4 6 3 8 4 5 7 3

FIFO
8