×
Ir ao conteúdo
  • Cadastre-se

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


Posts recomendados

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

runtime_error.jpg

Link para o comentário
Compartilhar em outros sites

@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.

memory_limit.jpg

Link para o comentário
Compartilhar em outros sites

@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.

 

  • Obrigado 1
Link para o comentário
Compartilhar em outros sites

@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.

Link para o comentário
Compartilhar em outros sites

@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.

  • Curtir 1
Link para o comentário
Compartilhar em outros sites

@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.

Link para o comentário
Compartilhar em outros sites

@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.

  • Curtir 1
Link para o comentário
Compartilhar em outros sites

Crie uma conta ou entre para comentar

Você precisa ser um usuário para fazer um comentário

Criar uma conta

Crie uma nova conta em nossa comunidade. É fácil!

Crie uma nova conta

Entrar

Já tem uma conta? Faça o login.

Entrar agora

Sobre o Clube do Hardware

No ar desde 1996, o Clube do Hardware é uma das maiores, mais antigas e mais respeitadas comunidades sobre tecnologia do Brasil. Leia mais

Direitos autorais

Não permitimos a cópia ou reprodução do conteúdo do nosso site, fórum, newsletters e redes sociais, mesmo citando-se a fonte. Leia mais

×
×
  • Criar novo...

Curso de Hacker Ético

LANÇAMENTO!

CLIQUE AQUI E CONFIRA!

* Este curso não é ministrado pela equipe do Clube do Hardware.