Page Contents
Codechef Covaxin vs Covishield 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+(i−1)⋅ba+(i−1)⋅b coins for every i≥1i≥1.
- ithith dose of Covishield costs c+(i−1)⋅dc+(i−1)⋅d coins for every i≥1i≥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 i≥1i≥1 and i≤I−1i≤I−1:
- Ai+1=(Ai+ansi⋅T)modM+PAi+1=(Ai+ansi⋅T)modM+P
- Bi+1=(Bi+ansi⋅T)modM+QBi+1=(Bi+ansi⋅T)modM+Q
- Ci+1=(Ci+ansi⋅T)modM+RCi+1=(Ci+ansi⋅T)modM+R
- Di+1=(Di+ansi⋅T)modM+SDi+1=(Di+ansi⋅T)modM+S .
Note: Since the output is large, prefer using fast input-output methods.
Also See: September Long Challenge 2021 Solutions
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
- 1≤I≤5⋅1051≤I≤5⋅105
- 1≤X,A1,B1,C1,D1≤10181≤X,A1,B1,C1,D1≤1018
- 1≤P,Q,R,S,M≤10181≤P,Q,R,S,M≤1018
- 1≤T≤1091≤T≤109
Subtasks
Subtask #1 (10 points):
- 1≤I≤1031≤I≤103
- 1≤X≤1091≤X≤109
- Time limit: 11 sec
Subtask #2 (30 points):
- 1≤I≤1031≤I≤103
- 1≤X≤10151≤X≤1015
- 109≤A1≤1018109≤A1≤1018
- 109≤B1≤1018109≤B1≤1018
- 109≤P≤1018109≤P≤1018
- 109≤Q≤1018109≤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+11⋅4+3)mod20,(3+11⋅4+7)mod20,(4+11⋅4+8)mod20,(1+11⋅4+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].
Follow us on telegram for quick update an abundance of free knowledge: Click Here
Solution
Program C:
#include <stdio.h>
#define ll long long int
int main(void) {
int I,i,j,flag;
scanf("%d",&I);
ll A,B,C,D,x,add,p,q,r,s,m,covaxin,covishield;
scanf("%lld %lld %lld %lld %lld",&x,&A,&B,&C,&D);
int t,ans;
scanf("%lld %lld %lld %lld %d %lld",&p,&q,&r,&s,&t,&m);
for(int k=0;k<I;k++){
add=0;
i=0;
j=0;
flag=0;
if(k>0){
A = (A+ans*t)%m + p;
B = (B+ans*t)%m + q;
C = (C+ans*t)%m + r;
D = (D+ans*t)%m + s;
}
while(x>add){
covaxin=A + i*B;
covishield=C + j*D;
if((add+covishield)>x && (add+covaxin)>x)
break;
if(covaxin<=covishield){
add+=covaxin;
i++;
flag++;
}
else{
add+=covishield;
j++;
flag++;
}
}
ans = flag;
printf("%d\n",ans);
}
return 0;
}
Program C++:
#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;
ll max_vac(ll x, ll a, ll b){
ll mv = 1, total_x = 0;
total_x = (mv*(2*a + (mv-1)*b))/2;
if(total_x > x) return 0;
else while(total_x <= x){
mv = mv<<1;
total_x = (mv*(2*a + (mv-1)*b))/2;
}
ll l = mv>>1, h = mv;
while(l<=h){
ll i = l + (h-l)/2;
total_x = (i*(2*a + (i-1)*b))/2;
if(total_x > x) h = i-1;
else l = i+1;
}
return h;
}
ll query_i(ll x, ll a, ll b, ll c, ll d){
ll u = max_vac(x, a, b);//if j == 0;
ll v = max_vac(x, c, d);//if i == 0;
if(u==0) return v;
if(v==0) return u;
ll l = 0, h = u;
ll ans = 0;
while(l<=h){
ll i = l + (h-l)/2;
ll rem_x = x - (i*(2*a+(i-1)*b))/2;
ll j = max_vac(rem_x, c, d);
if(i==0) break;
ans = max(ans, i+j);
ll cost_ith_covax = a + (i-1)*b;
ll cost_jth_covis = c + (j-1)*d;
if(cost_ith_covax < cost_jth_covis) l = i+1;
else if(cost_ith_covax > cost_jth_covis) h = i-1;
else{
if(i<j) h = i-1;
else l = i+1;
}
}
ll total_covax = h;
ll total_covis = max_vac(x-(total_covax*(2*a + (total_covax-1)*b))/2, c, d);
return max({ans, total_covax + total_covis, u, v});
}
void solve(){
ll I, x, a, b, c, d, p, q, r, s, t, m;
cin >> I
>> x >> a >> b >> c >> d
>> p >> q >> r >> s >> t >> m;
while(I--){
ll ans = query_i(x, a, b, c, d);
cout << ans << '\n';
a = (a%m + ((ans%m)*(t%m))%m)%m + p;
b = (b%m + ((ans%m)*(t%m))%m)%m + q;
c = (c%m + ((ans%m)*(t%m))%m)%m + r;
d = (d%m + ((ans%m)*(t%m))%m)%m + s;
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
solve();
return 0;
}
Program Java:
import java.io.*;
import java.util.*;
public class Main
{
public static void main(String[] args) throws IOException
{
try{
long I;
long x,a,b,c,d,p,q,r,s,t,m;
Scanner sc=new Scanner(System.in);
I=sc.nextLong();
x=sc.nextLong();
a=sc.nextLong();
b=sc.nextLong();
c=sc.nextLong();
d=sc.nextLong();
p=sc.nextLong();
q=sc.nextLong();
r=sc.nextLong();
s=sc.nextLong();
t=sc.nextLong();
m=sc.nextLong();
while(I--!=0)
{
long rem = x;
long cscount=1,covcount=1,res=0;
long covaxin,covidshield;
while(rem!=0)
{
long spend;
covaxin = a+(covcount-1)*b;
covidshield = c+(cscount-1)*d;
if(covaxin<covidshield)
{
spend = covaxin;
covcount++;
}
else if(covaxin>covidshield){
spend = covidshield;
cscount++;
}
else {
if(covcount>cscount)
{
spend = covaxin;
covcount++;
}
else{
spend = covidshield;
cscount++;
}
}
if(rem>=spend){
res++;
rem=rem-spend;
}
else
break;
}
System.out.println(res);
a = (a+res*t)%m+p;
b = (b+res*t)%m+q;
c = (c+res*t)%m+r;
d = (d+res*t)%m+s;
}
}
catch(Exception e){
return;
}
}}
Program Python:
# cook your dish here
I = int(input())
x,a,b,c,d = map(int, input().split())
p,q,r,s,t,m = map(int, input().split())
for i in range(I):
cost = 0
count = 0
pill1 = 1
pill2 = 1
while cost<x:
p1 = a+(pill1-1)*b
p2 = c+(pill2-1)*d
# print('prices ', p1, p2)
if p1>p2 and cost+p2<=x:
# print('p2 selected')
cost+=p2
count+=1
pill2+=1
elif p2>p1 and cost+p1<=x:
# print('p1 selected')
cost+=p1
count+=1
pill1+=1
else:
if cost+p2>x and cost+p1>x:
break
else:
# print('p1 of both selected')
cost+=p1
count+=1
pill1+=1
print(count)
a = (a + count*t)%m + p
b = (b + count*t)%m + q
c = (c + count*t)%m + r
d = (d + count*t)%m + s
Codechef Long Challenges
September Long Challenge 2021 Solution
- Airline Restrictions
- Travel Pass
- Shuffling Parities
- XOR Equal
- 2-D Point Meeting
- Minimize Digit Sum
- Minimum Digit Sum 2
- Treasure Hunt
- Covaxin vs Covishield
August Long Challenge 2021 Solutions
- Olympics Ranking
- Problem Difficulties
- Chef and Bulb Invention
- Array Filling
- Special Triplets
- Geometry 1
- Charge Scheduling
- Chef and Digits of Large Numbers
- Fat Hut
- Alternating LG Queries