## 113 - Power of Cryptography

Moderator: Board moderators

venusaur
New poster
Posts: 4
Joined: Wed Apr 23, 2003 3:05 pm
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
New poster
Posts: 15
Joined: Tue Apr 22, 2003 9:50 pm
Location: Lisboa, Portugal
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
-----------------
Jo

tzzx
New poster
Posts: 14
Joined: Thu May 15, 2003 6:29 am

### 113.Why I could got AC /

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
writeln(exp(ln(p)/n):1:0);
end;
end.
[/pascal][/pascal]

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
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
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

Tanzim-Saqib
New poster
Posts: 10
Joined: Thu Jun 05, 2003 5:23 pm
Contact:
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.
[Tanzim Saqib]
-----------------------------
Problemsetter of 10490
Website: http://tanzim.tk

r.z.
Learning poster
Posts: 56
Joined: Thu Jun 05, 2003 1:57 pm

### 113

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

what is the algorithm......

Hisoka
Experienced poster
Posts: 120
Joined: Wed Mar 05, 2003 10:40 am
Location: Indonesia
double can handle input more than that, 10^(+/-300)

r.z.
Learning poster
Posts: 56
Joined: Thu Jun 05, 2003 1:57 pm
oh really thanks.....

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

have to learn so much

thanks....

Rav
New poster
Posts: 27
Joined: Sat Jun 14, 2003 1:00 pm
Location: Polska Wroc&#322;aw
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
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

### Why so long

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
Experienced poster
Posts: 112
Joined: Tue Nov 12, 2002 11:15 pm
Location: Paris, France.
Hisoka wrote: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
We never perform a computation ourselves, we just hitch a ride on the great Computation that is going on already. --Tomasso Toffoli

UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:
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
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
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
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

New poster
Posts: 6
Joined: Mon Sep 15, 2003 3:21 am
Location: Charleston, S.C.
Contact:

### another 113 problem

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]
"Moral victories are for girls!" -- Shawn Kiernan

"You can't spell geek without EE..." -- Larkin Gentry

Maarten
Experienced poster
Posts: 108
Joined: Sat Sep 27, 2003 5:24 pm
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