1 min de leitura ·

Dúvida exercício beecrowd 1973

Olá pessoal, me chamo João Pedro e faço Engenharia de Software pela Universidade de Pernambuco. Hoje me deparei com um exercício passado em sala de aula um tanto quanto interessante. O exercício em questão é o mesmo que o número 1973 disponibilizado para iniciantes, mesmo executando inúmeras submissões meu código acaba excedendo o limite de tempo necessário para ser aceito pelo site. Abaixo segue meu código, gostaria de ajuda sobre como posso tá otimizando-o de forma suficiente para que o site aceite.

fazendas = int(input().strip())

if 1 <= fazendas <= 10**6:
    estrela = list(map(int, input().strip().split()))
    if all(1 <= x <= 10**6 for x in estrela):
        pos = 0
        visitadas_total = 0
    
        while 0 <= pos < fazendas:
            if estrela[pos] > 0:
                visitadas_total += 1
                if estrela[pos] % 2 == 0:
                    estrela[pos] -= 1
                    pos -= 1
                else:
                    estrela[pos] -= 1
                    pos += 1
            else:
                break
    
        restantes = 0
        for i in range(fazendas):
            restantes += estrela[i]
    
        print(visitadas_total, restantes)

Fonte: https://judge.beecrowd.com/pt/problems/view/1973

Pilati

2 dias atrás

Não entendo muito de python mas vou tentar ajudar

estrela = list(map(int, input().strip().split()))

Você está pegando uma linha com 1000000 inteiros diferentes (alguns milhões de caracteres), lendo todos de uma só vez, splitando, transformando em map, transformando em list .....

Só aqui seu processamento já está absurdo. a recomendação é otimizar essa leitura.

if all(1 <= x <= 10**6 for x in estrela)

aqui você está percorrendo toda a lista verificando se está dentro dos valores? Porque? não há nenhuma necessidade de fazer essa verificação

Acredito que seu problema esteja nesses 2 fatores

Sadzin

Autor

22 horas atrás

Tentei fazer algo nessa pegada:

input = sys.stdin.readline

fazendas = int(input())
estrela = list(map(int, input().split()))

visitadas = 0
pos = 0
vis = [False] * fazendas

while 0 <= pos < fazendas and estrela[pos] > 0:
    if not vis[pos]:
        vis[pos] = True
        visitadas += 1

    current = estrela[pos]

    if current % 2 == 0:
        estrela[pos] -= 1
        pos -= 1
    else:
        estrela[pos] -= 1
        pos += 1

print(visitadas, sum(estrela))

novamente o código roda mas não em menos de 2 segundos.