## 113 - Power of Cryptography

Moderator: Board moderators

darksk4
New poster
Posts: 13
Joined: Sun Jul 29, 2012 7:10 pm

### Re: 113 - wrong answer

What's the error in this code?

Code: Select all

``````I see thanks brianfry713
``````
Last edited by darksk4 on Sat Nov 03, 2012 1:20 pm, edited 2 times in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 113 - wrong answer

You need to set the precision so that only integers are displayed.
Check input and AC output for thousands of problems on uDebug!

salman2972
New poster
Posts: 1
Joined: Tue Jun 18, 2013 1:52 am

### Re: 113 precision

i tried to solve that problem in matlab it worked!!!

Code: Select all

``````clear all
close all
clc

%round;ceil;floor;
y=7;
x=4357186184021382204544;
n=4;
p=16;

% check if the n or p in float type then exit

con1=((n-floor(n))&&(n-floor(n)));
con2=((p-floor(p))&&(p-floor(p)));
if(~(con1&&con2))
k=exp(log(p)/n);
%round(k)
else
disp('the inputs must be the intiger values')
end

con3=((k-floor(k))&&(k-floor(k)));

if(~con3)
k
else
disp('the value of k is not an intiger  please try another combination')
end
``````
please let me know if i can make it better...

caiomcg
New poster
Posts: 3
Joined: Tue Oct 29, 2013 4:30 pm

### 113 - Precision - Time limit exceeded

Hey guys.

I am having a problem in the time limit.
Can you guys have a look?
Probably not the best code http://pastebin.com/m2tEjeEM

Thanks

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 113 - Precision - Time limit exceeded

Output pow(p, 1.0 / n));
Check input and AC output for thousands of problems on uDebug!

caiomcg
New poster
Posts: 3
Joined: Tue Oct 29, 2013 4:30 pm

### Re: 113 - Precision - Time limit exceeded

Thank You!

But, I don´t understand this expression, can you explain it to me?

Regards

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 113 - Precision - Time limit exceeded

pow(p, 1.0 / n)) is the same as the nth root of p.
Check input and AC output for thousands of problems on uDebug!

caiomcg
New poster
Posts: 3
Joined: Tue Oct 29, 2013 4:30 pm

### Re: 113 - Precision - Time limit exceeded

I got it lol, thank you Brian!

arash
New poster
Posts: 6
Joined: Wed Feb 19, 2014 10:19 am

### Re: 113 - Precision - Time limit exceeded

why I get wa by this code ?

Code: Select all

``````int main() {
long double p,n;
while (cin >> n >> p) {
cout << round(powl(p, (1.0/n))) << endl;
}
return 0;
}``````

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 113 - Precision - Time limit exceeded

cout << (int)round(powl(p, (1.0/n))) << endl;
Check input and AC output for thousands of problems on uDebug!

uDebug
A great helper
Posts: 475
Joined: Tue Jul 24, 2012 4:23 pm

### Re: 113 - Precision - Time limit exceeded

brianfry713 wrote:pow(p, 1.0 / n)) is the same as the nth root of p.
Right. So I came to the same conclusion before I looked at this thread but then I'm not sure how to go about doing this because p could be as large as 10^100 - and so surely a long double's not going to be able to store p. It occurred to me that I could employ BigInt in Java but the pow function doesn't allow for doubles in the exponent - just ints.

Did I miss something?

Update:

Looks like, foo asked the same question in the following thread here

http://acm.uva.es/board/viewtopic.php?f ... 8d#p205142

double has enough precision for the I/O in the judge for this problem.
Check input and AC output for over 7,500 problems on uDebug!

liya
New poster
Posts: 10
Joined: Fri Jan 23, 2015 2:36 pm

### Re: 113 - Power of Cryptography

WA.....

Code: Select all

``````#include<stdio.h>
#include<math.h>
int main()
{
double n,p,k;

while((scanf("%lf %lf",&n,&p))!=EOF)
{
k=pow(p,(1.0/n));
printf("%.0lf\n",k);

}
return 0;

}``````
Last edited by brianfry713 on Wed Jan 28, 2015 10:58 pm, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 113 - Power of Cryptography

That is AC code.
Check input and AC output for thousands of problems on uDebug!

Robur_131
New poster
Posts: 1
Joined: Fri Jun 16, 2017 3:41 pm

### Re: 113 - Power of Cryptography

The following code gives AC when the EPS is between 1e-10 and 1e-15. But if EPS is greater than 1e-10 or less than 1e-15, then it gives WA. Why is that? I though the double mantissa is represented by ~16 digits.

Code: Select all

``````#include <iostream>
#include <cmath>

int check(int n, double p, int check_value){
int exponentCheck, exponentTarget;
double mantissaCheck = frexp(check_value, &exponentCheck);
double mantissaTarget = frexp(p, &exponentTarget);

double mantissaCheckRaisedToPowerN = std::pow(mantissaCheck, n);
double multiplier = 0.5 / mantissaCheckRaisedToPowerN;
int powerToSubtract = static_cast<int>(std::ceil(std::log2(multiplier)));
int exponentProduct = exponentCheck * n - powerToSubtract;

if(exponentProduct < exponentTarget) return -1;
if(exponentProduct > exponentTarget) return 1;

double mantissaProduct = mantissaCheckRaisedToPowerN * std::pow(2, powerToSubtract);
double difference = std::abs(mantissaProduct - mantissaTarget);

constexpr double EPS = 1e-10; // works between 1e-10 and 1e-15
if(difference < EPS) return 0;
if(mantissaProduct < mantissaTarget) return -1;
return 1;
}

int binarySearch(int n, double p){
int low = 1, high = 1e9;
int ans = -1;
while(low <= high){
int mid = (low + high) / 2;
int status = check(n, p, mid);
if(!status){
ans = mid;
break;
} else if(status == -1){
low = mid + 1;
} else{
high = mid - 1;
}
}
return ans;
}

int main(int argc, char const *argv[])
{
int n;
double p;
while(std::cin >> n >> p){
// double rhs = std::log(p) / n;
// double k = std::exp(rhs);
// std::cout << static_cast<int>(std::nearbyint(k)) << '\n';
std::cout << binarySearch(n,p) << '\n';
}
return 0;
}
``````