Cache Hit Ledger

Replay a log of requests against a small cache that evicts the least frequently used entry, and report what happened to each request.

The cache holds at most capacity keys. Each cached key has a use count, and the cache remembers how recently each key was used.

A request is either a key k (a lookup) or !k (an invalidation).

• Lookup of k, key is cached: the result is "HIT". Its use count goes up by 1 and it becomes the most recently used key.
• Lookup of k, key is not cached: the key is inserted with use count 1 as the most recently used key. If the cache was full, first evict the key with the lowest use count; if several keys share that count, evict the least recently used of them. The result is "MISS" if nothing was evicted and "EVICT x" if key x was evicted. If capacity is 0 nothing is ever stored and the result is "MISS".
• Invalidation !k: if k is cached it is removed (result "DROP"), and if it later returns it starts again with use count 1. If k is not cached the result is "NOOP".

Aging: after every period-th lookup (invalidations are not counted), once that lookup has been fully processed, every cached key's use count becomes (count + 1) // 2, rounding up. Recency is not affected.

Input: capacity, period, and requests, a list of strings.

Output: a list [results, keys]: results has one result string per request in order, and keys is the sorted list of keys cached at the end.