[At Coder] Triplés Acing C-XYZ

Ceci est le numéro C du Concours de programmation Acing 2020. J'ai eu du mal, alors j'ai regardé en arrière avec le code qui a échoué.

Échec 1 (TLE)

n=int(input())
def f_count(j):
   count=0
   for x in range(1,j):
       for y in range(1,j):
           for z in range(1,j):
               if x**2+y**2+z**2+x*y+y*z+z*x==j:
                   count+=1
   return count
   
for i in range(1,n+1):
   print(f_count(i))

Il s'agit d'une méthode de définition d'une fonction f_count (j) qui trouve f (n), d'affectation de 1 à n à j et de sortie.

Depuis que le temps était révolu, j'ai essayé d'effacer z, mais c'était encore fini.

** <Point 1> **

En regardant la réponse, la valeur maximale de n est 10 ** 4. Puisque x, y, z sont au carré, la valeur maximale de x, y, z est inférieure à 100.

** <Point 2> **

Au moment de f (1), toute la recherche de x, y, z de 1 à 100 → Au moment de f (2), toute la recherche de x, y, z de 1 à 100 ... Cela prend du temps.

Échec 2

N=int(input())
#f(N)Liste à mettre
ans_list=[0]*N
for x in range(1,100):
   for y in range(1,100):
       for z in range(1,100):
           s=x**2+y**2+z**2+x*y+y*z+z*x
           if s<=N:
               ans_list[s]+=1
           
  
for i in range(1,N+1):
  print(ans_list[i])

<Résultat> IndexError: index de liste hors limites

Remplacez 1 par 100 pour x, y, z, calculez la valeur de x ** 2 + y ** 2 + z ** 2 + x * y + y * z + z * x, et listez le résultat ans_list Je l'ai mis.

Cependant, j'ai fait une erreur dans la gamme. Puisque ans_list [0] = [], ans_list [1] = f (1), ans_list [N-1] = f (N-1), f (N) n'est plus inclus dans la liste.

Bonne réponse 1

N=int(input())
max_x=int(N**0.5)
ans_list=[0]*N

for x in range(1,max_x):
   for y in range(1,max_x):
       for z in range(1,max_x):
           s=x**2+y**2+z**2+x*y+y*z+z*x
           if s<=N:
               ans_list[s-1]+=1
               
for i in range(N):
   print(ans_list[i])

J'ai mis ans_list [s-1] + = 1.

Bonne réponse 2

n=int(input())

keys=[i for i in range(1,n+1)]
values=[0 for i in range(1,n+1)]
dic=dict(zip(keys,values))

for x in range(1,100):
    for y in range(1,100):
        for z in range(1,100):
            num=x**2+y**2+z**2+x*y+y*z+z*x
            if 1<=num<=n:
                dic[num]+=1


for key in dic:
    value=dic[key]
    print(value)

Pour la bonne réponse 1, j'ai essayé d'en faire un dictionnaire car l'index de la liste et n de f (n) ne s'écartaient pas clairement.