Problem Link :
Author : Shivam Gupta
Tester : Misha Chorniy
Editorialist : Anand Jaisingh
Pre-Requisites :
None
Explanation :
This is a simple simulation based problem. The most simply way is to just simulate the entire process written in the problem statement.
Before beginning our simulation, let’s make a small observation : One a single day, there can exist only a population of a single type. Initially, on day 0, there’s a single bit.
Now, exactly 2 days later the bit transforms into a nibble, exactly 8 days after that the nibble transforms into a byte and exactly 16 days after that, we have 2 bits, exactly 8 days after that we have 2 nibbles and so on.
So, without using any further ideas or any optimizations, we can just simulate this. Since the time limit is strict and we don’t want to take any chances, we can just precompute this information once initially for each possible n.
Let us maintain a table answer(i,j), 0 \le i \le 2, 0 \le j \le 1600, where answer(0,j) is population of bits on day j, answer(1,j) for population of nibbles on the j^{th} day and so on.
Now,let’s keep a variable curr, and add to it 2/8/16 as appropriate and update all days too, when the population doesn’t change. For example, let day curr have population of x number of bits. Then we need to add 2 to curr, and update , answer(0,j)=x, curr \le j < curr+2 . If the current day had a population of x nibbles, then we would add 8 to curr, and then update answer(1,j)=x, curr \le j < curr+8 .
Later, we can answer all queries in O(1)
Beyond this, you could just read the code to understand. Note that for larger days, answers can be really large, so don’t forget to use long numbers.
Time Complexity : O(maxn+T), where maxn=1600 .