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:
N = int(input())

def func(N_max):
#     print(f'N_max:{N_max}')
    cnt = 0
#     flag = False
    ans = []
    
    total = 0

    for x in range(1, N_max):
        total = x**2
        if N_max < total:
            break
        for y in range(x, N_max):
            total = x**2 + y**2 + x*y
            if N_max < total:
                break

            for z in range(y, N_max):
                total = x**2 + y**2 + x*y + z**2+y*z+z*x
                if N_max < total:
                    break
                ans.append((total, change(len(set((x,y,z))))))

    return ans

def change(length):
    if length < 1:
        return 0
    elif length == 1:
        return 1
    elif length == 2:
        return 3
    elif length == 3:
        return 6

data = func(N)
for i in range(1, N+1):
    ans = 0
    for d in data:
        if d[0] == i:
            ans = d[1]
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
la=list(range(2,10**2+1))
l=[]
for i in range(len(la)):
  l.append(la[i]**2)
for n in range(1,N+1):
  if n<6:
    print(0)
  else:
    c=0
    for x in range(len(l)):
      if l[x]*3>2*n:
        break
      else:
        for y in range(x,len(l)):
          if l[x]+2*l[y]>2*n:
            break
          else:
            for z in range(y,len(l)):
              if l[x]+l[y]+l[z]>2*n:
                break
              else:
                
                if l[x]+l[y]+l[z]==2*n:
                  
                  if (x+y+z)%2==0 and x+y+2>z:
                      if l[x]==l[y] and l[y]==l[z]:
                        c+=1
                      elif l[x]==l[y] or l[y]==l[z]:
                        c+=3
                      else:
                        c+=6
                   
    print(c)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

for i in range(1,N+1):
  ans = 0
  if i < 6:
    print(ans)
  else:
    for a in range(2,int((2*i)**0.5+1)):
      for b in range(a,int((2*i-a**2)**0.5+1)):
        for c in range(b,int((2*i-a**2-b**2)**0.5+1)):
          #print(a,b,c)
          if a**2 + b**2 + c**2 > 2*i:
            ans = 0
          if a**2 + b**2 + c**2 == 2*i:
            if max(a,b,c) < a+b+c-max(a,b,c):
              if len({a,b,c}) == 1:
                ans = 1
              elif len({a,b,c}) == 2:
                ans = 3
              else:
                ans = 6
              #print(a,b,c)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
import math
import collections
import copy
from collections import deque 
from functools import reduce
from itertools import product

# input = sys.stdin.readline

def ff(N):
#     print("call ff{0}".format(N))
    if N > 100:
        n = int(np.sqrt(20))+5
    else:
        n = N
    cnt = 0
    for x in range(1, n+1):
        x2 = x**2
        for y in range(1, n+1):
            y2 = y**2
            xy = x * y
            tt = x2 + y2 + xy
            if tt > N:
                break
            for z in range(1, n+1):
                num = tt + z**2 + x*z + y*z
                if N == num:
                    cnt += 1
                elif N < num:
                    break
    return(str(cnt))    
    
N = int(input())    
n = int(np.sqrt(20))+1
pr = []
for i in range(1, N+1):
#     ff(i)
     pr.append(ff(i))
print("\n".join(pr))

Submission status: Time Limit Exceeded

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

n_max = int(math.sqrt(N))
l = [i for i in range(1, n_max)]
cand = []
score = []
for c in itertools.combinations_with_replacement(l, 3):
  cand.append(c[0]**2 + c[1]**2 + c[2]**2 + c[0]*c[1] + c[0]*c[2] + c[1]*c[2])
  if len(set(c)) == 3:
    score.append(6)
  elif len(set(c)) == 2:
    score.append(3)
  else:
    score.append(1)

for n in range(1, N+1):
  ans = 0
  if n in cand:
    ans += score[cand.index(n)]
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
i0 = 1
i1 = 1
i2 = 1
def checkTried(tried, toTry):
  for i in tried:
    #print(i[0] == toTry[0] , i[1] == toTry[1] , i[2] == toTry[2])
    if i[0] == toTry[0] and i[1] == toTry[1] and i[2] == toTry[2]:
      return True
  return False
def getChildren(arr):
  return [[arr[0]+1,arr[1],arr[2]],[arr[0],arr[1]+1,arr[2]],[arr[0],arr[1],arr[2]+1]]
def calc_(x,y,z):
  return (x**2)+(y**2)+(z**2)+(x*y)+(y*z)+(z*x)
def getRes(n):
  toTrys = [[1,1,1]]
  res = 0 
  tried = [] 
  while len(toTrys) !=0:

    toTry = toTrys.pop()
    c = calc_(toTry[0],toTry[1],toTry[2])
    wasTried = checkTried(tried,toTry)
    tried.append(toTry)
    if c == n and not wasTried:
      #print(toTry)
      res += 1
    if c < n and not wasTried:
      toTrys.extend(getChildren(toTry))

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

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
for i in range(1,n+1):
    cnt=0
    for x in range(1,101):
        if x**2>i:
            break
        for y in range(1,101):
            if y**2>i:
                break
            elif x**2+y**2>i:
                break
            for z in range(1,101):
                if z**2>i:
                    break
                if x**2+y**2+z**2+x*y+y*z+z*x==i:
                    cnt+=1
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import time
import itertools

N = int(input())
def function(x,y,z):
    return pow(x,2) + pow(y,2) + pow(z,2) + (x * y) + (x * z ) + (y * z)

start = time.time()

p = list(itertools.product(range(1,30),repeat=3))
a = []

for p_in in p:
    a.append(function(p_in[0],p_in[1],p_in[2]))

for n in range(1,N + 1):
    print(a.count(n))

elapsed_time = time.time() - start
# print("elapsed_time:{0}".format(elapsed_time) + "[sec]")

Submission status: Time Limit Exceeded

Solution code:
def f(n):
    if n < 2:
        return 0
    lim1 = int((n - 2) ** 0.5 - 1) + 1
    lim2 = int((-2 + (4 - 12 * (1 - n)) ** 0.5) / 6) + 1
    lim3 = int(n / 6) + 1

    result = set()
    for x in range(1, lim3):
        for y in range(1, lim2):
            if x > y:
                continue
            for z in range(1, lim1):
                if y > z:
                    continue
                if x ** 2 + y ** 2 + z ** 2 + x * y + y * z + z * x == n:
                    tmp = set([x, y, z])
                    if tmp not in result:
                        result.add(tuple(tmp))
    count = 0
    for s in result:
        if len(s) == 1:
            count += 1
        elif len(s) == 2:
            count += 3
        else:
            count += 6
    return count


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

Submission status: Time Limit Exceeded

Solution code:
import time
import itertools

N = int(input())
def function(x,y,z):
    return pow(x,2) + pow(y,2) + pow(z,2) + (x * y) + (x * z ) + (y * z)

start = time.time()

p = list(itertools.product(range(1,40),repeat=3))
a = []

for p_in in p:
    a.append(function(p_in[0],p_in[1],p_in[2]))

for n in range(1,N + 1):
    print(a.count(n))

elapsed_time = time.time() - start
# print("elapsed_time:{0}".format(elapsed_time) + "[sec]")

Submission status: Time Limit Exceeded

Solution code:
#from matplotlib import pyplot as plt
def binary_search(mn,mx,a,x,y):
    #リストlからaの値のインデックスをサーチする。
    #二分探索を可能にするためにはリストlはソートされていなければならない。
    z = (mx+1)//2
    low = mn
    high = mx+1
    while low <= high:
        temp = rule2(x,y,z)
        if temp == a:
            if z <= 0:
                return None
            return z
        elif temp < a:
            low = z + 1
        elif temp > a:
            high = z - 1

        z = (low + high) // 2
    return None

def rule2(x,y,z):
    return x ** 2 + y ** 2 + z**2 + x * y + y * z + z*x
def main():
    n = int(input())
    x = []
    y = []
    for i in range(1,n+1):
        #x.append(i)
        #y.append(f(i))
        print(f(i))
    #plt.scatter(x,y)
    #plt.show()


def f(n):
    counter = 0
    for x in range(1,n):
        if x ** 2 > n:
            break
        for y in range(x,n-x**2):
            if y < x:
                continue
            if x ** 2 + y ** 2 > n:
                break
            z = binary_search(y,n-x**2-y**2-x*y,n,x,y)
            if z == None:
                continue
            else:
                if rule2(x,y,z) == n:
                    if x == y and y == z and z == x:
                        counter += 1
                    elif x != y and y != z and z != x:
                        counter += 6
                    else:
                        counter += 3

    return counter


if __name__ == '__main__':
    main()

#6 24 54 96
#1  4  9 16
#18

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000000)
input = sys.stdin.readline
n=int(input())

a=[0]*(n+1)
for i in range(1,n+1):
    for j in range(1,42):
        for k in range(1,42):
            for l in range(1,42):
                if j**2+k**2+l**2+j*k+k*l+l*j==i:
                    a[i]+=1

for x in range(1,n+1):
    print(a[x])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

def func(N):
    count = 0
    for x in range(1, int(N**0.5)+1):
      for y in range(1, int(N**0.5)+1):
          if x <= y:
            D = (x+y)**2 -4*(x**2 + y**2+ x*y - N)
            if D > 0:
                z = -(x+y)/2 + D**0.5 / 2
                if z.is_integer() and z >= y :
                    if x == y and y == z:
                        count +=1
                    elif x== y and y != z:
                        count +=3
                    elif y == z and z != x:
                        count +=3
                    elif z == x and x != y:
                        count += 3
                    elif x != y and y != z:
                        count +=6
    return count
                
for n in range(1,N+1):
  print(func(n))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
ans = 0
tmp = []
for i in range(1,40):
    for j in range(1,57):
        for h in range(1,98):
            num = i*i + j*j + h*h + i*j + j*h +h*i
            tmp.append(num)
            num = 0

tmp.sort()


for i in range(1,N+1):
    print(tmp.count(i))

Submission status: Time Limit Exceeded

Solution code:
import math
n = int(input())
count = [0]*n
ch = []
for i in range(100):
    ch.append(i+1)
for i in range(1,n+1):
    for x in range(1,int(n**0.5)+1):
        for y in range(1,int(n**0.5)+1):
            b = x + y
            c = x*x + y*y + x*y - i
            if b**2 >= 4*c:
                if( (-b + math.sqrt(b**2-4*c))/2 ) in ch:
                    count[i-1] += 1
                elif( (-b - math.sqrt(b**2-4*c))/2 ) in ch:
                    count[i-1] += 1
for i in range(n):
    print(count[i])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
for n in range (1,N+1):
    cnt = 0
    for x in range (1,n+1):
        for y in range(x,n+1):
            for z in range(y,n+1):
                if x ** 2 + y ** 2 + z ** 2 + x * y + y * z + z * x == n:
                    cnt += 1
                    if x == y == z:
                        cnt += 0
                    elif x == y != z:
                        cnt += 2
                    elif x != y == z:
                        cnt += 2
                    else:
                        cnt += 5
                else:
                    cnt += 0
    print(str(cnt))

Submission status: Time Limit Exceeded

Solution code:
import itertools
import collections

n = int(input())
cnt = [0] * n
for i in range(1,n+1):
  l = [j for j in range(1, int(i**0.5)+1)]
  for x, y, z in itertools.product(l, l, l):
    if x**2 + y**2 + z**2 + x*y + y*z + z*x == i: cnt[i-1] += 1
for i in cnt:
  print(i)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys
import itertools
import math

def input():
    return sys.stdin.readline()


def resolve():
    n = int(input().rstrip())
    for m in range(1, n+1):

        max_n = math.sqrt(m)
        max_n = math.ceil(max_n)
        p = itertools.combinations_with_replacement(range(1,max_n+1), 3)

        ans_cnt = 0
        for v in p:
            #print(v)
            x, y, z = v
            ans = x*x + y*y + z*z + x*y + y*z + z*x

            if ans == m:
                if x == y == z:
                    ans_cnt += 1
                elif x == y or y == z or x == z:
                    ans_cnt += 3
                else:
                    ans_cnt += 6

        print(ans_cnt)



if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:

N=int(input())

n=1
while n<=N:
    tmp=n
    count=0
    for x in range(1,N+1):
        # if tmp != n:
        #     n+=1
        #     break
        x2=x**2
        if x2>n:
            break
        for y in range(1,N+1):
            # if tmp != n:
            #     break
            y2=y**2
            xy=x*y
            if y2 > n or xy > n or x2+y2>n or x2+xy > n or xy+y2 > n:
                break
            for z in range(1,N+1):
                z2=z**2
                xz=x*z
                yz=y*z
                if z2 > n or xz > n or yz > n or  x2+y2+z2>n or x2+z2>n or y2+z2>n or xy+yz>n or yz+xz>n or z2+xz>n or z2+xy>n or z2+yz>n:
                    tmp=n+1
                    break
                else:
                    comp=1
                    comp=x2+y2+z2+xy+yz+xz
                    if comp==n:
                        # print(x,y,z,n)

                        count+=1
    n+=1

    print( count)
    # print(n, count)

Submission status: Time Limit Exceeded

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

def judge(n, x=1, y=1, z=1, l=[]):
    num = 0
    x_th = math.ceil(math.sqrt(n) / 3) + 1
    #print('x_th: ', x_th+1)
    for x_i in range(x, x_th+1):
        #print('x_i: ', x_i)
        for y_i in range(x_i, x_th+1):
            y_th = n - x_i**2 + y_i**2 + x_i*y_i
            #print('y_i: ', y_i)
            #print('y_th: ', y_th)
            if y_th < 0:
                break
            for z_i in range(y_i, x_th+1):
                #print('z_i: ', z_i)
                result = x_i**2 + y_i**2 + z_i**2 + x_i*y_i + y_i*z_i + z_i*x_i
                #print('result: ', result)
                if result > n:
                    break
                elif result == n:
                    if x_i != y_i != z_i:
                        num += 6
                    elif x_i == y_i != z_i or x_i != y_i == z_i:
                        num += 3
                    elif x_i == y_i == z_i:
                        num += 1
                    #print('num: ', num)
    return num

#fn = judge(18, l=[])
#print(fn)
for i in range(1, n+1):
    fn = judge(i, l=[])
    print(fn)

Submission status: Time Limit Exceeded

Solution code:
from math import sqrt
N=int(input())
num=1
def checker(n):
    hoge=n
    if hoge>2:
        hoge=n-2
    count=0
    x=1
    for a in range(int(sqrt(hoge))):
        y=1
        for b in range(int(sqrt(hoge))):
            z=1
            for c in range(int(sqrt(hoge))):
                ans=x*x+y*y+z*z+x*y+x*z+z*y
                if ans==n:
                    count=count+1
                z=z+1
            y=y+1
        x=x+1
    return count
for i in range(N):
    print(checker(num)) 
    num=num+1

Submission status: Time Limit Exceeded

Solution code:
import math
N = int(input())
for n in range(1,N+1):
    r_n = math.floor(math.sqrt(n))
    count = 0
    if(n >= 6):
        for x in range(1,r_n):
            for y in range(1,r_n):
                for z in range(1,r_n):
                    if (x*x + y*y + z*z + x*y + y*z + z*x) == n:
                        count+=1
    print(count)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

def f(x,y,z):
    return x**2 + y**2 + z**2 + x*y + y*z + z*x

for i in range(n):
    s = 0
    for x in range(1, n+1, 1):
        if x**2 + 2*x + 3 > i+1:
            print(s)
            break
        else:
            for y in range(1, x+1, 1):
                for z in range(1, y+1, 1):
                    if f(x,y,z) == i+1:
                        if x == y and y == z:
                            s += 1
                        elif x == y or y == z:
                            s += 3
                        else:
                            s += 6

Submission status: Time Limit Exceeded

Solution code:
#C - XYZ Triplets
N = int(input())
ans = 0
for l in range(N):
    ans = 0
    for i in range(int((l+1)**0.5)):
        for j in range(int((l+1)**0.5)):
            # a = (i+1)+(j+1)
            # b = (i+1)*(j+1)
            # if (i + 1) ** 2 + (j + 1) ** 2 + (k + 1) ** 2 + (i + 1) * (j + 1) + (j + 1) * (k + 1) + (k + 1) * (
            #         i + 1) == l + 1:
            for k in range(max((i+1),(j+1))):
                if (i+1)**2 + (j+1)**2 + (k+1)**2 +(i+1)*(j+1)+(j+1)*(k+1)+(k+1)*(i+1)== l+1:
                    if i == j == k:
                        ans = 1
                        break

                    elif (i == j and j !=k) or (k == j and i !=k):
                        ans = 3
                        break
                    else:
                        ans = 6
                        break
                break
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
def solve():
    for n in range(1,N+1):
        cnt = 0
        for x in range(1,int(n**0.5)):
            if 6*(x**2) == n:
                cnt += 1
                break
            for y in range(x,int(n**0.5)):
                if 3*(x**2) + y**2 + 2*x*y == n:
                    cnt += 3
                    x += 1
                    break 
                for z in range(y,int(n**0.5)):
                    if x**2+y**2+z**2+x*y+y*z+z*x==n:
                        cnt += 3
                        x += 1
                        break                
        print(cnt)

if __name__=="__main__":
    N = int(input())
    solve()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

for i in range(1, N+1):
    num = 0
    sqi = int(float(i)**0.5)
    for j in range(1,sqi+1):
        sqj = int(float(i-j**2)**0.5)
        for k in range(1, sqj+1):
            c = float(i-j**2-k**2-j*k)
            if c > 0:
                c *= -1.0
                b = float(j) + float(k)
                d = b**2-4*c
                if d >=0.0:
                    z = (-b + d**0.5)/2.0
                    if z.is_integer():
                        #print(j,k,z)
                        num +=1
    print(num)

Submission status: Time Limit Exceeded

Solution code:
import math
def equal(x,y,z):
    return x**2 + y**2 + z**2 +x*y+y*z+z*x

N = int(input())

for i in range(1,N+1):
    cnt = 0
    for x in range(1,math.ceil(math.sqrt(i))+1):
        for y in range(1,math.ceil(math.sqrt(i))+1):
            for z in range(1,math.ceil(math.sqrt(i))+1):
                if equal(x,y,z) == i:
                    #print(x,y,z)
                    cnt+=1
    print(cnt)