Algorithm
Problem link- https://www.spoj.com/problems/IMMERSED/
IMMERSED - Fantastic Discovery
A fantastic discovery is about to happen in the biology field, and you are part of the team making the research. The research is about measuring the cells growth in an environment oxygen less and in presence of a toxic substance. The team came to a curious hypothesis, the analyzed data tells them that: the growth, the number of days and the toxicity; are related by this formula:
P = N*NcN
where P is the growth measured in thousands of cells.
N is the elapsed number of days.
and c is the constant that relates to the toxicity level of the experiment.
Your biology partners need to takeout some tissues from the cells when these cells reach a specific growth. They require you to write a program that tells them the exact time when this will happen, given a toxicity level and the growth required.
Input
The first line is T (1 ≤ T ≤ 40,000), the number of test cases, then T test cases follow.
Each test case is a line with 2 integers (P c) separated by a space.
P (1 ≤ P ≤ 1015)
c (1 ≤ c ≤ 5)
Output
For each test case you have to output the expected time in decimal format.
Example
Input:
3
1 1
3 4
100 1
Output:
1.000000
1.207384
3.086308
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <bits/stdc++.h>
#include <limits.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;
#define MOD (ll)1000000007
#define pb push_back
#define EPS 1e-9
#define FOR(i, n) for(int i = 0;i < n; i++)
#define pi(a) printf("%d\n", a)
#define all(c) c.begin(), c.end()
#define tr(container, it) for(typeof(container.begin()) it = container.begin(); it != container.end(); it++)
#define gc getchar_unlocked
template <typename T> T gcd(T a, T b){return (b==0)?a:gcd(b,a%b);}
template <typename T> T lcm(T a, T b){return a*(b/gcd(a,b));}
template <typename T> T mod_exp(T b, T p, T m){T x = 1;while(p){if(p&1)x=(x*b)%m;b=(b*b)%m;p=p>>1;}return x;}
template <typename T> T invFermat(T a, T p){return mod_exp(a, p-2, p);}
template <typename T> T exp(T b, T p){T x = 1;while(p){if(p&1)x=(x*b);b=(b*b);p=p>>1;}return x;}
void si(int &x){
register int c = gc();
x = 0;
int neg = 0;
for(;((c<48 || c>57) && c != '-');c = gc());
if(c=='-') {neg=1;c=gc();}
for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
if(neg) x=-x;
}
double binarySearch(double p, int c>{
double lo = 1, hi = 70;
while(hi-lo > 0.000001){
double mid = (lo+hi)/2;
if(mid*pow(mid, c*mid) < p){
lo = mid;
}else
hi = mid;
}
return (lo+hi)/2;
}
int main(){
int t;
si(t);
while(t--){
double p, c;
scanf("%lf%lf", &p, &c);
// double ptemp = log(p);
// cout<<ptemp<<endl;
// cout<<(4*3.086308+1)*log(3.086308)<<endl;
printf("%.6lf\n", binarySearch(p, c)>;
}
return 0;
}Input
1 1
3 4
100 1
Output
1.207384
3.086308
Demonstration
SPOJ Solution-Fantastic Discovery-Solution in C, C++, Java, Python