miércoles, 21 de septiembre de 2011

11428 - Cubes Solution

#include<iostream>
#include<cstdio>
#define db(a) cout << #a << " = " << a << endl;
#define db2(a, b) cout << #a << " = " << a << " " << #b << " = " << b << endl;
using namespace std;
int cubo(int a) {
 return a * a * a;
}
int main() {
   int n, x, y;
   while(scanf("%d", &n)) {
    if(n == 0) break;
    x = y = 0;
    while(1) {
     if(n == cubo(x) - cubo(y)){
      printf("%d %d\n", x, y);
      break;
     }
     if(n < cubo(x) - cubo(y)) y++;
     if(n > cubo(x) - cubo(y)) x++;
      if(cubo(x) - cubo(y) == 0 || x >= 60 || y>= 59) {
          printf("No solution\n");
          break;
      }
    }
   }
  return 0;
}

I just simply iterate looking for a pair x, y that satisfy n = x^3 - y^3 and I do it until
x >= 60 || y>= 59 because the diference between them is greater than 10,000 this means that
there is no solution.
for example if n = 1 then:
1 = 1^3 - 0^3 then printf "1 0"
2 = 0^3 - 0^3 doesn't match ... so I keep it up looking for the next candidate
2 = 1^3 - 0^3 equal to 1 so also, doesn't match again and as this is less than n = 2 x must be greater so increase it again ...
2 = 2^3 - 0^3 this is 8 , we have exceeded so we need to modify y now. so we increse it.
2 = 2^3 - 1^3 this is 7 , this goes being the same (or be it greater) so y++ again
2 = 2^3 - 2^3 this becomes less than 2 again so it means that there is no solution

The same logic applies for the rest of numbers.
I hope your comments.

No hay comentarios:

Publicar un comentario