# Distinct solutions | hackerearth solution

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 ${t}_{1}$ units of time to write a solution, and Alice needs ${t}_{2}$ units of time. They start to work simultaneously at time $0$. For example, Bob finishes writing his first solution at time ${t}_{1}$, his second solution at $2\ast {t}_{1}$, 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$${t}_{1}$ and ${t}_{2}$.

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\le T\le 100000\phantom{\rule{0ex}{0ex}}1\le N,{t}_{1},{t}_{2}\le 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);
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:-
iMocha coding Questions:-
Tech Mahindra coding questions:-
Unthinkable Solutions coding questions:-