Header Ads Widget

Distinct solutions | hackerearth solution

EasyCodingZone 01:11

  Problem:-

Bob and Alice decided that problem X needs at least N distinct solutions to be written. It does not matter how many solutions each of them will write, they need to write at least N solutions in total.

Bob needs t1 units of time to write a solution, and Alice needs t2 units of time. They start to work simultaneously at time 0. For example, Bob finishes writing his first solution at time t1, his second solution at 2∗t1, and so on.

Bob and Alice are working using the same algorithm. Each time Bob or Alice finishes writing a solution, he checks on how many solutions have already been written up to the current time moment t. If the number of such solutions is strictly less than N, then he starts writing the next solution. If a member began working on a problem, he does not stop working under any circumstances and he will surely finish it.

Bob and Alice realize that if they act on this algorithm, they will not necessarily write exactly N solutions in total. 

Considering that Bob and Alice work non-stop, find how many solutions they wrote in total and the moment when the latest solution was finished. 

Input format

  • The first line contains an integer T denoting the number of test cases.
  • The first line of each test case contains three space-separated integers N, t1 and t2.

Output format

For each test case, print two integers m and f, where m is the number of written solutions and f is the moment when the last solution was finished. Output for each test case should be in a new line.

Constraints

1≤T≤1000001≤N,t1,t2≤1000000000

Sample Input
3
2 1 2
2 2 4
4 5 5
Sample Output
3 2
3 4
4 10
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

For the first test case, Bob will finish writing his first solution at t=1. At this moment, only 1 solution is completed. Therefore, he will start writing his second solution and finish at t=2. At this moment, Alice will also finish writing her first solution. Thus, total 3 solutions will be written.

For the third test case, both Bob and Alice will end up writing exactly 4 solutions at t=10.

 Code:-

Solution 2 ( C++ language):-

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define LL long long int
#define ULL unsigned LL
#define LD long double
#define FI first
#define SE second
#define PB push_back
#define PF push_front
#define V vector
#define PQ priority_queue
#define ALL(x) x.begin(), x.end()
#define SZ(x) (int)(x).size()
#define FORI(i, a, b) for(int i = a; i < b ; ++i)
#define FORD(i, a, b) for(int i = a; i > b ; --i)
using namespace std;
using pii = pair<int, int>;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
clock_t start_t = clock();
int t, n, t1, t2;
    cin >> t;
    while(t--){
    cin >> n >> t1 >> t2;
        LL lf = 1, rf = (LL)n * min(t1, t2);
        while(lf < rf){
            LL f = (lf + rf) / 2, m1 = f / t1, m2 = f / t2;
            if (m1 + m2 < n){
                lf = f + 1;
            }
            else {
                rf = f;
            }
        }
        // cout << rf << ' ';
        LL m = rf / t1 + rf / t2;
        if (rf % t1){
            m++;
            rf += t1 - rf % t1;
        }
        else if (rf % t2){
            m++;
            rf += t2 - rf % t2;
        }
    cout << m << ' ' << rf << '\n';
    }
return 0;
}

Recommended Post :-

HCL Coding Questions:-

Capgemini Coding Questions:-

Companies interview:-

Full C course:-    

Key points:-

Cracking the coding interview:-

 Array and string:-

Tree and graph:-

Hackerearth Problems:-

Hackerrank Problems:-

Data structure:-

 MCQs:-

Tags:

Post a Comment

0 Comments