Python Programação dinâmica, runtime error e Python!

[kampa896]

Pessoal, boa tarde. Devido a faculdade, comecei a aprender um pouco de Python e testar os conhecimentos em sites de programação competitiva.

Estou com um problema há um tempo e não consigo localizar a solução.

 

total = []
acess = False
n_0 = 0
n_1 = 0
n_2 = 0
n_3 = 0
n_4 = 0
n_5 = 0
n_6 = 0
n_7 = 0
n_8 = 0
n_9 = 0

numeros = input()
vetor = numeros.split()
num1 = int(vetor[0])
num2 = int(vetor[1])

for n in range(100000):
    total.append([acess, n_0, n_1, n_2, n_3, n_4, n_5, n_6, n_7, n_8, n_9])

while num1 != 0 and num2 != 0:

    for n in range(num1, (num2 + 1)):
        string = str(n)
        lista = list(string)
        lista1 = total[n]
        if lista1[0]:
            continue
        else:
            tam = len(string)
            for i in range(tam):
                if lista[i] == '0':
                    n_0 += 1
                if lista[i] == '1':
                    n_1 += 1
                if lista[i] == '2':
                    n_2 += 1
                if lista[i] == '3':
                    n_3 += 1
                if lista[i] == '4':
                    n_4 += 1
                if lista[i] == '5':
                    n_5 += 1
                if lista[i] == '6':
                    n_6 += 1
                if lista[i] == '7':
                    n_7 += 1
                if lista[i] == '8':
                    n_8 += 1
                if lista[i] == '9':
                    n_9 += 1
            acess = True
            total.insert(n, [acess, n_0, n_1, n_2, n_3, n_4, n_5, n_6, n_7, n_8, n_9])
            n_0 = 0
            n_1 = 0
            n_2 = 0
            n_3 = 0
            n_4 = 0
            n_5 = 0
            n_6 = 0
            n_7 = 0
            n_8 = 0
            n_9 = 0

    for n in range(1, 11):
        dig = 0
        for i in range(num1, (num2 + 1)):
            a = total[i]
            b = int(a[n])
            dig += b
        if n == 10:
            print('%d' % dig)
        else:
            print('%d ' % dig, end='')

    numeros = input()
    vetor = numeros.split()
    num1 = int(vetor[0])
    num2 = int(vetor[1])

 

Na linha 27 do código, o "juiz online" acusa IndexError, porém eu não consigo entender o motivo. A linha é a seguinte: "lista1 = total[n]", que se encontra na imagem em anexo.

Se alguém puder me dar uma luz, eu agradeço. O exercício encontra-se no seguinte link: https://www.beecrowd.com.br/judge/pt/problems/view/1138

[Midori]

@kampa896 Sua lista tem o tamanho de 10^5 e como você está usando o contador do for como indice, esse valor pode chegar a 10^8 já que o range está pegando os valores de A e B. Acho que é isso.

[kampa896]

@Midori eu abaixei o índice porque meu computador não consegue rodar...

 

Mas deixa eu te perguntar. No meu código o índice fica igual a "n", que tem o mesmo valor de "num1". O programa não deveria entender que está dentro dos valores? Por IndexError é quando o índice não existe na lista, não é?

 

Eu alterei conforme você comentou e apresentou memória excedida... é um número muito alto pra ser calculado, meu notebook travou algumas vezes que insisti pro programa rodar.

[Midori]

@kampa896 Acho que o código pode ser mais simples sem uma lista tão grande.

 

Tente usar apenas uma lista para armazenar a quantidade dos 10 dígitos, algo assim:

 

n1 = 12
n2 = 321
digitos = [0] * 10

for n in range(n1, n2 + 1):
    for d in str(n):
        digitos[int(d)] += 1
        
print(digitos)

 

Nos casos dos exemplos deu certo, mas não testei na plataforma e acho que assim vai passar do limite de tempo. Esse é um desafio nível 8 então não será tão fácil resolver.

 

[kampa896]

@Midori sim, simplificar a função estourará no tempo.

Sim, o desafio valeu a pena, pra entender a lógica utilizada na programação dinâmica.

Eu só estou com dúvida na questão da lista mesmo. Porque que está dando erro IndexError.

Mas vou continuar pesquisando. Obrigado pela atenção.

[Midori]

@kampa896 É como comentei sobre o tamanho da lista. Se ela foi criada para ter x elementos, quando tentar acrescentar x + 1 vai dar esse erro. É isso que acontece p.ex neste código, vai dar erro na atribuição do índice 2 já que ele não existe (a lista tem tamanho 2 e vai de 0 a 1) :

  

x = [0] * 2

x[0] = 10
x[1] = 20
x[2] = 30

 

No seu código quando o valor do range num1-num2 passa o tamanho acontece o erro.

[kampa896]

@Midori eu entendi, meu amigo.

Mas olha que estranho. A lista 'lista1' recebe o valor da lista 'total[n]'. Ou seja, a lista 'total' é uma lista de lista. A lista 'lista1' vai receber o valor da lista 'total' de  índice 'n'.

Se eu colocar o valor de 10^8 como diz no enunciado do exercício, a própria plataforma da erro de limite de memória, como postei aí em cima.

Além do mais, a variável 'lista1' é uma variável local, que recebe os valores do 'range' do for a qual ela pertence.

 

Então nunca terá um valor acima do índice, entende? Por isso que não estou entendendo este erro.

Mas agradeço a atenção, meu amigo.

[Midori]

@kampa896 O erro é referente a lista total e portanto antes da lista1 receber o valor. Não importa se é lista de lista, a questão é apenas o índice n da lista total. Em relação ao erro do limite de memória é questão de programar de outra forma e não criar uma lista tão grande.