Problem:


Score : 300 points

Problem Statement

Let f(n) be the number of triples of integers (x,y,z) that satisfy both of the following conditions:

1 \leq x,y,z

x^2 + y^2 + z^2 + xy + yz + zx = n

Given an integer N, find each of f(1),f(2),f(3),\ldots,f(N).

Constraints

All values in input are integers.

1 \leq N \leq 10^4

Input

Input is given from Standard Input in the following format:

N

Output

Print N lines. The i-th line should contain the value f(i).

Sample Input 1

20

Sample Output 1

0
0
0
0
0
1
0
0
0
0
3
0
0
0
0
0
3
3
0
0

For n=6, only (1,1,1) satisfies both of the conditions. Thus, f(6) = 1.

For n=11, three triples, (1,1,2), (1,2,1), and (2,1,1), satisfy both of the conditions. Thus, f(6) = 3.

For n=17, three triples, (1,2,2), (2,1,2), and (2,2,1), satisfy both of the conditions. Thus, f(17) = 3.

For n=18, three triples, (1,1,3), (1,3,1), and (3,1,1), satisfy both of the conditions. Thus, f(18) = 3.



Sample input:
20


Sample output:
0
0
0
0
0
1
0
0
0
0
3
0
0
0
0
0
3
3
0
0

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, product
import sys
import math
import bisect

def LI(): return [int(x) for x in sys.stdin.readline().split()]


def I(): return int(sys.stdin.readline())


def LS(): return [list(x) for x in sys.stdin.readline().split()]


def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res


def IR(n):
    return [I() for i in range(n)]


def LIR(n):
    return [LI() for i in range(n)]


def SR(n):
    return [S() for i in range(n)]


def LSR(n):
    return [LS() for i in range(n)]


sys.setrecursionlimit(1000000)
mod = 1000000007


def solve():
    n = I()
    def f(n):
        count = 0
        nli = set([i for i in range(1,n+1)])
        for x in nli:
            for y in nli:
                for z in nli:
                    if x**2 + y**2 + z**2 + x*y + y*z + z*x == n:
                        count += 1
        return count

    for i in range(1,n+1):
        print(f(i))
    return


if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools
input = sys.stdin.readline
 
N=int(input())
 
A=[]
for i in range(99):
    A.append(i+1)
 
D=list(itertools.combinations_with_replacement(A, 3))
S = []
#print(len(D))
for i in range(len(D)):
    if D[i][0]+D[i][1]+D[i][2]<123:
        S.append(D[i])

     


#print(len(D))
for j in range(1,N+1):
    count=0
    for sa in S:
        if (sa[0]+sa[1]+sa[2])**2-sa[0]*sa[1]-sa[1]*sa[2]-sa[2]*sa[0]==j:
            if sa[0]!=sa[1] and sa[1] !=sa[2]:
                
                count+=6
            elif sa[0]==sa[1] and sa[1]==sa[2]:
                count+=1
            else:
                count+=3
 
    print(count)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())


for n in range(1,N+1):
    cnt = 0
    for x in range(1,105):
        for y in range(1, 105):
            for z in range(1, 105):
                if x**2 + y**2 + z**2 + x*y + y*z + z*x == n:
                    cnt +=1
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
c = 0
n = 0
list = []
for l in range(1,N+1):
    list = []
    for i in range(1,int(N**0.5)):      
        for j in range(1,int(N**0.5)):
            for k in range(1,int(N**0.5)):
                if i*i + j*j + k*k + i*j +j*k + i*k == l:
                    list.append(1)
                    break;
    print(sum(list))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import math

N = int(input())
f = [0] * N
for i in range(1, N+1):
  count = 0
  for x in range(1, i):
    for y in range(x, i):
      z = i-x-y
      if z < y:
        break
      n = x**2 + y**2 + z**2 + x*y + y*z + z*x
      if z > math.sqrt(n + 1):
        break
      if n <= N:
        if x == y and x == z:
          f[n-1] += 1
        elif x == y or y == z:
          f[n-1] += 3
        elif x != y and x != z and y != z:
          f[n-1] += 6
for i in f:
  print(i)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
c = 0
n = 0
list = []
for l in range(1,N+1):
    list = []
    for i in range(1,int(N**0.5)):
        if i*i > l:
            break;       
        for j in range(1,int(N**0.5)):
            a = i*i + j*j + i*j
            for k in range(1,int(N**0.5)):
                if i*i + j*j + k*k + i*j +j*k + i*k == l:
                    list.append(1)
                    break;
    print(sum(list))

Submission status: Time Limit Exceeded

Solution code:
import math
N = int(input()) 

for n in range(1, N + 1):
    sum = 0
    root = int(math.sqrt(2*n))
    max = int(math.sqrt(2*n/3))
    if n<4:
        print(sum)
        continue
    for u in range(2, max + 1):
        for v in range(u, root + 1):
            if int(u*u + v*v) >= int(2*n):
                break
            for w in range(v, root + 1):
                if int(u*u + v*v + w*w) > int(2*n):
                    break
                if int(u*u + v*v + w*w) == int(2*n):
                    x = int((u - v + w)/2)
                    y = int((u + v - w)/2)
                    z = int((-u + v + w)/2)
                    if (x > 0 and y > 0 and z > 0):
                        if x == y and y == z:
                            sum += 1
                        elif x == y or y == z or z == x:
                            sum += 3
                        else:
                            sum += 6
                        
    print(sum)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
ans = [0] * (n + 1)
loop = int((n/6) ** 1.5) + 1

def f(i, j, k):
    return i ** 2 + j ** 2 + k ** 2 + i*j + j*k + k*i

for i in range(1, loop+1):
    for j in range(1, loop+1):
        for k in range(1, loop+1):
            res = int(f(i, j, k))
            if res <= n:
                ans[res] += 1

for a in ans[1:]:
    print(a)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# スペース区切りの整数の入力
N = int(input())

Ans = 0

for i in range(1,N+1):
  if int(float(i)**0.5) <= 1:
    rMax = 1
  else:
    rMax = int(float(N)**0.5)  

  for x in range(1,rMax+1):
    if x**2 > i:
      break
    else:
      for y in range(1,rMax+1):
        if x**2 + y**2 > i:
          break
        else:
          for z in range(1,rMax+1):
            if x**2 + y**2 + z**2 > i:
              break
            else:
              if x**2 + y**2 + z**2 + (x * y) + (y * z) + (z * x) == i:
                Ans += 1
  
  print(Ans)
  Ans = 0

Submission status: Time Limit Exceeded

Solution code:
import math
N = int(input()) 

for n in range(1, N + 1):
    sum = 0
    root = int(math.sqrt(2*n))
    max = int(math.sqrt(2*n/3))
    if n<4:
        print(sum)
        continue
    for u in range(2, max + 1):
        for v in range(u, root):
            if int(u*u + v*v) >= int(2*n):
                break
            for w in range(v, root):
                if int(u*u + v*v + w*w) > int(2*n):
                    break
                if int(u*u + v*v + w*w) == int(2*n):
                    x = int((u - v + w)/2)
                    y = int((u + v - w)/2)
                    z = int((-u + v + w)/2)
                    if (x > 0 and y > 0 and z > 0):
                        if x == y and y == z:
                            sum += 1
                        elif x == y or y == z or z == x:
                            sum += 3
                        else:
                            sum += 6
                        
    print(sum)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [0]*(n+1)
for n in range(1, n+1):
    for i in range(1, 102):
        for j in range(1, 102):
            for k in range(1, 102):
                if n == (i*i + j*j + k*k + i*j + j*k + i*k):
                    a[n]+=1
for x in a[1:]:
    print(x)

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline

def calc(n):
    for i in range(1,int((n+1)**0.5)):
        for j in range(1,int((n+1)**0.5)):
            for k in range(1, int((n+1)**0.5)):
                if (i+j+k)**2 - i*j - j*k - k*i == n:
                    if i == j == k:
                        return 1
                    else:
                        return 3
    return 0    

def main():
    n = int(input())
    for i in range(1,n+1):
        print(calc(i))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())


for i in range(1, N+1):
    sum = 0

    range_x = int((i-5)**0.5)+1 if i-5 >0 else 0
    s = set()
    for x in range(1, range_x):
        flag = False
        if x in s:
            continue
        range_y = int((i-x**2-x-3)**0.5)+1 if i-x**2-2*x-2 > 0 else 0
        for y in range(x, range_y):
            if y in s:
                continue
            D = (x+y)**2-4*(x*x+y*y+x*y-i)
            if D >0:
                z = (-(x+y)+D**0.5)/2
                # print(z)
                if z//1 == z and 1<=z:
                    z = int(z)
                    num = len(set([x,y,z]))
                    sum += 6 if num == 3 else 3 if num==2 else 1
                    s = s | set([x,y,z])
                    break

    print(sum)

Submission status: Time Limit Exceeded

Solution code:
import math

N = int(input())

used = [[0]*3]*N

count = [0] * N


if N <= 5:
    for x in range(N):
        print(count[x])
else:
    for n in range(6,N):
        rtn = int(math.sqrt(n))
        #print(n)
        for x in range(1,rtn):
            #print(x)
            xx = x**2
            if xx <= n - 5:
                #print("xpath")
                for y in range(1,rtn):
                    #print(x,y)
                    xy = x*y
                    yy = y**2
                    ysum = xx+yy+xy
                    if ysum >= n:
                        break
                    if ysum <= n-3:
                        #print("ypath")
                        for z in range(1,rtn):
                            #print(x,y,z)
                            zz = z**2
                            xz = x*z
                            yz = y*z
                            result = ysum+zz+xz+yz
                            if result > n:
                                break
                            if result == n:
                                count[n-1] += 1
                                #print("zpath")
                                used.append
    for x in range(N):
        print(count[x])

Submission status: Time Limit Exceeded

Solution code:
import math
n = int(input())

for i in range(1, n+1):
  count = 0
  upper = int(math.sqrt(i))
  lower = int(math.sqrt(i/6))
  for x in range(lower, upper):
    for y in range(lower, x+1):
      for z in range(lower, y+1):
        if x*x + y*y + z*z + x*y + y*z + z*x == i:
          if x == y and y == z and z == x:
          	count += 1
          else:
            count += 3
            
  print(count)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import math

def A(n):
    return [i**2 for i in range(2, int(math.sqrt(2*n))) if i**2 <= n-8]

N  = int(input())


count = 0

array = A(2*N)

for n in range(1, N+1):
    # print(f"n = {n}")
    count = 0
    for a in array:
        for b in array:
            c = 2*n - (a + b)
            if(c >= 4 and c <= 2*n-8 and (c ** .5).is_integer()):
                X = math.sqrt(a)
                Y = math.sqrt(b)
                Z = math.sqrt(c)
                x = (X-Y+Z)/2
                y = (X+Y-Z)/2
                z = (-X+Y+Z)/2
                if(x.is_integer() and y.is_integer() and z.is_integer()):
                    if(x >= 1 and y >= 1 and z >= 1):
                        count += 1
    print(count)

Submission status: Time Limit Exceeded

Solution code:
def calc(n):
    c = 0
    for x in range(1,int(n**.5)+1):
        for y in range(1,int(n**.5)+1):
            for z in range(1,int(n**.5)+1):
                if n == x**2+y**2+z**2+x*y+y*z+z*x:
                    c += 1
    print(c)
    
    
n = int(input())
for i in range(1,n+1):
    calc(i)

Submission status: Time Limit Exceeded

Solution code:
def f(n):
  count = 0
  for i in range(1,n+1):
    if i >= 100:
      break
    for j in range(i,n+1):
      if j >= 100:
        break
      for l in range(j,n+1):
        if l >= 100:
          break
        if (i+j)**2 + (j+l)**2 + (l+i)**2 == 2*n:
          if i == j == l:
            count += 1
          elif i == j or j == l or l == i:
            count += 3
          else:
            count += 6
  return (count)
n = int(input())
for i in range(1,n+1):
  print(f(i))

Submission status: Time Limit Exceeded

Solution code:
import math

N = int(input())

used = [[0]*3]*N

count = [0] * N


if N <= 5:
    for x in range(N):
        print(count[x])
else:
    for n in range(6,N):
        rtn = int(math.sqrt(n))
        #print(n)
        for x in range(1,rtn):
            #print(x)
            xx = x**2
            if xx <= n - 5:
                #print("xpath")
                for y in range(1,rtn):
                    #print(x,y)
                    xy = x*y
                    yy = y**2
                    ysum = xx+yy+xy
                    if ysum <= n-3:
                        #print("ypath")
                        for z in range(1,rtn):
                            #print(x,y,z)
                            zz = z**2
                            xz = x*z
                            yz = y*z
                            result = ysum+zz+xz+yz
                            if result > n:
                                break
                            if result == n:
                                count[n-1] += 1
                                #print("zpath")
                                used.append
                    else:
                        break
    for x in range(N):
        print(count[x])

Submission status: Time Limit Exceeded

Solution code:
import itertools
import math
import fractions
import functools
import copy
from collections import deque
from functools import reduce
from decimal import Decimal


def main():
    n = int(input())

    def f(num):
        ans = 0
        x = 1
        while x**2 < num:
            y = 1
            while x**2 + y**2 + x*y < num:
                z = 1
                while x**2 + y**2 + z**2 + x*y + y*z + z*x <= num:
                    if x**2 + y**2 + z**2 + x*y + y*z + z*x ==num:
                        ans +=1
                    z += 1
                y += 1
            x += 1
        return ans

    for i in range(1, n+1):
        print(f(i))
    

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
def f(a, b, c):
    return a**2 + b**2 + c**2 + a*b + b*c + c*a

for i in range(1, N+1):
    if i < 6:
        print(0)
    else:
        x, y, z = 0, 0, 0
        ans = 0
        while True:
            x += 1
            y = 0
            z = 0
            if f(x,y,z) > i:
                break
            while True:
                y += 1
                z = 1
                s = f(x,y,z)
                if s > i:
                    break
                while s <= i:
                    if s == i:
                        ans += 1
                        break
                    z += 1
        print(ans)