A records vault answers requisition requests for computed reports. Each requisition names a report type and an ordered list of integer reference codes. Because generating a report is expensive, the vault remembers every requisition it has already computed: if the exact same report type is requested again with the exact same ordered list of reference codes, the vault serves the previously computed value directly from its cache instead of recomputing it. Two requisitions are considered identical only when both the report type and the full ordered list of reference codes match exactly -- the same codes given in a different order count as a different requisition, and the same codes requested under a different report type also count as a different requisition.
There are four report types:
Process requisitions strictly in the given order. For each requisition, output the value of the requested report on the given codes (whether it is computed fresh or served from the cache). After processing every requisition, output two integers: the number of requisitions that had to be computed for the first time (cache misses, including the very first requisition ever made), followed by the number that were served directly from the cache (cache hits).
Line 1: an integer q (1 <= q <= 20000), the number of requisitions. Each of the next q lines describes one requisition as: TYPE k c1 c2 ... ck where TYPE is one of SUM, PRODUCT, MAX, MIN; k (1 <= k <= 5) is the number of reference codes; and each ci is an integer with -100 <= ci <= 100.
Print q lines, the i-th containing a single integer: the report value for the i-th requisition (in input order). Then print one final line containing two integers separated by a single space: the total number of cache misses followed by the total number of cache hits.
Example 1
Input
4 SUM 3 1 2 3 SUM 3 1 2 3 MAX 2 -5 7 SUM 3 1 2 3
Expected
6 6 7 6 2 2
Explanation
Requisition 1, SUM of 1 2 3, is 6 and is computed fresh (a miss, since nothing is cached yet). Requisition 2 is an exact repeat of requisition 1 (same type SUM, same ordered codes 1 2 3), so it is served from the cache -- it still prints 6, and counts as a hit. Requisition 3, MAX of -5 7, is 7, computed fresh (a miss, since this exact type-and-codes combination has never been seen). Requisition 4 repeats requisition 1's key again, so it is another cache hit, printing 6. Across all 4 requisitions there are 2 misses (requisitions 1 and 3) and 2 hits (requisitions 2 and 4), so the final line is "2 2".
Example 2
Input
3 PRODUCT 2 3 4 PRODUCT 2 4 3 MIN 1 -10
Expected
12 12 -10 3 0
Explanation
Requisition 1, PRODUCT of 3 4, is 12, computed fresh (a miss). Requisition 2 asks for PRODUCT of 4 3 -- the same two codes as requisition 1 but in the opposite order, so it is treated as a DIFFERENT requisition (order matters for the cache key): it is computed fresh as 4*3=12 (a miss, not a hit, even though the printed value happens to equal requisition 1's). Requisition 3, MIN of -10, is -10, computed fresh (a miss). All three requisitions were misses and none were hits, so the final line is "3 0".
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →