113 - Power of Cryptography

[El-idioto]

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]

use double instead of long double.

( double ldPower, ldResult; )

[El-idioto]

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]

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.

[shamim]

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]

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.

[asif_rahman0]

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]

Certainly I'v got AC. Thanks.

[clist]

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[0] = 1;
temp[1] = 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]

Code: Select all

temp[0] = 1;
temp[1] = 1; 

what's this? eleven?

[clist]

temp[0] is the length of temp

[teni_teni]

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]

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]

I think it is ok because the length of array defined can be more than 101

[Andrey]

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]