113 - Power of Cryptography

[zbogi]

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.
Any way I will give you a hint. There is NO number theory for this problem. Just (almost) brute force.
Any way I still think that such question should not be asked here.

[minskcity]

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]

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]

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]

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.

[minskcity]

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

[yiuyuho]

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]

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

[yiuyuho]

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

[minskcity]

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.

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.

[rbuchan]

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.

[Sarmento]

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

[Sarmento]

By the way, the prob is 113...

[venusaur]

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

[Sarmento]

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?