[Solved] Covaxin vs Covishield codechef solution

Covaxin vs Covishield codechef solution

There are two types of vaccines available: Covaxin and Covishield.

A black marketeer has XX Rs and wants to buy as many vaccines as possible. Due to the black marketing concerns, government has enforced the following policy:

  • ithith dose of Covaxin costs a+(i1)ba+(i−1)⋅b coins for every i1i≥1.

  • ithith dose of Covishield costs c+(i1)dc+(i−1)⋅d coins for every i1i≥1.

The values of the four parameters a,b,ca,b,c and dd, however isn’t constant and might vary from query to query. In general the value of these four parameters for ithith query will be Ai,Bi,CiAi,Bi,Ci and DiDi respectively. Let ansiansi be the maximum total quantity of vaccines the black marketeer can buy corresponding to the ithith query. For each query, you have to find the value of ansiansi.

You will be given integers A1,B1,C1,D1,P,Q,R,S,TA1,B1,C1,D1,P,Q,R,S,T and MM which will define the queries to be followed.

For i1i≥1 and iI1i≤I−1:

  • Ai+1=(Ai+ansiT)modM+PAi+1=(Ai+ansi⋅T)modM+P
  • Bi+1=(Bi+ansiT)modM+QBi+1=(Bi+ansi⋅T)modM+Q
  • Ci+1=(Ci+ansiT)modM+RCi+1=(Ci+ansi⋅T)modM+R
  • Di+1=(Di+ansiT)modM+SDi+1=(Di+ansi⋅T)modM+S .

Note: Since the output is large, prefer using fast input-output methods.

Input Format

  • First line contains of input contains an integer II denoting the number of queries.
  • Second line of input contains five integers X,A1,B1,C1,D1X,A1,B1,C1,D1.
  • Third line of input contains six integers P,Q,R,S,T,MP,Q,R,S,T,M.

Output Format

For each query output the maximum quantity of vaccines the black marketeer can buy.

Constraints

  • 1I51051≤I≤5⋅105
  • 1X,A1,B1,C1,D110181≤X,A1,B1,C1,D1≤1018
  • 1P,Q,R,S,M10181≤P,Q,R,S,M≤1018
  • 1T1091≤T≤109

Subtasks

Subtask #1 (10 points):

  • 1I1031≤I≤103
  • 1X1091≤X≤109
  • Time limit: 11 sec

Subtask #2 (30 points):

  • 1I1031≤I≤103
  • 1X10151≤X≤1015
  • 109A11018109≤A1≤1018
  • 109B11018109≤B1≤1018
  • 109P1018109≤P≤1018
  • 109Q1018109≤Q≤1018
  • Time limit: 11 sec

Subtask #3 (60 points):

  • Original constraints
  • Time limit: 33 sec

Sample Input 1 

3
20 2 3 4 1
3 7 8 4 11 20

Sample Output 1 

4
1
2

Explanation

Test case 11:

  • For the first query, [a,b,c,d]=[A1,B1,C1,D1]=[2,3,4,1][a,b,c,d]=[A1,B1,C1,D1]=[2,3,4,1]. It is optimal to buy 22 doses of Covaxin (2+5=7)(2+5=7) and 22 doses of Covishield (4+5=9)(4+5=9). So the total money spent is 7+9=167+9=16 and now the black marketeer cannot buy any more doses. So the answer is 4.

  • For the second query, [a,b,c,d]=[A2,B2,C2,D2]=[(2+114+3)mod20,(3+114+7)mod20,(4+114+8)mod20,(1+114+4)mod20]=[9,14,16,9][a,b,c,d]=[A2,B2,C2,D2]=[(2+11⋅4+3)mod20,(3+11⋅4+7)mod20,(4+11⋅4+8)mod20,(1+11⋅4+4)mod20]=[9,14,16,9].

  • For the third and the last query, [a,b,c,d]=[A3,B3,C3,D3]=[3,12,15,4][a,b,c,d]=[A3,B3,C3,D3]=[3,12,15,4].


Also read : Airline Restrictions codechef solution

Also read :Travel Pass codechef solution

Also read : Shuffling Parities codechef solution

Also read : XOR Equal codechef solution

Also read : 2-D Point Meeting codechef solution

Also read : Minimize Digit Sum codechef solution

Also read : Treasure Hunt codechef solution

Covaxin vs Covishield codechef solution

Leave a Comment

Your email address will not be published. Required fields are marked *