MMSCORE -Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest

Author: Riddhish Lichade
Tester: Ram Agrawal
Editorialist: Prathamesh Sogale

DIFFICULTY:

EASY-MEDIUM

PREREQUISITES:

Greedy, DP, Math etc. Ideally with the links to Wikipedia

PROBLEM:

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.

EXPLANATION:

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.

Now,

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:
con=N-w*(d-1) .
Assign: p=2,ans=1

The number of times his score gets doubled can be given by:
t=con/d.
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
ans=(ans-1)*2*d+n-t*d
Output the answer modulo 10^9+7

SOLUTIONS:

Setter's Solution 
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)