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

zbogi
New poster
Posts: 15
Joined: Thu Aug 29, 2002 11:00 pm
Location: Bulgaria

I am not sure you should write this

Post by zbogi » Sun Sep 15, 2002 7:13 pm

I really don`t think that it is good to ask such a questions here. After all, if algorith is esential part of the problem. :x
Any way I will give you a hint. There is NO number theory for this problem. Just (almost) brute force. :wink:
Any way I still think that such question should not be asked here.
Tsvetan Bogdanov.
from Brain Explorer - Sofia University - FMI 2
e-mail: zbogi@yahoo.com

minskcity
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver

#113

Post by minskcity » Tue Mar 04, 2003 10:10 pm

I submit two variations of code to judge - first solution terminates if p == 0, second does not make this check. First solution gets WA (I think because p == 0). Second - TLE (my solution runs forever, if p == 0). I think problem here is with my input method. Can anybody find an input that will cause my code to run forever or print WA? Input should follow input rules provided in problem description http://acm.uva.es/p/v1/113.html.
One more time: my code is sure that first judge's input for p is 0...

By the way, my solution solves samples correctly.

[cpp]#include <iostream.h>
#include <stdio.h>
const unsigned long base = 10000;
const unsigned long N = 100;

struct my_long{
unsigned long digit[N];
};

my_long incr[N*8];

int lll(my_long in){
int i = N;
while((!in.digit)&&(i > 0)) i--;
return i;
}

void print(my_long &ml){
int i = N - 1;
while((!ml.digit) && (i > 0)) i--;
cout << ml.digit;
i--;
while(i >= 0){
if(ml.digit < 1000) cout << "0";
if(ml.digit < 100) cout << "0";
if(ml.digit < 10) cout << "0";
cout << ml.digit;
i--;
};
cout << endl;
}

void shift(my_long &ml){
for(int i = 0; i < N; i++){
ml.digit[i + 1] += ml.digit/base;
ml.digit %= base;
}
}

void add(my_long &ml, unsigned long in){
ml.digit[0] += in;
shift(ml);
}

void add(my_long &in1, my_long &in2){
for(int i = 0; i < N; i++) in1.digit += in2.digit[i];
shift(in1);
}

void mult(my_long &ml, unsigned long in){
for(int i = 0; i < N; i++) ml.digit[i] *= in;
shift(ml);
}

void move_left(my_long &ml, int in){
int i;
for(i = N - 1; i >= in; i--) ml.digit[i] = ml.digit[i - in];
for(i = i; i >= 0; i--) ml.digit[i] = 0;
}

void mult(my_long &in1, my_long in2){
my_long out;
for(int i = 0; i < N; i++) out.digit[i] = 0;
my_long temp;
for(int i = 0; i < (N/2 - 3); i++){
temp = in1;
mult(temp,in2.digit[i]);
move_left(temp,i);
add(out,temp);
}
in1 = out;
}

int power(my_long &n, int pow){
my_long temp;
temp = n;
for(int i = 1; i < pow; i++) mult(n,temp);
return 1;
}

void create_incr(){
my_long temp;
for(int i = 0; i < N; i++) temp.digit[i] = 0;
temp.digit[0] = 1;
for(int i = 0; i < N*8; i++){
incr[i] = temp;
mult(temp,3);
}
}

int less_or_equal(my_long in1, my_long in2){
for(int i = N - 1; i >= 0; i--){
if(in1.digit[i] < in2.digit[i]) return 1;
if(in1.digit[i] > in2.digit[i]) return 0;
}
return 1;
}

int equal(my_long in1, my_long in2){
for(int i = 0; i < N; i++) if(in1.digit[i]!=in2.digit[i]) return 0;
return 1;
}

my_long p,answer,temp;
unsigned long n;
char buffer[200];

void find_answer(){
int i,flag;
for(int i = 0; i < N; i++) temp.digit[i] = 0;
answer = temp;

while(1){
i = 0;
do{
temp = answer;
add(temp,incr[i]);
flag = power(temp,n);
if(equal(temp,p)){
add(answer,incr[i]);
print(answer);
return;
}
i++;
}while((less_or_equal(temp,p))&&(flag));

add(answer,incr[i - 2]);
}
}

int main(){
int k;
create_incr();
while(cin >> n){
gets(buffer);
k = 0;
for(int i = 0; i < N; i++) p.digit[i] = 0;
while(buffer[k]){
mult(p,10);
add(p,buffer[k] - 48 );
k++;
}
if((p.digit[0] == 0)&&(lll(p) < 1)) return 0; //This line checks if p == 0 *********
find_answer();
}
return 0;
}[/cpp]

minskcity
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver

Post by minskcity » Thu Mar 06, 2003 10:31 pm

As far as I know pow and exp are applied to doubles, doubles have presision of 15 decimal digits, long double around 19. What if input is:

Code: Select all

2
number 100 digits long
The output should be around 50 digits long. If I use long double all digits after 20th will be zeros, which means incorrect answer in most cases... :(
Do you mean Judge don't have such inputs, so I can use just doubles or long doubles to get AC? (Without implementing long numbers arithmetic) :-?
PS: I can write a code that will solve samples, using only long double, but that code will not solve inputs described above...

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:

Post by yiuyuho » Fri Mar 07, 2003 8:47 am

look at it this way:

p might be very large, but k is not.
we use k=exp(ln(p)/n)

since k is guarateed to be integer, the precision of p from input will be neglected, for p to be large, n need to be large also and k is always a small number <=10^9

since n is large when p is large, then k^n and k^(n+/-1) will have a big difference.

unsigned long double will be find.

Hisoka
Experienced poster
Posts: 120
Joined: Wed Mar 05, 2003 10:40 am
Location: Indonesia

Post by Hisoka » Fri Mar 07, 2003 11:11 am

with long double we can get input more than 100 digit. and the output only a small digit number. :)
when I try to solved it before, my mind is same like yours, because I forgot about that. :wink:

minskcity
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver

Post by minskcity » Fri Mar 07, 2003 11:55 am

Now I see. I did not notice that k <= 10^9 when I read problem description first time. :-?
Anyway, if anybody can test my solution and find an input resulting in WA or TLE, that would be great.

When I had problems with 105 someone told me that #105 is the easiest problem :lol: he was so wrong.
my AC'd code:
[cpp] while(cin >> n >> p) cout << pow(p,1/n) << endl;[/cpp]
I can't understand what a problem like this do in problem set :roll: .

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:

Post by yiuyuho » Fri Mar 07, 2003 9:30 pm

Hisoka wrote:with long double we can get input more than 100 digit.
are you sure? If so, please prove it. Because I was always believing in the fact that it only have about 17 digits precision

minskcity
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver

Post by minskcity » Fri Mar 07, 2003 10:12 pm

Hisoka wrote:
with long double we can get input more than 100 digit.

Hisoka is right - of cause we can get that input (using double we can get 308 digit input), but with finite precision. :wink:
By the way, there is no solution in the world that will guarantee you infinite precision.

[cpp]double d;
cin >> d;[/cpp]
try this code it will prove you all you want. 8)

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:

Post by yiuyuho » Sat Mar 08, 2003 11:30 pm

Alright, may be I should clearify my statement: double can only give you about 17 significant digits, right?

minskcity
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver

Post by minskcity » Sat Mar 08, 2003 11:50 pm

Double gives you at least 15 significant digits (you can get more, depending on compiler). Long double gives you at least double's precision(One more time: you can get more, depending on compiler). Usually double - 64bit, long double - 80bit. It's not difficult to calculate what maximum possible precision is. :wink:

You can get maximum 24 digits if you put an integer in 80bit.
In practice you will not get even 20 significant digits. But some information taken from up to 308 digits will be stored in double. :wink:

rbuchan
New poster
Posts: 27
Joined: Fri Feb 28, 2003 7:59 am
Contact:

Off subject

Post by rbuchan » Sun Mar 09, 2003 3:49 am

If anyone has test data and correct answers for 173, that would be of a big help. I keep getting a wrong answer, but the problem here is not the messages being correct, but the order of the messages that I am concerned about.

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

Really Big Numbers in Java

Post by Sarmento » Wed Apr 23, 2003 5:10 pm

What's the data type that supports the biggest numbers in java? Is it double? I'm getting WA from the judge and I guess it's because of that.....

Thanks,

joao sarmento
-----------------
Jo

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

Post by Sarmento » Wed Apr 23, 2003 5:11 pm

By the way, the prob is 113...
-----------------
Jo

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

Post by venusaur » Wed Apr 23, 2003 6:05 pm

double is right, but real number can't be used in Problem #113 . Problem #113 should be solved ONLY with integer.

There is a class that supports such a big integer: java.math.BigInteger; but there is a problem:

This class isn't supproted yet in the judge compiler; (I think) judge compliler supports only JDK1.1 classes, and BigInteger is JDK1.2 feautre

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

Post by Sarmento » Wed Apr 23, 2003 6:22 pm

Then how am I supposed to solve this one using java? It's impossible? Can't I use double and then cast it to int?
-----------------
Jo

Post Reply

Return to “Volume 1 (100-199)”