113  Power of Cryptography
Moderator: Board moderators

 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]
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]

 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)
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)
A question about problem 113.
I didn't use any algorithm in this problem. Just a pow(p,1/n).
I can't believe I got AC!
And later I met a question. Look at this program:
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.
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;}
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;}
I stay home. Don't call me out.
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.
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.
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.
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.

 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
GOOD PROGRAMMING.
Asif
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[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?
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?
Code: Select all
temp[0] = 1;
temp[1] = 1;
I'm sorry. That was a quite silly question.
I have done like this: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.
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
}
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.
Code: Select all
l = 1; r = 1000000000;
if (n>12) r = (int)pow(10,101.0/n);
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
Can anybody help me?
why this code got AC
And this WA
Thank's![/code]
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));}
}
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);
}