We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. All Contests
  2. ProjectEuler+
  3. Project Euler #174: Counting the number of "hollow" square laminae that can form one, two, three, ... distinct arrangements.
  4. Discussions

Project Euler #174: Counting the number of "hollow" square laminae that can form one, two, three, ... distinct arrangements.

  • Piyushgrwl
     + 1 comment

    Hi all, any suggestions for the optimization here. Should I precompute the results as well for every possible input?

    #include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;


int main() {
    static long long T, k, a[1000005], tiles, i, j, counter;
    vector <long long> N[11];
    scanf("%lld", &T);

    for (i = 3; i <= 1000000; i ++) {
        for (j = i - 2; j >= 1 && i-j <= 1000; j = j-2) {
            tiles = (i-j)*(i+j);
            if (tiles <= 1000000)
                a[tiles] ++;
        }
    }

    for (i = 8; i <= 1000005; i ++) {
        if (a[i] <= 10) {
            N[a[i]].push_back(i);
        }
    }

    while (T--) {
        scanf("%lld", &k);
        counter = 0;
        for (i = 1; i <= 10; i ++) {
            for (j = 0; N[i][j] <= k && j < N[i].size(); j ++) {
                counter ++;
            }
        }
        printf("%lld \n", counter);
    }
    return 0;
}