Saturday, January 24, 2015

113: power of cryptography

I don't like this problem because it dwells more on technicality than logic. The first time I saw this problem, I did not know how to solve it because I thought that you're suppose to only use integers. The problem said that the program should be able to handle numbers as large as p = 10^101, but integers can only handle up to 2^64 for unsigned long long int. 2^64 is smaller than 10^101. And so I was stuck. I was thinking do I have to use a class for very big integers.

I looked at the discussions in the Internet and discovered that you could actually just use double type, which is kind of smart. double type can handle numbers as large as 10^300. float type however cannot do because float I think can only handle up to 10^38.

Using double gives us a whole range of mathematical powers. We can use the cmath library to raise the number p to the fraction (1/n) to get the nth root of p.

I read the forums and they said that the correct way to read a double using scanf is to use %lf. In printing the double, I initially used %d and casting the double to an integer. Unfortunately, this did not work and I got wrong answers. probably because the specs mentions that k should be able to handle up to 10^9, while %d which corresponds to an integer can only handle up to 2^31.

Again I consulted the forums and they told me to use %.0lf in printf. The .0 corresponds to having no decimals after the decimal point.

After doing these things I still got a wrong answer. As you can see, this can be very frustrating, getting wrong answers every now and then because of technicality in the C language.

The way I got input was something like this:

fgets(line, 100, stdin);
sscanf(line, "%lf", &n);
fgets(line, 100, stdin);
sscanf(line, "%lf, &p);

I also checked if fgets returned true whenever I used it. Unfortunately again, I got wrong answers. Very frustrating problem.

So, again after consulting the forums, they recommended I use while (scanf("%lf %lf", &n, &p)==2). So, I used this syntax and it worked and I finally got the accepted AC response.

I think, however, that this is unfair because the problem specs mentions that each integer input will be on a line of its own. This means that for every line input, there will only be one integer. Using scanf("%lf %lf, &n, &p), however, means that a line input can have two integers already which is a contradiction from the specs. This is why I feel the problem is ugly and very frustrating because it deals with technicality instead of logic.

#include "stdio.h"
#include "cmath"

int main() {
  char line[100];
  double n, p, k;

  while (scanf("%lf %lf", &n, &p) == 2) {
    k = pow(p, 1.0/n);
    printf("%.0lf\n", k);
  }

  return 0;
}


No comments:

Post a Comment