## 113 - Power of Cryptography

Moderator: Board moderators

El-idioto
New poster
Posts: 45
Joined: Mon Jul 14, 2003 9:42 pm
Location: Zoetermeer, The Netherlands
For some reason I get WA. I don't have g++, so maybe g++ gives a different result for my app(?)

Could someone please test / check this?

[cpp]#include <cstdio>
#include <cmath>

int main()
{
long double ldPower, ldResult;

// Read the power and the result
while(scanf("%lf %lf", &ldPower, &ldResult) == 2)
{
// n 1/n p/n
// k = p <=> k = p <=> k = e
//
// In debug mode formula 1 is about twice as fast as formula 2.
// In release mode they are equally fast (they are optimized to the same code).

// Calculate the base
printf("%.lf\n", floor(pow(ldResult, (long double)1.0 / ldPower) + 0.5));
}

return 0;
}[/cpp]

Subeen
Experienced poster
Posts: 127
Joined: Tue Nov 06, 2001 2:00 am
Contact:
use double instead of long double.

( double ldPower, ldResult; )

El-idioto
New poster
Posts: 45
Joined: Mon Jul 14, 2003 9:42 pm
Location: Zoetermeer, The Netherlands
Hi Subeen, You are right, now I got accepted.

I normally never use 'long double' because I work with Visual Studio (where double and long double are the same).
I thought that g++ saw them as different types(?)

Still, my point stands... why wouldn't my code work with g++? (it works just fine with Visual Studio)

ImLazy
Experienced poster
Posts: 215
Joined: Sat Jul 10, 2004 4:31 pm
Location: Shanghai, China

### A question about problem 113.

I didn't use any algorithm in this problem. Just a pow(p,1/n).

Code: Select all

``````#include<stdio.h>
#include<math.h>
int main(){
double n,p;
while(scanf("%lf %lf",&n,&p)==2){
printf("%.lf\n",floor(pow(p,1.0/n)+0.5));}
return 0;}
``````
I can't believe I got AC!
And later I met a question. Look at this program:

Code: Select all

``````#include<stdio.h>
int main(){
double p;
scanf("%lf",&p);
printf("%lf",p);
return 0;}
``````
When input 4357186184021382204544 (as the sample input), the output is 4357186184021382000000.000000. You see, the last 6 bits are lost. Then how can the former program get AC in this case??? I can't understand. Who can tell me? Thanks.
I stay home. Don't call me out.

shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA
Hi ImLazy,
There has been a long term discussions over this topic. When I first heard that the problem can be solved this easily, I thought the judge data must be shallow. But on a later date, I checked the input file using assert() to see if there is really numbers of 100 digits, surprisingly there is. So it also my wonder as to how this is possible.

ImLazy
Experienced poster
Posts: 215
Joined: Sat Jul 10, 2004 4:31 pm
Location: Shanghai, China

### Oh! I'v got the point of problem 113!

We know, if we input a number of more than 16 bits to a datum of double type, for instance, 4357186184021382204544 (as the sample input of 113), the precision will be lost. The 4357186184021382204544 will be stored as 4357186184021382000000. But that doesn't matter, the program can still get right answer!
Because, if a number is very very big, then even it changes a lot a lot, its root will change only a little a little. In fact we can input any number from 4357186184000000000000 to 4357186184021382204544, the answer will be always 1234.
Maybe you have realized this. But for me, a new comer, it was so exciting to get this idea this morning. So I have to say it here.
I stay home. Don't call me out.

asif_rahman0
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm

### Fine!!!!!

Hey Imlazy congratulations u've got a good idea.But U didn't say that either ur code has been excepted or not.If u don't solve the problem yet then I tell u to read the problem carefully as the solve of the problem also described there.Just look carefully to the problem description.
GOOD PROGRAMMING. Asif

ImLazy
Experienced poster
Posts: 215
Joined: Sat Jul 10, 2004 4:31 pm
Location: Shanghai, China
Certainly I'v got AC. Thanks.
I stay home. Don't call me out.

clist
New poster
Posts: 3
Joined: Wed Feb 16, 2005 10:56 am

### About 113,Why I keep getting WA

The main code below:
l = 1; r = 1000000000;
if (n>12) r = (int)pow(10,101.0/n);

while (l<r){
for (i=2;i<=MAXN;i++)
temp = 0;
temp = 1;
temp = 1;
x = (l + r) / 2;
for (i=1;i<=n;i++)
multiply(temp,x);

flag = compare(temp);

if (flag==0){
l = x;
break;
}
else if (flag==1){
l = x + 1;
}
else r = x - 1;

}
printf("%d\n",l);
It may be an arbitrary method to solve this problem,but I think it's right.I've thought for 3 hours but ...Could anyone help me?

teni_teni
New poster
Posts: 15
Joined: Sat Feb 05, 2005 8:04 am

Code: Select all

``````temp = 1;
temp = 1; ``````
what's this? eleven?

clist
New poster
Posts: 3
Joined: Wed Feb 16, 2005 10:56 am
temp is the length of temp

teni_teni
New poster
Posts: 15
Joined: Sat Feb 05, 2005 8:04 am
I'm sorry. That was a quite silly question.

I have done like this:

Code: Select all

``````while (true) {  // <= !!!
x = (l + r) / 2;

if (P == power( x, N ))
break;

if (P >  power( x, N ))
l = x;              // should use x + 1
else
r = x;              // should use x - 1
}``````
note that this is not actual program but mere concept.

I know that this will stop only when a correct integer pair is given.
But it also hardly stops if comparing/multiplying function has a bug.

Main part of your program seems to be correct, so you would be better to reconsult other part.

teni_teni
New poster
Posts: 15
Joined: Sat Feb 05, 2005 8:04 am

Code: Select all

`````` l = 1; r = 1000000000;
if (n>12) r = (int)pow(10,101.0/n);``````
r = 10^9;

Code: Select all

``````n=11 ==> 10^(11 * 9) = 10 ^ 99
n=12 ==> 10^(12 * 9) = 10 ^ 108                   <=!!!!!!!
n=13 ==> pow(10,101.0/n)^13 = 58780160^13 < 10^101``````
temp's size is ok? is this a small thing?

clist
New poster
Posts: 3
Joined: Wed Feb 16, 2005 10:56 am
I think it is ok because the length of array defined can be more than 101

Andrey
New poster
Posts: 16
Joined: Sat Mar 05, 2005 8:25 pm
Location: Ukraine,Vinnitsa

### Can anybody help me?

why this code got AC

Code: Select all

``````#include<stdio.h>
#include<math.h>

void main()
{
double n,p;
while(scanf("%lf %lf",&n,&p)==2)
{printf("%.lf\n",floor(pow(p,1.0/n)+0.5));}
}
``````
And this WA

Code: Select all

``````#include<iostream.h>
#include<math.h>

void main()
{
double n,p;
while(cin>>n>>p) cout<<floor(pow(p,1.0/n)+0.5);
}``````
Thank's![/code]