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.

  • 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))