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.

Sort by

recency

|

25 Discussions

|

  • bhavikgevariya
     + 0 comments

    Your programme can be tested using these test cases.

    5
10000
100000
500000
750000
1000000

Output:
2383
22285
106666
158345
209566

  • APovalyaev
     + 0 comments

    It's strange. I got the right answer for 10**6 on projecteuler, but TestCase2 won't pass.

    Here is my code:

    # Enter your code here. Read input from STDIN. Print output to STDOUT
from bisect import bisect_left

T = int(input().rstrip())
u_res = []

def SUM1(n):
    return n*n

input_k = []
max_k = 0
for _ in range(0, T):
    k = int(input().rstrip())
    if k > max_k:
        max_k = k;
    input_k.append(k)

if 1:
    rest = dict()
               
    i1 = 1
    sum1 = SUM1(i1)
    stop = False
    while not stop:
        
        if sum1 > max_k:
            stop = True    
        
        i2 = i1+2
        sum2 = SUM1(i2)
        while sum2 - sum1 <= max_k:
            stop = False
            
            if 1:
                if sum2-sum1 in rest:
                    rest[sum2-sum1] += 1
                else:
                    rest[sum2-sum1] = 1
            i2 += 2
            sum2 = SUM1(i2)
            
        i1 += 1
        sum1 = SUM1(i1)

    
s_res = sorted(rest.items())

u_res = []
total_value = 0
for key, value in s_res:
    if value <= 10:
        total_value += 1
    u_res.append((key, total_value))

len_ures = len(u_res)

for k in input_k:
    
    i = bisect_left(u_res, (k,10**6))

    r = 0
    if i >= len_ures:
        i -= 1
    if u_res[i][1] > k:
        if i > 0:
            i -= 1
            r = u_res[i][1]
        else:
            r = 0
    else:
        r = u_res[i][1]
            
            
    print("{}".format(r))

  • gautamsw5
     + 0 comments

    Useless problem Time limit excceds by small margin even for O(N) pre-computation and O(1) queries Tried 6-7 languages, worked in Python 2

  • robin_vezina
     + 0 comments

    As 100% solutions are already posted, here is in Java :

    import java.io.BufferedInputStream;
import java.io.BufferedOutputStream;
import java.io.PrintStream;
import java.util.Scanner;

public class Solution {
  public static void main(String[] args) throws Exception {
    final int[] s = new int[250_001];
    for (int h = 1; h < 501; h++)
      for (int p = h * h + h; p < s.length; p += h)
        s[p]++;

    for (int i = 2, sum = 0; i < s.length; i++)
      s[i] = sum += s[i] <= 10 ? 1 : 0;

    try (Scanner in = new Scanner(new BufferedInputStream(System.in))) {
      try (PrintStream out = new PrintStream(new BufferedOutputStream(System.out))) {
        for (int T = in.nextInt(); T > 0; T--)
          out.println(s[in.nextInt() >> 2]);
      }
    }
  }
}

  • 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;
}