Covaxin vs Covishield Solution September Challenge 2021

Covaxin vs Covishield Solution

There are two types of vaccines available: Covaxin and Covishield. A black marketeer has X Rs and wants to buy as many vaccines as possible. Due to the black marketing concerns, government has enforced the following policy:

  • ith dose of Covaxin costs a+(i−1)⋅b coins for every i≥1.
  • ith dose of Covishield costs c+(i−1)⋅d coins for every i≥1.

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

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

For i≥1 and i≤I−1:

  • Ai+1=(Ai+ansi⋅T)modM+P
  • Bi+1=(Bi+ansi⋅T)modM+Q
  • Ci+1=(Ci+ansi⋅T)modM+R
  • Di+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 I denoting the number of queries.
  • Second line of input contains five integers X,A1,B1,C1,D1
  • Third line of input contains six integers P,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⋅105
  • 1≤X,A1,B1,C1,D1≤1018
  • 1≤P,Q,R,S,M≤1018
  • 1≤T≤109

Subtasks

Subtask #1 (10 points):

  • 1≤I≤103
  • 1≤X≤109
  • Time limit: 1 sec

Subtask #2 (30 points):

  • 1≤I≤103
  • 1≤X≤1015
  • 109≤A1≤1018
  • 109≤B1≤1018
  • 109≤P≤1018
  • 109≤Q≤1018
  • Time limit: 1 sec

Subtask #3 (60 points):

  • Original constraints
  • Time limit: 3 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 1:

  • For the first query, [a,b,c,d]=[A1,B1,C1,D1]=[2,3,4,1]. It is optimal to buy 22 doses of Covaxin (2+5=7) and 2 doses of Covishield (4+5=9). So the total money spent is 7+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) mod 20,(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].

SOLUTION

Program C: Covaxin vs Covishield Solution in 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++: Covaxin vs Covishield Solution in 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: Covaxin vs Covishield Solution in 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: Covaxin vs Covishield Solution in 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 

September Long Challenge 2021 Solution

Leave a Comment

2 × 1 =