TRJOL - Editorial

editorial
, , , ,
1

TRJOL

PROBLEM LINK:

Contest

Setter: Nitish Kumar Dubey

Tester : Aditya Kumar Shaw

Editorialist: Bratati Chakraborty

DIFFICULTY:

Easy

PREREQUISITES:

Basic Maths

PROBLEM:

We need to increase the Fragrance (F) of the drug to its maximum value such that H is always less than Y. Two chemicals 1 and 2 can be added to the drug to increase its fragrance. On adding 1, H gets multiplied by A and F gets increased by 1 and on adding 2, H gets incremented by B, and F gets increased by 1.
The initial hardness is X and the initial fragrance is 0. We have to find the maximum possible value of fragrance in such a way that H doesn’t reach Y.

QUICK EXPLANATION:

We need to choose the operation (adding either chemical 1 or 2) that results in the minimum new value of X. Since H needs to be less than Y, this will ensure that the hardness will increase as slowly as possible. And we will get the maximum number of operations resulting in the maximized F.

EXPLANATION:

If we add chemical 1, then H gets multiplied by A and if we add chemical 2, H gets incremented by B. But, in both the cases F gets incremented by 1. So, every time we add any of the two chemicals, F gets incremented. Hence, the final value of F will be equal to the number of operations performed.

Every operation could result in X=X * A or X=X+B. And H has to be less than Y, so if we want to maximize the no. of operations (in order to maximize F), we would want H to increase slowly. We need to choose the operation such that the new hardness is the minimum of the two results (X=X * A and X=X+B).

If X * A < X+B, then we’ll choose chemical 1 over 2 and the same will hold true for the steps following it. Alternatively, if X * A>X+B, then we’ll choose chemical 2 throughout the entire procedure.

We can execute X=X * A and F++ in a loop with the condition that X * A is minimum and the new X is less than Y:

	  while(a*x<y&&a*x<=x+b)
	  {
	      x*=a;
	      f++;
	  }

Note that if X+B is minimum, then for all the next steps it will be minimum as well. In this case, multiplication won’t be selected at all. So, the number of operations (=maximum fragrance) will be (Y-X-1)/b (because H can’t be greater than or equal to Y and that is our condition for operating on H and F).

The final answer will be the number of times we perform X * A operations (which is nothing but the no of times the while loop runs) plus the number of X+B operations performed.

TIME COMPLEXITY:

O(log n)

SOLUTION:

Setter's Solution 
Language: C++14

#include <bits/stdc++.h>

/*ABBREVIATION*/

#define ll long long int
#define mod 1000000007
#define vi vector<ll>
#define vic vector<char>
#define mp make_pair
#define pb push_back
#define ff first
#define ss second
#define sz(x) (x.size())
#define CASE(t) cout<<"Case #"<<(t)<<": "
#define mii map<ll,ll>
#define mci map<char,ll>
#define inf 1e18

/*loops*/

#define f(i,a,b) for(ll i=a;i<b;i++)
#define rf(i,a,b) for(ll i=a;i>=b;i--)
#define rep(i,n) f(i,0,n)
#define rrep(i,n) rf(i,n-1,0)
#define w(t) ll t; cin>>t; while(t--)
/*max-min*/
#define max3(a, b, c)   max(max(a, b), c)
#define min3(a, b, c)   min(min(a, b), c)

//print

#define no cout<<"NO"<<endl
#define yes cout<<"YES"<<endl
#define print(a) cout<<a<<endl
#define line cout<<endl

// sorting

#define all(V) (V).begin(),(V).end()
#define srt(V) sort(all(V))
#define sortGreat(V) sort(all(V),greater<ll>())

//input format
#define in ll n;cin>>n;
#define input rep(i,n){cin>>a[i];}

using namespace std;

/*void nitishcs414()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
#ifndef ONLINE_JUDGE
	freopen("input3.txt", "r", stdin);
	freopen("output3.txt", "w", stdout);
#endif
//	return 0;
}
*/


int main() {
	//ios_base::sync_with_stdio(false);
	//cin.tie(NULL);
	
	//nitishcs414();
	w(t)
	{
	  ll x,y,a,b;
	  cin>>x>>y>>a>>b;
	  ll ans=0;
	  while(a*x<y&&a*x<=x+b)
	  {
	      x*=a;
	      ans++;
	     
	  }
	  cout<<ans+(y-x-1)/b<<endl;
	}

	return 0;
}
Tester's Solution 
Language: Java

import java.util.*;

class Trjol
{
	public static void main(String args[])
	{
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		while(T-->0) {
			int x,y,a,b;
			x = sc.nextInt();
			y = sc.nextInt();
			a = sc.nextInt();
			b = sc.nextInt();
			int h = x;
			int f = 0;
			while(h*a < y && h*(a-1)<b ) {
				f += 1;
				h *= a;
			}	
			f += (y-1-h)/b;
			//int alt= (y-1-x)/b;
			// System.out.println(f + " " + alt);
			//f = (alt>f) ? alt : f;
			System.out.println(f);
		}
	}
}
Editorialist's Solution 
Language: C++

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main(){
	int t;
	cin>>t;
	while(t--){
		ll x,y,a,b;
		cin>>x>>y>>a>>b;
		ll f=0;
		while(x*a<y&&x*a<=x+b){
			x*=a;
			f++;
		}
		cout<<f+(y-x-1)/b<<endl;
	}
}
1 Like