ZOJ Problem Set - 2895
Professor Johnson is doing a research on the direct-mapped cache.
Cache is one part of the CPU. When the CPU is going to access a memory block, it will first check if the memory block is in the cache. If it is in the cache(called a "hit"), the CPU will access the block in the cache, instead of the memory. If it is NOT in the cache(called a "miss"), the CPU will first copy the memory block to the cache, then access the block in the cache.
There are many blocks in the cache, so which one should the memory block be copied to? Here we use direct-mapped. It uses "(Memory block address) modulo (Number of cache blocks in the cache)" as the index, then copy the memory block to the cache block which the index represents.
Now, Professor Johnson want to know, given the sequence of memory block accessing, what is the minimum cache size(the number of cache blocks in the cache), which can lead to the minimum times of miss.
Assume that there is only one level of cache between the CPU and the memory.
There are several test cases. In each test case, the first line contains one integer N (N <= 1,000,000). Then the second line contains N integers, which represents the sequence of memory block accessing. Each of these N integers, is the address of the memory block to access, which will be between 0 and 999 inclusively.
For each test case, output one line with the minimum cache size which can lead to the minimum times of miss.
8 1 2 3 4 1 2 3 4 8 0 1 1 0 2 3 2 3
Author: JIAN, Hengyi
Source: ZOJ Monthly, January 2008