Greedy, DP, Math etc. Ideally with the links to Wikipedia
Yesterday, Meena appeared in a quiz competition, where he answered N questions correctly. There were a total of Q questions in the quiz. The result of the quiz has not been declared yet. Meena is too eager to know his score. He wants to find his score by today. The rules of the quiz were as follows:
- The judges use a counter to note any participant’s score, there is a separate counter for every participant. The counter is used to note the consecutive correct answers.
- Every correct answer adds one point to the participant’s score.
- If a participant answers a question incorrectly, then the counter is reduced to 0.
- If a participant’s counter reaches a value dd, then the counter is reset and the participant’s score gets doubled.
Now, the problem with Meena is, he doesn’t remember in what order he answered the questions. Help Meena find out his possible minimum score.
If the answer is too big, output it modulo 10^9+7.
Let w=Q-N representing number of wrong answers.
If (w+1)*(d-1) \geq n, in this case he doesn’t answer continuously more than d-1 questions correctly. So the his score equals N.
To find the minimum score, lets consider the order of correct answers is like
He answers d-1 questions correctly then a wrong answer then again d-1 questions correctly and so on untill the wrong answer count equals w and then he answers all the remaining question correct continuously.
These correct answers at last which he answers correctly equals:
The number of times his score gets doubled can be given by:
Find the answer by running a while loop till t!=0.
In the loop check if t is odd then ans=ans*p. reduce t by a factor of 2, that is t=t/2. p=p*p%mod
After the loop
Output the answer modulo 10^9+7
from sys import stdin mod=10**9+7 for _ in range(int(stdin.readline())): q, n, d = map(int, stdin.readline().strip().split()) w=q-n #wrong answers if((w+1)*(d-1)>=n): print(n) continue con=n-w*(d-1) t=con//d ans=1 p=2 t2=t while(t2!=0): if(t2&1): ans*=p ans=ans%mod t2//=2 p=p*p%mod ans=((ans-1)*2*d+n-t*d)%mod print(ans)