113 - Power of Cryptography

All about problems in Volume 1. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
El-idioto
New poster
Posts: 45
Joined: Mon Jul 14, 2003 9:42 pm
Location: Zoetermeer, The Netherlands

Post by 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
Experienced poster
Posts: 127
Joined: Tue Nov 06, 2001 2:00 am
Location: Bangladesh
Contact:

Post by Subeen »

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

Post by El-idioto »

Hi Subeen,

:o 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.

Post by 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.
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

Post by 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
Experienced poster
Posts: 215
Joined: Sat Jul 10, 2004 4:31 pm
Location: Shanghai, China

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

Post by 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.
I stay home. Don't call me out.

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

Fine!!!!!

Post by 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 :o to the problem description.
GOOD PROGRAMMING. :D
Asif

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

Post by ImLazy »

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

Post by 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
New poster
Posts: 15
Joined: Sat Feb 05, 2005 8:04 am

Post by teni_teni »

Code: Select all

temp[0] = 1;
temp[1] = 1; 
what's this? eleven?

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

Post by clist »

temp[0] is the length of temp

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

Post by 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
New poster
Posts: 15
Joined: Sat Feb 05, 2005 8:04 am

Post by 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
New poster
Posts: 3
Joined: Wed Feb 16, 2005 10:56 am

Post by clist »

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?

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

Post Reply

Return to “Volume 1 (100-199)”