Uva 256 - Quirksome Squares

 1  /*
 2  Problem link
 3  Type: Complete Search
 4  Algorithm:
 5      Just do as it says
 6  */
 7  #include <iostream>
 8  #include <cstdio>
 9  #include <cstring>
10  #include <cmath>
11  
12  using namespace std;
13  const double EPS = 1E-9;
14  
15  int GetLength(int num);
16  bool IsQuirk(int x, int len);
17  
18  int main()
19  {
20      int input;
21      while (scanf("%d", &input) != EOF) {
22          int maxx = (int)sqrt((int)pow(10,input) - 1);   // The upper bound for the search
23          for (int i = 0; i <= maxx; i++) {
24              if (IsQuirk(i*i,input)) {
25                  int e = GetLength(i*i);
26                  while (e < input) { printf("0"); e++; } // Add preceding zeroes
27                  printf("%d\n",i*i);
28              }
29          }
30      }
31      return 0;
32  }
33  
34  int GetLength(int num) {
35      if (num == 0) return 1;
36      int result = 0;
37      while (num) {
38          result++;
39          num /= 10;
40      }
41      return result;
42  }
43  
44  bool IsQuirk(int x, int len) {
45      if ((int)sqrt(x) * (int)sqrt(x) != x) return false;
46      int half = (int)(pow(10,len/2) + EPS);          // Watch out for floating point error!!
47      if (x/half + x%half == (int)sqrt(x)) return true;
48      return false;
49  }