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

venusaur
New poster
Posts: 4
Joined: Wed Apr 23, 2003 3:05 pm

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

User avatar
Sarmento
New poster
Posts: 15
Joined: Tue Apr 22, 2003 9:50 pm
Location: Lisboa, Portugal

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

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

113.Why I could got AC /

Post by 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
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by 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
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
Location: CS, AIUB, Dhaka, Bangladesh
Contact:

Post by 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.
[Tanzim Saqib]
-----------------------------
Problemsetter of 10490
Website: http://tanzim.tk

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

113

Post by r.z. »

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

Post by Hisoka »

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

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

Post by r.z. »

oh really thanks.....

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

have to learn so much

thanks.... :wink:

Rav
New poster
Posts: 27
Joined: Sat Jun 14, 2003 1:00 pm
Location: Polska Wrocław

Post by 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
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Why so long

Post by shamim »

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

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

epsilon0
Experienced poster
Posts: 112
Joined: Tue Nov 12, 2002 11:15 pm
Location: Paris, France.

Post by epsilon0 »

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:

Post by 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
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

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

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

another 113 problem

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

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

Post Reply

Return to “Volume 1 (100-199)”