113 - Power of Cryptography

[venusaur]

If you cast from double to int (or long) such a big integer, only first 13-14 digits will be right.

In this situlation, you should emulate big integer operation; separate big integer and story at array of integer (for example, store 8 digits per one space of array).

Then, you should implement arithmetic operations (In problem #113, you need to implement division)

PS: Some other example similar to this problem is #288

[Sarmento]

It's easier to simply programme this in C. When will this guys use a more recent version of the language compiler?

Thanks anyway,

joao

[tzzx]

could anyone tell me a standard one using BIG NUMBERS
i just write:
[pascal]
var
n,p:double;
begin
while not eof(input) do
begin
readln(n,p);
writeln(exp(ln(p)/n):1:0);
end;
end.
[/pascal][/pascal]

[Dominik Michniewski]

I think, you got Accepted, because OJ uses only "small" numbers as input - small means less than 10^19 maybe .....

Try your program with numbers which are near of upper limit ... I think that you don't get right answers ... but I could be wrong

Best regards
DM

[Tanzim-Saqib]

It's a very simple problem. In C at most 'long double' you may use for this problem, check for equivalent data type in Pascal.

[r.z.]

the p limit is 10^101
there is no data type that can go that far....

what is the algorithm......

[Hisoka]

double can handle input more than that, 10^(+/-300)

[r.z.]

oh really thanks.....

I'm a newbie in programming.....

have to learn so much

thanks....

[Rav]

Could somebody help me. I writed this program(113), and all is OK, but when i send this program to the judge i get this:
"Your program has died with signal 11 (SIGSEGV). Meaning:

Invalid memory reference

Before crash, it ran during 0.123 seconds."

And it is my program

#include<stdio.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <math.h>

struct tablica
{
int wart,stan;
};


long int liczba,t1,t2;
int tabl[104],i,s,l,pot;
char c,licz[]="0123456789";

void wysz(long int k1,long int k2)
{
tablica tab[103];
int tmp,wskpot,wsktab,dl,wsktabl;
for (wsktab=0;wsktab<=102;++wsktab)
{
tab[wsktab].wart=0;
tab[wsktab].stan=0;
}
tab[102].wart=1;
tab[102].stan=1;
pot=(int)((k1+k2)/2);
for (wskpot=1;wskpot<=liczba;++wskpot)
{
wsktab=102;
while (tab[wsktab].stan!=0)
{
tab[wsktab].wart=pot*tab[wsktab].wart;
--wsktab;
}
wsktab=102;
while (tab[wsktab].stan!=0)
{
while (tab[wsktab].wart>9)
{
tab[wsktab-1].stan=1;
tmp=(int)(tab[wsktab].wart/10);
tab[wsktab].wart=tab[wsktab].wart%10;
tab[wsktab-1].wart=tab[wsktab-1].wart+tmp;
}
--wsktab;
}
}
dl=0;
wsktabl=0;
while (tab[dl].stan==0)
++dl;
tmp=102-dl+1;


if (tmp>i)
wysz(k1,pot);

else if (tmp<i)
wysz(pot,k2);
else
{
while ((wsktabl<i) && (tab[dl].wart==tabl[wsktabl] ))
{
++dl;
++wsktabl;
}
if (wsktabl==i)
printf("%d\n",pot);
else if (tab[dl].wart>tabl[wsktabl])
wysz(k1,pot);
else
wysz(pot,k2);
}
}



int main()
{
#ifndef ONLINE_JUDGE
close (0); open ("myprog.in", O_RDONLY);
close (1); open ("myprog.out", O_WRONLY | O_CREAT, 0600);
#endif
while((scanf("%d",&liczba))==1)
{

if ((c=getchar())==EOF)
return 1;
for (i=0;i<=103;++i)
tabl=0;
i=0;

while(((c=getchar())!='\n') && (c!=EOF))
{

l=0;
while (licz[l]!=c)
++l;
tabl=l;
++i;

}

wysz(1,1000001);





}

}

[shamim]

Why did u make such an easy and short program so long.

For your information, my code is 152 bytes long and I got AC.

[epsilon0]

double can handle input more than that, 10^(+/-300)

i doubt it. double is something like 8 bytes on most hardware.

2 ^ 64 is roughly 10 ^ 20

how can this problem be solved with double?

i used a special structure to describe very large numbers, then i redefined operations like ADD MUL etc...

my program seems to work on test data but i got TLE

HELP

[UFP2161]

You're thinking double as a normal integer .. Remember, it keeps an exponent and some number of significant digits (15 for double, 7 for float) .. thus, the range for double is about 1.7E+/-308, which is actually enough for this problem using standard C functions.

[Dominik Michniewski]

Yes, but I think, that judge doesn't have tests for big values - in which you should print result as 50-digits number , which doesnt fit exactly in any floating variable ..

Best regards
DM

[bignad98]

This program is a one-liner for the most part, but the judge keeps giving me wrong answer with this code. I've tested it with other inputs and get correct outputs. what am i doing wrong?
[cpp]
long k;
short n;
double p;
while(cin >> n >> p)
{
if(p==1)
{ cout << 1 << endl; continue;}
if(n==1)
{ cout << p << endl; continue;}
k = exp( log(p)/n ) + 0.5;
// k performs automatic truncation to long, so add for rounding
cout << k << endl;
}[/cpp]

[Maarten]

My compiler says:

Code: Select all

113.cpp: In function `int main(int, char**)':
113.cpp:15: warning: assignment to `long int' from `double'
113.cpp:15: warning: argument to `long int' from `double'

Perhaps you should try get rid of these warnings first